• Consider the following two statements about regular languages:
  S₁: Every infinite regular language contains an undecidable language as a subset.
  S₂: Every finite language is regular.
  Which one of the following choices is correct.?

In some programming languages, an identifier is permitted to be a letter following by any number of letters or digits. If L and D denote the sets of letters and digits respectively, which of the following expressions defines an identifier?

Consider a grammar with the following productions

S → a∝b|b∝c| aB
S → ∝S|b
S → ∝b b|ab
S ∝ → bd b|b 

The above grammar is:

Which of the following definitions below generates the same language as L, where L = {xⁿyⁿ such that n >= 1}?

 I. E → xEy|xy
 II. xy|(x+xyy+)
 III. x+y+ 

A finite state machine with the following state table has a single input x and a single out z.

If the initial state is unknown, then the shortest input sequence to reach the final state C is:

Let Σ = {0,1}, L = Σ* and R = {0ⁿ1ⁿ such that n >0} then the languages L ∪ R and R are respectively

Let L be a language over ∑ i.e., *L ≤ ∑ . Suppose L satisfies the two conditions given below
(i) L is in NP and
(ii) For every n, there is exactly one string of length n that belongs to L.
Let L^c be the complement of L over ∑*. Show that L^c is also in NP.

Consider the language L = {aⁿ| n≥0} ∪ {aⁿbⁿ| n≥0} and the following statements.

I. L is deterministic context-free.
II. L is context-free but not deterministic context-free.
III. L is not LL(k) for any k.

Which of the above statements is/are TRUE?

Consider the following statements.

I. If L₁ ∪ L₂ is regular, then both L₁ and L₂ must be regular.
II. The class of regular languages is closed under infinite union.

Which of the above statements is/are TRUE?

Which one of the following regular expressions represents the set of all binary strings with an odd number of 1’s?

Which of the following languages are undecidable? Note that indicates encoding of the Turing machine M.

L₁ = | L(M) = Φ}
L₂ = {| M on input w reaches state q in exactly 100 steps}
L₃ = {| L(M) is not recursive}
L₄ = {| L(M) contains at least 21 members}

Consider the following language.

   L = {x ∈ {a,b}* | number of a’s in x is divisible by 2 but not divisible by 3} 

The minimum number of states in a DFA that accepts L is ______.

Consider the following languages.

L₁ = {wxyx | w,x,y ∈ (0 + 1)⁺}
L₂ = {xy | x,y ∈ (a + b)*, |x| = |y|, x ≠ y}

Which one of the following is TRUE?

Which two of the following four regular expressions are equivalent? (ε is the empty string).

(i) (00)*(ε+0)
(ii) (00)*
(iii) 0*
(iv) 0(00)*

Which of the following statements is false?

Let L ⊆ Σ* where Σ = {a, b}. Which of the following is true?

If L₁ and L₂ are context free languages and R a regular set, one of the languages below is not necessarily a context free language. Which one?

Define for a context free language L ⊆ {0,1}*, init(L) = {u ∣ uv ∈ L for some v in {0,1}∗} (in other words, init(L) is the set of prefixes of L)
Let L = {w ∣ w is nonempty and has an equal number of 0’s and 1’s}
Then init(L) is

The grammar whose productions are

  → if id then 
  → if id then   else 
  → id := id 

is ambiguous because

Consider the given figure of state table for a sequential machine. The number of states in the minimized machine will be

Let G be a context-free grammar where G = ({S, A, B, C},{a,b,d},P,S) with the productions in P given below.

   S → ABAC
   A → aA ∣ ε
   B → bB ∣ ε
   C → d  

(ε denotes null string). Transform the grammar G to an equivalent context-free grammar G' that has no ε productions and no unit productions. (A unit production is of the form x → y, and x and y are non terminals.)

Let Q = ({q₁,q₂}, {a,b}, {a,b,Z}, δ, Z, ϕ) be a pushdown automaton accepting by empty stack for the language which is the set of all non empty even palindromes over the set {a,b}. Below is an incomplete specification of the transitions δ. Complete the specification. The top of the stack is assumed to be at the right end of the string representing stack contents.

(1) δ(q1,a,Z) = {(q1,Za)}
(2) δ(q1,b,Z) = {(q1,Zb)}
(3) δ(q1,a,a) = {(.....,.....)}
(4) δ(q1,b,b) = {(.....,.....)}
(5) δ(q2,a,a) = {(q2,ϵ)}
(6) δ(q2,b,b) = {(q2,ϵ)}
(7) δ(q2,ϵ,Z) = {(q2,ϵ)} 

Given Σ = {a,b}, which one of the following sets is not countable?

Which one of the following regular expressions over {0,1} denotes the set of all strings not containing 100 as a substring?

Which one of the following is not decidable?

Which of the following languages over {a,b,c} is accepted by a deterministic pushdown automata?

 Note: wR  is the string obtained by reversing 'w'. 

Let N be an NFA with n states. Let k be the number of states of a minimal DFA which is equivalent to N. Which one of the following is necessarily true?

The set of all recursively enumerable languages is

If the regular set A is represented by A = (01 + 1)* and the regular set ‘B’ is represented by B = ((01)*1*)*, which of the following is true?

Both A and B are equal, which generates strings over {0,1}, while 0 is followed by 1.

Regarding  the power of recognition of languages, which of the following statements is false?

The string 1101 does not belong to the set represented by

How many sub strings of different lengths (non-zero) can be found formed from a character string of length n?

Let L be the set of all binary strings whose last two symbols are the same. The number of states in the minimum state deterministic finite 0 state automaton accepting L is

Which of the following statements is false?

Design a deterministic finite state automaton (using minimum number of states) that recognizes the following language:
L = {w ∈ {0,1}* | w interpreted as a binary number (ignoring the leading zeros) is divisible by 5}

Let M = ({q₀, q₁}, {0, 1}, {z₀, x}, δ, q₀, z₀, ∅) be a pushdown automaton where δ is given by

δ(q₀, 1, z₀) = {(q₀, xz₀)}
δ(q₀, ε, z₀) = {(q₀, ε)}
δ(q₀, 1, X) = {(q₀, XX)}
δ(q₁, 1, X) = {(q₁, ε)}
δ(q₀, 0, X) = {(q₁, X)}
δ(q₀, 0, z₀) = {(q₀, z₀)}

(a) What is the language accepted by this PDA by empty stack?

(b) Describe informally the working of the PDA.

(a) Let G₁ = (N, T, P, S₁) be a CFG where,
N = {S₁, A, B}, T = {a,b} and
P is given by

         S1 → aS1b             S1 → aBb
         S1 → aAb              B → Bb
         A → aA                B → b
         A → a 

What is L(G1)?

(b) Use the grammar in part(a) to give a CFG
for L₂ = {aⁱ b^j a^k b^l | i, j, k, l ≥ 1, i=j or k=l} by adding not more than 5 production rule.

(c) Is L₂ inherently ambiguous?

(a) An identifier in a programming language consists of upto six letters and digits of which the first character must be a letter. Derive a regular expression for the identifier.

(b) Build an LL(1) parsing table for the language defined by the LL(1) grammar with productions

Program → begin d semi X end
X → d semi X | sY
Y → semi s Y | ε 

Consider the regular expression (0 + 1) (0 + 1)…. N times. The minimum state finite  automation  that  recognizes  the  language  represented  by  this  regular expression contains

Context-free languages are closed under: