Draw the state transition of a deterministic finite state automaton which accepts all strings from the alphabet {a,b}, such that no string has 3 consecutive occurrences of the letter b.

A simple Pascal like language has only three statements.
(i) assignment statement e.g. x:=expression
(ii) loop construct e.g. for i:=expression to expression do statement.
(iii) sequencing e.g. begin statement ;…; statement end

(a) Write a context-free grammar (CFG) for statements in the above language. Assume that expression has already been defined. Do not use optional parentheses and * operator in CFG.
(b) Show the parse tree for the following statement:

     for j:=2 to 10 do
         begin x:=expr1;
               y:=expr2
         end  

If the state machine described in figure, should have a stable state, the restriction on the inputs is given by

(a) Given a set
S = {x| there is an x-block of 5's in the decimal expansion of π}
(Note: x-block is a maximal block of x successive 5’s)
Which of the following statements is true with respect to S? No reasons need to be given for the answer.

(i) S is regular
(ii) S is recursively enumerable
(iii) S is not recursively enumerable
(iv) S is recursive

(b) Given that a language L₁ is regular and that the language L₁ ∪ L₂ is regular, is the language L₂ always regular? Prove your answer.

A grammar G is in Chomsky-Normal Form (CNF) if all its productions are of the form A → BC or A → a, where A, B and C, are non-terminals and a is a terminal. Suppose G is a CFG in CNF and w is a string in L(G) of length, then how long is a derivation of w in G?

Every subset of a countable set is countable.
State whether the above statement is true or false with reason.

The regular expression for the language recognized by the finite state automaton of figure is __________

Which of the following features cannot be captured by context-free grammars?

Which of the following conversions is not possible (algorithmically)?

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.

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

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:

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+ 

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:

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 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}

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

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?

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?

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,ϵ)} 

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.)

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

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

Which of the following statements is false?

Let L ⊆ Σ* where Σ = {a, b}. Which 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)*

Let Σ be the set of all bijections from {1, ..., 5} to {1, ..., 5}, where id denotes the identity function i.e. id(j) = j,∀j. Let º denote composition on functions. For a string x = x₁ x₂ ... x_n ∈ Σⁿ, n ≥ 0. Let π(x) = x₁ º x₂ º ... º x_n.

Consider the language L = {x ∈ Σ* | π(x) = id}. The minimum number of  states in any DFA accepting L is ______.

Which one of the following languages over Σ = {a,b} is NOT context-free?

Consider the following sets:

S1.  Set of all recursively enumerable languages over the alphabet {0,1}
S2.  Set of all syntactically valid C programs
S3.  Set of all languages over the alphabet {0,1}
S4.  Set of all non-regular languages over the alphabet {0,1}

Which of the above sets are uncountable?

For Σ = {a,b}, let us consider the regular language L = {x|x = a^2+3k or x = b^10+12k, k ≥ 0}. Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for L?

If L is a regular language over Σ = {a,b}, which one of the following languages is NOT regular?

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'. 

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?

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

(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 | ε 

(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?

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.

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}

Which of the following statements is false?

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