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

Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two zeros. For example, 001110 and 011001 are in the language, but 100010 is not. All strings of length less than 3 are also in the language. A partially completed DFA that accepts this language is shown below.

The missing arcs in the DFA are

Given the language L ={ab,aa,baa}, which of the following strings are in L *?

1) abaabaaabaa
2) aaaabaaaa
3) baaaaabaaaab
4) baaaaabaa

Which of the following problems are decidable?

1) Does a given program ever produce an output?

2) If L is a context-free language, then, is also context-free?

3) If L is a regular language, then, is also regular?

4) If L is a recursive language, then, is also recursive?

What is the complement of the language accepted by the NFA shown below?

Assume Σ={a} and ε is the empty string.

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

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

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

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

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?