TheoryofComputation
Question 1 
If L is a regular language over Σ = {a,b}, which one of the following languages is NOT regular?
A  Suffix (L) = {y ∈ Σ* such that xy ∈ L} 
B  {ww^{R} │w ∈ L} 
C  Prefix (L) = {x ∈ Σ*│∃y ∈ Σ* such that xy ∈ L} 
D  L ∙ L^{R} = {xy │ x ∈ L, y^{R} ∈ L} 
Question 2 
For Σ = {a,b}, let us consider the regular language L = {xx = 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?
A  3 
B  9 
C  5 
D  24 
For any language L, there exists an integer n, such that for all x ∈ L with x ≥ n, there exists u,v, w ∈ Σ*, such that x = uvw, and
(1) uv ≤ n
(2) v ≥ 1
(3) for all i ≥ 0: uv^{i}w ∈ L
We have to find “n” which satisfies for all the strings in L.
Considering strings derived by b^{10+12k}.
The minimum string in L = “bbbbbbbbbb” but this string b^{10} cannot be broken in uvw.
So, pumping length 3, 9 and 5 cannot be the correct answer.
So, the minimum pumping length, such that any string in L can be divided into three parts “uvw” must be greater than 10.
Question 3 
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 nonregular languages over the alphabet {0,1}
Which of the above sets are uncountable?
A  S2 and S3 
B  S3 and S4 
C  S1 and S4 
D  S1 and S2 
S2 is countable, since a valid C program represents a valid algorithm and every algorithm corresponds to a Turing Machine, so S2 is equivalent to set of all Turing Machines.
S3 is is uncountable, it is proved by diagonalization method.
S4 is uncountable, as set of nonregular languages will have languages which is set of all languages over alphabet {0,1} i.e., S3.
Question 4 
Which one of the following languages over Σ = {a,b} is NOT contextfree?
A  {ww^{R} w ∈ {a,b}*} 
B  {wa^{n}w^{R}b^{n} w ∈ {a,b}*, n ≥ 0} 
C  {a^{n}b^{i}  i ∈ {n, 3n, 5n}, n ≥ 0} 
D  {wa^{n}b^{n}w^{R} w ∈ {a,b}*, n ≥ 0} 
This is similar to language
L = {a^{n}b^{m}c^{n}d^{m}  n, m > 0}
Suppose we push “w” then a^{n} and then w^{R}, now we cannot match b^{n} with a^{n}, because in top of stack we have w^{R}.
Question 5 
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_{1} x_{2} … x_{n} ∈ Σ^{n}, n ≥ 0. Let π(x) = x_{1} º x_{2} º … º x_{n}.
Consider the language L = {x ∈ Σ*  π(x) = id}. The minimum number of states in any DFA accepting L is ______.
A  120 
B  136 
C  125 
D  132 
Question 6 
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?
A  k ≥ 2^{n} 
B  k ≥ n 
C  k ≤ n^{2} 
D  k ≤ 2^{n}

In other words, if number of states in NFA is “n” then the corresponding DFA have at most 2^{n} states.
Hence k ≤ 2^{n} is necessarily true.
Question 7 
The set of all recursively enumerable languages is
A  closed under complementation. 
B  closed under intersection. 
C  a subset of the set of all recursive languages. 
D  an uncountable set. 
Recursive enumerable languages are not closed under Complementation.
Recursive enumerable languages are a countable set, as every recursive enumerable language has a corresponding Turing Machine and set of all Turing Machine is countable.
Recursive languages are subset of recursive enumerable languages.
Question 8 
L^{0} = {ε}
L^{i} = L^{i1}∙L for all i>0
The order of a language L is defined as the smallest k such that L^{k} = L^{k+1}.
Consider the language L_{1} (over alphabet 0) accepted by the following automaton.
The order of L_{1} is ______.
A  2 
B  3 
C  4 
D  5 
Now L_{1}^{0} = ϵ and L_{1}^{1} = ϵ . (ϵ+0 (00)*) = ϵ + 0 (00)* = L_{1}
Now L_{1}^{2} = L_{1}^{1} .
L_{1} = L_{1} .
L_{1} = (ϵ + 0 (00)*) (ϵ + 0 (00)*)
= (ϵ + 0 (00)* + 0(00)* + 0(00)*0(00)*)
= (ϵ + 0 (00)* + 0(00)*0(00)* ) = 0*
As it will contain epsilon + odd number of zero + even number of zero, hence it is 0*
Now L_{1}^{3} = L_{1}^{2} .
L_{1} = 0* (ϵ + 0 (00)*) = 0* + 0*0(00)* = 0*
Hence L_{1}^{2} = L_{1}^{3}
Or L_{1}^{2} = L_{1}^{2+1} ,
hence the smallest k value is 2.
Question 9 
I. {a^{m} b^{n} c^{p} d^{q} ∣ m + p = n + q, where m, n, p, q ≥ 0}
II. {a^{m} b^{n} c^{p} d^{q} ∣ m = n and p = q, where m, n, p, q ≥ 0}
III. {a^{m} b^{n} c^{p} d^{q} ∣ m = n = p and p ≠ q, where m, n, p, q ≥ 0}
IV. {a^{m} b^{n} c^{p} d^{q} ∣ mn = p + q, where m, n, p, q ≥ 0}
Which of the above languages are contextfree?
A  I and IV only 
B  I and II only 
C  II and III only 
D  II and IV only 
mn = qp
First we will push a’s in the stack then we will pop a’s after watching b’s.
Then some of a’s might left in the stack.
Now we will push c’s in the stack and then pop c’s by watching d’s.
And then the remaining a’s will be popped off the stack by watching some more d’s.
And if no d’s is remaining and the stack is empty then the language is accepted by CFG.
ii) a^{m} b^{n} c^{p} d^{q}  m=n, p=q
Push a’s in stack. Pop a’s watching b’s.
Now push c’s in stack.
Pop c’s watching d’s.
So it is context free language.
iii) a^{m} b^{n} c^{p} d^{q}  m=n=p & p≠q
Here three variables are dependent on each other. So not context free.
iv) Not context free because comparison in stack can’t be done through multiplication operation.
Question 10 
(I) For an unrestricted grammar G and a string w, whether w∈L(G)
(II) Given a Turing machine M, whether L(M) is regular
(III) Given two grammar G_{1} and G_{2} whether L(G_{1}) = L(G_{2})
(IV) Given an NFA N, whether there is a deterministic PDA P such that N and P accept the same language
Which one of the following statement is correct?
A  Only I and II are undecidable 
B  Only III is undecidable 
C  Only II and IV are undecidable 
D  Only I, II and III are undecidable 
I, II and III is undecidable.
Question 11 
S → abScT  abcT
T → bT  b
Which one of the following represents the language generated by the above grammar?
A  {(ab)^{n} (cb)^{n}│n ≥ 1} 
B  {(ab)^{n} cb^{(m1 )} cb^{(m2 )}…cb^{(mn )}│n,m_{1},m_{2},…,m_{n} ≥ 1} 
C  {(ab)^{n} (cb^{m})^{n}│m,n ≥ 1} 
D  {(ab)^{n} (cb^{n})^{m}│m,n ≥ 1} 
S→ abScT  abcT, this production will generate equal number of “ab” and “c” and for every “abc” any number of b’s ( > 1) after “abc”.
For Ex:
Hence the language generated by the grammar is
L = {(ab)^{n} cb^{(m1 )} cb^{(m2 )}…cb^{(mn )}│n,m_{1},m_{2},…,m_{n} ≥ 1}
Question 12 
Consider the language L given by the regular expression (a+b)*b(a+b) over the alphabet {a,b}. The smallest number of states needed in deterministic finitestate automation (DFA) accepting L is _________.
A  4 
B  5 
C  6 
D  7 
After converting the NFA into DFA:
After converting the NFA into DFA:
Question 13 
S → SaS  aSb  bSa  SS  ϵ
where S is the start variable, then which one of the following strings is not generated by G?
A  abab 
B  aaab 
C  abbaa 
D  babba 
But the string “babba” can’t be generated by the given grammar.
The reason behind this is, we can generate any number of a’s with production S→ SaS, but for one “b” we have to generate one “a”, as the production which is generating “b” is also generating “a” together (S→ aSb and S→ bSa).
So in string “babba” the first and last “ba” can be generated by S→ bSa, but we can’t generate a single “b” in middle.
In other words we can say that any string in which number of “b’s” is more than number of “a’s” can’t be generated by the given grammar.
Question 14 
G_{1}: S → aSbT, T → cTϵ
G_{2}: S → bSaT, T → cTϵ
The language L(G_{1}) ∩ L(G_{2}) is
A  Finite 
B  Not finite but regular 
C  ContextFree but not regular 
D  Recursive but not contextfree 
{ϵ, c, cc, ccc, … ab, aabb, aaabbb….acb, accb… aacbb, aaccbb, …}
Strings generated by G_{2}:
{ϵ, c, cc, ccc, … ba, bbaa, bbbaaa….bca, bcca… bbcaa, bbccaa, …}
The strings common in L (G_{1}) and L (G_{2}) are:
{ϵ, c, cc, ccc…}
So, L (G_{1}) ∩ L (G_{2}) can be represented by regular expression: c*
Hence the language L (G_{1}) ∩ L (G_{2}) is “Not finite but regular”.
Question 15 
Let L_{1} = {a^{n} b^{n} c^{m}│m,n ≥ 0} and L_{2} = {a^{m} b^{n} c^{n}│m,n ≥ 0}
Which of the following are contextfree languages?
I. L_{1} ∪ L_{2}
II. L_{1} ∩ L_{2}
A  I only 
B  II only 
C  I and II 
D  Neither I nor II 
Strings in L_{2} = {ϵ, a, aa, …., bc, bbcc,…., abc, aabc,…, abbcc, aabbcc, aaabbcc,..}
Strings in L_{1} ∪ L_{2} ={ϵ, a, aa, .., c, cc,.. ab, bc, …, aabb, bbcc,.., abc, abcc, aabc,…}
Hence (L_{1} ∪ L_{2}) will have either (number of a’s = equal to number of b’s) OR (number of b’s = number of c’s).
Hence (L_{1} ∪ L_{2}) is CFL.
Strings in L_{1} ∩ L_{2} = {ϵ, abc, aabbcc, aaabbbccc,…}
Hence (L_{1} ∩ L_{2}) will have (number of a’s = number of b’s = number of c’s)
i.e., (L_{1} ∩ L_{2}) = {a^{n}b^{n}c^{n}  n ≥ 0} which is CSL.
Question 16 
Let A and B be finite alphabets and let # be a symbol outside both A and B. Let f be a total function from A* to B*. We say f is computable if there exists a Turing machine M which given an input x in A*, always halts with f(x) on its tape. Let L_{f} denote the language {x # f(x)│x ∈ A*}. Which of the following statements is true:
A  f is computable if and only if L_{f} is recursive. 
B  f is computable if and only if L_{f} is recursively enumerable. 
C  If f is computable then L_{f} is recursive, but not conversely. 
D  If f is computable then L_{f} is recursively enumerable, but not conversely. 
Total function means for every element in domain, there must be a mapping in range.
Let us consider A= {a, b} and B = {0,1}
The concept of computing has been intuitively linked with the concept of functions.
A computing machine can only be designed for the functions which are computable.
The basic definition is:
Given a recursive language L and a string w over Σ*, the characteristic function is given by
The function “f” is computable for every value of “w”.
However if the language L is not recursive, then the function f may or may not be computable.
Hence, f is computable iff L_{f} is recursive.
Question 17 
Let L_{1}, L_{2} be any two contextfree languages and R be any regular language. Then which of the following is/are CORRECT?
A  I, II and IV only 
B  I and III only 
C  II and IV only 
D  I only 
CFL is not closed under complementation.
So L_{1} compliment may or may not be CFL. Hence is Context free, is a false statement.
L_{1} – R means and Regular language is closed under compliment, so
is also a regular language, so we have now L_{1} ∩ R .
Regular language is closed with intersection with any language, i.e. L∩R is same type as L.
So L_{1}∩R is context free.
CFL is not closed under INTERSECTION, so L_{1} ∩ L_{2} may or may not be CFL and hence IV^{th} is false.
Question 18 
Identify the language generated by the following grammar, where S is the start variable.
S → XY X → aXa Y → aYbϵ
A  {a^{m} b^{n} │ m ≥ n, n > 0} 
B  {a^{m} b^{n} │ m ≥ n, n ≥ 0} 
C  {a^{m} b^{n} │ m > n, n ≥ 0} 
D  {a^{m} b^{n} │ m > n, n > 0} 
So the production S→XY can generate any number of a’s (≥1) in the beginning (due to X) and then Y will generate equal number of a’s and b’s.
So, the number of a’s will always be greater than number of b’s and number of b’s must be greater than or equal to 0 (as Y → ϵ, so number of b’s can be zero also).
Hence the language is {a^{m} b^{n}│m>n,n≥0}.
Question 19 
The minimum possible number of a deterministic finite automation that accepts the regular language L = {w_{1}aw_{2}  w_{1}, w_{2} ∈ {a,b}*, w_{1} = 2,w_{2} ≥ 3} is _________.
A  8 
B  9 
C  10 
D  11 
So we have four possibilities of w_{1} = {aa, ab, ba, bb}.
w_{2}  ≥ 3 means the w_{2} will have at least three length string from {a,b}.
w_{2} will have {aaa, aab, aba, abb, baa, bab, bba, bbb, ……….}
So, the required DFA is
Question 20 
Let δ denote the transition function and denote the extended transition function of the εNFA whose transition table is given below:
Then is
A  ∅ 
B  {q_{0},q_{1},q_{3}} 
C  {q_{0},q_{1},q_{2}} 
D  {q_{0},q_{2},q_{3}} 
If δ is our transition function, then the extended transition function is denoted by δ.
The extended transition function is a function that takes a state q and a string w and returns a state p (the state that the automaton reaches when starting in state q and processing the sequence of inputs w).
The starting state is q_{2}, from q_{2}, transition with input “a” is dead so we have to use epsilon transition to go to other state.
With epsilon transition we reach to q_{0}, at q_{0} we have a transition with input symbol “a” so we reach to state q_{1}.
From q_{1}, we can take transition with symbol “b” and reach state q_{2} but from q_{2}, again we have no further transition with symbol “a” as input, so we have to take another transition from state q_{1}, that is, the epsilon transition which goes to state q_{2}.
From q_{2} we reach to state q_{0} and read input “b” and then read input “a” and reach state q_{1}. So q_{1} is one of the state of extended transition function.
From q_{1} we can reach q_{2} by using epsilon transition and from q_{2} we can reach q_{0} with epsilon move so state q_{2} and q_{0} are also part of extended transition function.
So state q_{0},q_{1},q_{2}.
Question 21 
L_{1}= {a^{p}│p is a prime number}
L_{2}= {a^{n}b^{mc2m n ≥ 0, m ≥ 0} L3= {anbnc2n│ n ≥ 0} L4= {anbn│ n ≥ 1} Which of the following are CORRECT? I. L1 is contextfree but not regular. II. L2 is not contextfree. III. L3 is not contextfree but recursive. IV. L4 is deterministic contextfree.}
A  I, II and IV only 
B  II and III only 
C  I and IV only 
D  III and IV only 
L_{2} = {a^{n} b^{m} c^{2m}│n ≥ 0, m ≥ 0} is a context free as we have to do only one comparison (between b’s and c’s) which can be done by using PDA, so L^{2} is Context free and II is true.
L_{3} = {a^{n} b^{n} c^{2n}│n≥0} is context sensitive.
The reason it has more than one comparison (at a time) as we have to compare number of a’s, b’s and c’s.
So this cannot be done using PDA. Hence III is CSL and every CSL is recursive, so III is True
L_{4} = {a^{n} b^{n}│n ≥ 1} is Context free (as well as Deterministic context free).
We can define the transition of PDA in a deterministic manner.
In beginning push all a’s in stack and when b’s comes pop one “a” for one “b”.
If input and stack both are empty then accept.
Question 22 
Which of the following decision problems are undecidable?
I. Given a regular expression R and a string w, is w ∈ L(R)?
II. Given a contextfree grammar G, is L(G) = ∅?
III. Given a contextfree grammar G, is L(G) = Σ* for some alphabet Σ?
IV. Given a Turing machine M and a string w, is w ∈ L(M)?
A  I and IV only 
B  II and III only 
C  II, III and IV only 
D  III and IV only 
Emptiness problem for Context free language is decidable, so II is decidable.
Completeness problem (i.e. L(G) = Σ* for a CFG G) is undecidable.
Membership problem for recursive enumerable language (as language of Turing Machine is recursive enumerable) is undecidable.
So IV is undecidable.
Question 23 
Which of the following languages is generated by the given grammar?
A  {a^{n}b^{m} n,m ≥ 0} 
B  {w ∈ {a,b}*  w has equal number of a’s and b’s} 
C  {a^{n} n ≥ 0}∪{b^{n} n ≥ 0}∪{a^{n} b(sup>nn ≥ 0} 
D  {a,b}* 
Question 24 
I. Given NFAs N_{1} and N_{2}, is L(N_{1})∩L(N_{2})= Φ?
II. Given a CFG G = (N,Σ,P,S) and a string x ∈ Σ*, does x ∈ L(G)?
III. Given CFGs G and G_{2}, is L(G_{1}) = L(G_{2})?
IV. Given a TM M, is L(M) = Φ?
A  I and IV only 
B  II and III only 
C  III and IV only 
D  II and IV only 
Statement II is decidable, as for CFG we have membership algorithm, hence it is decidable.
But for problems in statement III and IV, there doesn’t exist any algorithm which can decide it.
Question 25 
Which one of the following regular expressions represents the language: the set of all binary strings having two consecutive 0s and two consecutive 1s?
A  (0 + 1)* 0011(0 + 1)* + (0 + 1)* 1100(0 + 1)* 
B  (0 + 1)* (00(0 + 1)* 11 + 11(0 + 1)* 00)(0 + 1)* 
C  (0 + 1)* 00(0 + 1)* + (0 + 1)* 11(0 + 1)* 
D  00(0 + 1)* 11 + 11(0 + 1)* 00 
Option C generates string “00” which doesn’t have two consecutive 1’s.
Option D doesn’t generate string “00110” which has two consecutive 0’s and two consecutive 1’s.
Question 26 
Consider the following contextfree grammars:
G_{1}: S → aSB, B → bbB G_{2}: S → aAbB, A → aABε, B → bBε
Which one of the following pairs of languages is generated by G_{1} and G_{2}, respectively?
A  {a^{m} b^{n}│m > 0 or n > 0} and {a^{m} b^{n} m > 0 and n > 0} 
B  {a^{m} b^{n}│m > 0 and n > 0} and {a^{m} b^{n} m > 0 or n≥0} 
C  {a^{m} b^{n}│m≥0 or n > 0} and {a^{m} b^{n} m > 0 and n > 0} 
D  {a^{m} b^{n}│m≥0 and n > 0} and {a^{m} b^{n} m > 0 or n > 0} 
S→aS;
will generate any number of a’s and then we can have any number of b’s (greater than zero) after a’s by using he productions
S→B and B→bbB
G_{2}:
By using S→aA and then A→aA  ϵ we can have only any number of a’s (greater than zero) OR we can use A→B and B→bB  ϵ to add any number of b’s after a’s OR by using S→bB and B→bB  ϵ we can have only any number of b’s (greater than zero).
Question 27 
Consider the transition diagram of a PDA given below with input alphabet Σ = {a,b} and stack alphabet Γ = {X,Z}. Z is the initial stack symbol. Let L denote the language accepted by the PDA.
Which one of the following is TRUE?
A  L = {a^{n} b^{n}│n ≥ 0} and is not accepted by any ﬁnite automata 
B  L = {a^{n} n≥0} ∪ {a^{n}b^{n}n ≥ 0} and is not accepted by any deterministic PDA 
C  L is not accepted by any Turing machine that halts on every input 
D  L = {a^{n} n ≥ 0} ∪ {a^{n} b^{n} n ≥ 0} and is deterministic contextfree 
where q_{0} and q_{2} are final states.
This PDA accepts the string by both ways i.e. by using q_{0} accepts as final state and by using q_{2} it accepts as empty stack.
Since q_{0} is initial as well as final state, so it can accept any number of a’s (including zero a’s) and by using q_{2} as empty stack it accept strings which has equal number of a’s and b’s (b’s comes after a’s).
Hence, L = {a^{n}  n≥0} ∪ { a^{n} b^{n}  n≥0}.
Question 28 
Let X be a recursive language and Y be a recursively enumerable but not recursive language. Let W and Z be two languages such that reduces to W, and Z reduces to (reduction means the standard manyone reduction). Which one of the following statements is TRUE?
A  W can be recursively enumerable and Z is recursive. 
B  W can be recursive and Z is recursively enumerable. 
C  W is not recursively enumerable and Z is recursive. 
D  W is not recursively enumerable and Z is not recursive. 
If A ≤ _{p} B
Rule 1: If B is recursive then A is recursive
Rule 2: If B is recursively enumerable then A is recursively enumerable
Rule 3: If A is not recursively enumerable then B is not recursively enumerable
Since X is recursive and recursive language is closed under compliment, so is also recursive.
: By rule 3, W is not recursively enumerable.
: By rule 1, Z is recursive.
Hence, W is not recursively enumerable and Z is recursive.
Question 29 
The number of states in the minimum sized DFA that accepts the language deﬁned by the regular expression
A  2 
B  3 
C  4 
D  5 
So, the DFA has two states.
Question 30 
Language L_{2} is deﬁned by the grammar: S_{2} → abS_{2}ε
Consider the following statements:
P: L_{1}is regular
Q: L_{2}is regular
Which one of the following is TRUE?
A  Both P and Q are true 
B  P is true and Q is false 
C  P is false and Q is true 
D  Both P and Q are false

So, in order to compare equality between a’s and b’s memory (stack) is required.
Hence, L_{1} is not regular.
Moreover, L_{1} = {a^{n} b^{n}  n ≥ 0} which is DCFL.
The language L_{2} generated by grammar contains repetition of “ab” i.e. L_{2} = (ab)* which is clearly a regular language.
Question 31 
Consider the following types of languages: L_{1}: Regular, L_{2}: Contextfree, L_{3} : Recursive, L_{4} : Recursively enumerable. Which of the following is/are TRUE?
A  I only 
B  I and III only 
C  I and IV only 
D  I, II and III only 
L_{3} is recursive, so is also recursive (because recursive language closed under complementation), so is recursive enumerable.
L_{4} is recursive enumerable.
So is also recursive enumerable (closed under union).
II.
L_{2} is context free, so L_{2} is recursive.
Since L_{2} is recursive. So is recursive.
L_{3} is recursive.
So is also recursive (closed under union)
III.
L_{1} is regular, so L_{1}* is also regular.
L_{2} is context free.
So, L_{1}*∩L_{2} is also context free (closed under regular intersection).
IV.
L_{1} is regular.
L_{2} is context free, so may or may not be context free (not closed under complement).
So, may or may not be context free.
Hence, answer is (D).
Question 32 
I. If all states of an NFA are accepting states then the language accepted by the NFA is Σ*.
II. There exists a regular language A such that for all languages B, A∩B is regular.
Which one of the following is CORRECT?
A  Only I is true 
B  Only II is true 
C  Both I and II are true 
D  Both I and II are false 
The reason is NFA doesn’t have dead state, so even though all states are final state in NFA, the NFA will reject some strings.
For ex:
Consider L = a*b*
The NFA would be:
Even though all states are final states in above NFA, but it doesn’t accept string “aba”.
Hence its language can’t be ∑*.
Statement II is true:
Since A= Φ is a regular language and its intersection with any language B will be Φ (which is regular).
Question 33 
L_{1} = {a^{n} b^{m} c^{n+m}: m,n ≥ 1}
L_{2}= {a^{n} b^{n} c^{2n}: n ≥ 1}
Which one of the following is TRUE?
A  Both L_{1} and L_{2} are contextfree. 
B  L_{1} is contextfree while L_{2} is not contextfree. 
C  L_{2} is contextfree while L_{1} is not contextfree. 
D  Neither L_{1} nor L_{2} is contextfree. 
At the end if input and stack is empty then accept.
Hence, it is CFL.
But L_{2} can’t be recognized by PDA, i.e. by using single stack.
The reason is, it has two comparison at a time,
1^{st} comparison:
number of a’s = number of b’s
2^{nd} comparison:
number of c’s must be two times number of a’s (or b’s)
It is CSL.
Question 34 
L_{1} = {〈M〉M takes at least 2016 steps on some input},
L_{2} = {〈M〉│M takes at least 2016 steps on all inputs} and
L_{3} = {〈M〉M accepts ε},
where for each Turing machine M, 〈M〉 denotes a speciﬁc encoding of M. Which one of the following is TRUE?
A  L_{1} is recursive and L_{2}, L_{3} are not recursive 
B  L_{2} is recursive and L_{1}, L_{3} are not recursive 
C  L_{1}, L_{2} are recursive and L_{3} is not recursive 
D  L_{1}, L_{2}, L_{3} are recursive 
Since counting any number of steps can be always decided.
We can simulate TM (M) whether it takes more than 2016 steps on some input string, which has length upto 2016.
If it happens then reached to accepting (YES) state else reject (NO).
L_{2} is recursive:
Similarly, we can simulate TM (M) whether it takes more than 2016 steps on each input string which has length upto 2016.
If it happens then reached to accepting (YES) state else reject (NO).
L_{3} is not recursive:
If L_{3} is recursive then we must have a Turing machine for L_{3}, which accept epsilon and reject all strings and always HALT.
Since Halting of Turing machine can’t be guaranteed in all the case.
Hence this language is not recursive.
Question 35 
int a[10][3];
The grammars use D as the start symbol, and use six terminal symbols int; id[] num.
Grammar G1 Grammar G2
D → intL; D → intL;
L → id[E L → idE
E → num] E → E[num]
E → num][E E → [num]
Which of the grammars correctly generate the declaration mentioned above?
A  Both G1 and G2 
B  Only G1 
C  Only G2 
D  Neither G1 nor G2 
Question 36 
For any two languages L_{1} and L_{2} such that L_{1} is contextfree and L_{2} is recursively enumerable but not recursive, which of the following is/are necessarily true?
A  I only 
B  III only 
C  III and IV only 
D  I and IV only 
This one is true, because L_{1} is context free which is nothing but recursive, recursive language is closed under complement hence true.
2 ⇒ (complement of L_{2}) is recursive
If L_{2} and both are recursive enumerable then is recursive.
Hence option 2 is false
3 ⇒ is context free
Which is false because context free language does not closed under complement
4 ⇒ ∪L_{2} is recursive enumerable
⇒ recursive
Every recursive language is also recursive enumerable
L_{2} ⇒ recursive enumerable
∪ L_{2} ⇒ recursive enumerable
Because recursive enumerable language closed under union.
Question 37 
Consider the DFAs M and N given above. The number of states in a minimal DFA that accepts the language L(M) ∩ L(N) is __________.
A  1 
B  2 
C  3 
D  4 
Question 38 
Consider the NPDA 〈Q = {q0, q1, q2}, Σ = {0, 1}, Γ = {0, 1, ⊥}, δ, q0, ⊥, F = {q2}〉, where (as per usual convention) Q is the set of states, Σ is the input alphabet, Γ is stack alphabet, δ is the state transition function, q0 is the initial state, ⊥ is the initial stack symbol, and F is the set of accepting states, The state transition is as follows:
A  10110 
B  10010 
C  01010 
D  01001 
Question 39 
Consider two decision problems Q_{1}, Q_{2} such that Q_{1} reduces in polynomial time to 3SAT and 3 SAT reduces in polynomial time to Q_{2}. Then which one of following is consistent with the above statement?
A  Q_{1} is in NP, Q_{2} in NP hard 
B  Q_{1} is in NP, Q_{2} is NP hard 
C  Both Q_{1} and Q_{2} are in NP 
D  Both Q_{1} and Q_{2} are NP hard 
Q_{1}≤p 3SAT≤p Q_{2} ≤p ≤p hence → Q1 is in NP
but Q_{2} is not given in NP
Hence Q_{2} is in NPHard.
Question 40 
Consider the following statements:

I. The complement of every Turning decidable language is Turning decidable
II. There exists some language which is in NP but is not Turing decidable
III. If L is a language in NP, L is Turing decidable
Which of the above statements is/are True?
A  Only II 
B  Only III 
C  Only I and II 
D  Only I and III 
Turing decidable language are recursive language which is closed under complementation.
II. False.
All language which is in NP are turing decidable.
III. True.
Question 41 
Which of the following language is/are regular ?
 L1: {wxw^{R} ⎪ w, x ∈ {a, b}* and ⎪w⎪, ⎪x⎪ >0} w^{R} is the reverse of string w
L2: {a^{n}b^{m} ⎪m ≠ n and m, n≥0}
L3: {a^{p}b^{q}c^{r} ⎪ p, q, r ≥ 0}
A  L_{1} and L_{3} only 
B  L_{2} only 
C  L_{2} and L_{3} only 
D  L_{3} only 
L_{2}: In this number of a’s is dependent on number of b’s. So PDA is needed.
L_{3}: Any number of a’s followed by any number of b’s followed by any number of c’s. Hence Regular.
Question 42 
The number of states in the minimal deterministic finite automaton corresponding to the regular expression (0 + 1) * (10) is __________.
A  3 
B  4 
C  5 
D  6 
No. of states in minimal DFA is 3.
Question 43 
Consider alphabet ∑ = {0, 1}, the null/empty string λ and the sets of strings X_{0}, X_{1} and X_{2} generated by the corresponding nonterminals of a regular grammar. X_{0}, X_{1} and X_{2} are related as follows:

X_{0} = 1 X_{1}
X_{1} = 0 X_{1} + 1 X_{2}
X_{2} = 0 X_{1} + {λ}
Which one of the following choices precisely represents the strings in X_{0}?
A  10(0* + (10*)* 1 
B  10(0* + (10)*)* 1 
C  1(0 + 10)* 1 
D  10(0 + 10)* 1 + 110(0 + 10)* 1 
From the given diagram we can write,
X_{0} = 1(0+10)* 1
Question 44 
Let L be the language represented by the regular expression Σ*0011Σ* where Σ = {0,1}. What is the minimum number of states in a DFA that recognizes (complement of L)?
A  4 
B  5 
C  6 
D  8 
So, 5 states are there.
Question 45 
Language L1 is polynomial time reducible to language L2. Language L3 is polynomial time reducible to L2, which in turn is polynomial time reducible to language L4. Which of the following is/are True?
 I. If L4 ∈ P, L2 ∈ P
II. If L1 ∈ P or L3 ∈ P, then L2 ∈ P
III. L1 ∈ P, if and only if L3 ∈ P
IV. If L4 ∈ P, then L1 ∈ P and L3 ∈ P
A  II only 
B  III only 
C  I and IV only 
D  I only 
L_{1} ≤ pL_{2}
If L_{4} ∈ P then L_{2} ∈ P hence L_{1} ∈ P, hence option C.
Question 46 
Which of the following languages are contextfree?
 L1 = {a^{m}b^{n}a^{n}b^{m} ⎪ m, n ≥ 1}
L2 = {a^{m}b^{n}a^{m}b^{n} ⎪ m, n ≥ 1}
L3 = {a^{m}b^{n} ⎪ m = 2n + 1}
A  L_{1} and L_{2} only 
B  L_{1} and L_{3} only 
C  L_{2} and L_{3} only 
D  L_{3} only 
L_{2}: First push all the a’s in the stack then push all the b’s in the stack. Now again a’s come which cannot be compared by previous a’s in the stack because at top of the stack’s there are b’s which is also needed to be pushed for further comparison with the next b’s. So not CFL.
L_{3}: First simply read one ‘a’, then push one ‘a’ in the stack after reading two a’s and then pop all the a’s by reading the b’s. Since can be done by PDA hence CFL.
Question 47 
Which one of the following is TRUE?
A  The language L={a^{n} b^{n}│n≥0} is regular. 
B  The language L={a^{n}│n is prime} is regular. 
C  The language L={w│w has 3k+1b’s for some k∈N with Σ={a,b} } is regular. 
D  The language L={ww│w∈Σ* with Σ={0,1} } is regular. 
L = {a^{n}  n is prime} is CSL, as calculation of “n is prime” can be done by LBA (Turing machine)
L = {ww  w ∈ ∑*} is CSL.
But L = { w  w has 3k+1 b’s for some k ∈ natural number} is regular.
Lets take values of k={1,2,3,….}
So number of b’s will be {4, 7, 10,……….} and number of a’s can be anything.
The DFA will be
Question 48 
Consider the finite automaton in the following figure.
What is the set of reachable states for the input string 0011?
A  {q_{0}, q_{1}, q_{2}} 
B  {q_{0}, q_{1}} 
C  {q_{0}, q_{1}, q_{2}, q_{3}} 
D  {q_{3}} 
{q_{0} , 0 → q_{0}} , { q_{0} , 0 → q_{0} }, {q_{0} , 1 → q_{0}}, {q_{0} , 1 → q_{1}} . Hence δ (q_{0}, 0011) = q_{1}
{q_{0} , 0 → q_{0}} , { q_{0} , 0 → q_{0} }, {q_{0} , 1 → q_{1}}, {q_{1} , 1 → q_{2}} . Hence δ (q_{0}, 0011) = q_{2}
Hence δ (q_{0}, 0011) = {q_{0}, q_{1}, q_{2}}
Question 49 
If L_{1} = {a^{n}n≥0} and L_{2} = {b^{n}n≥0}, consider

(I) L_{1}·L_{2} is a regular language
(II) L_{1}·L_{2} = {a^{n}b^{n}n≥0}
Which one of the following is CORRECT?
A  Only (I) 
B  Only (II) 
C  Both (I) and (II) 
D  Neither (I) nor (II) 
Since L_{1} and L_{2} both are regular languages and regular languages are closed under concatenation. So their concatenation (i.e., L_{1}⋅ L_{2}) must also be a regular language.
So, L_{1}⋅L_{2} = { a^{n}b^{n}  n ≥ 0}
Hence, statement (i) is True but statement (ii) is False.
Question 50 
Let A≤_{m}B denotes that language A is mapping reducible (also known as manytoone reducible) to language B. Which one of the following is FALSE?
A  If A≤_{m} B and B is recursive then A is recursive. 
B  If A≤_{m} Band A is undecidable then B is undecidable. 
C  If A≤_{m} Band B is recursively enumerable then A is recursively enumerable. 
D  If A≤_{m} B and B is not recursively enumerable then A is not recursively enumerable. 
Rule 1: If B is recursive then A is recursive.
Rule 2: If B is recursively enumerable then A is recursively enumerable.
Rule 3: If A is not recursively enumerable then B is not recursively enumerable.
Rule 4: If A is undecidable then B is undecidable.
Other than these rules, all conclusion are false.