TheoryofComputation
Question 1 
If L is a regular language over Σ = {a,b}, which one of the following languages is NOT regular?
Suffix (L) = {y ∈ Σ* such that xy ∈ L}  
{ww^{R} │w ∈ L}  
Prefix (L) = {x ∈ Σ*│∃y ∈ Σ* such that xy ∈ L}  
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?
3  
9  
5  
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 
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?
S2 and S3  
S3 and S4  
S1 and S4  
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?
{ww^{R} w ∈ {a,b}*}  
{wa^{n}w^{R}b^{n} w ∈ {a,b}*, n ≥ 0}  
{a^{n}b^{i}  i ∈ {n, 3n, 5n}, n ≥ 0}  
{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 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?
k ≥ 2^{n}
 
k ≥ n
 
k ≤ n^{2}  
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 6 
closed under complementation.
 
closed under intersection.
 
a subset of the set of all recursive languages.
 
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 7 
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 ______.
2  
3  
4  
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 8 
Consider the following languages:

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?
I and IV only  
I and II only
 
II and III only  
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 9 
Consider the following problems. L(G) denotes the language generated by a grammar G. L(M) denotes the language accepted by a machine M.

(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?
Only I and II are undecidable
 
Only III is undecidable  
Only II and IV are undecidable  
Only I, II and III are undecidable

I, II and III is undecidable.
Question 10 
Consider the following contextfree grammar over the alphabet Σ = {a, b, c} with S as the start symbol:

S → abScT  abcT
T → bT  b
Which one of the following represents the language generated by the above grammar?
{(ab)^{n} (cb)^{n}│n ≥ 1}  
{(ab)^{n} cb^{(m1 )} cb^{(m2 )}…cb^{(mn )}│n,m_{1},m_{2},…,m_{n} ≥ 1}  
{(ab)^{n} (cb^{m})^{n}│m,n ≥ 1}  
{(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 11 
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 _________.
4  
5  
6  
7 
After converting the NFA into DFA:
After converting the NFA into DFA:
Question 12 
If G is a grammar with productions
where S is the start variable, then which one of the following strings is not generated by G?
abab  
aaab  
abbaa  
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 13 
Consider the contextfree grammars over the alphabet {a, b, c} given below. S and T are nonterminals.

G_{1}: S → aSbT, T → cTϵ
G_{2}: S → bSaT, T → cTϵ
The language L(G_{1}) ∩ L(G_{2}) is
Finite  
Not finite but regular  
ContextFree but not regular  
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 14 
Consider the following languages over the alphabet Σ = {a, b, c}.
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}
I only  
II only  
I and II  
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 15 
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:
f is computable if and only if L_{f} is recursive.  
f is computable if and only if L_{f} is recursively enumerable.  
If f is computable then L_{f} is recursive, but not conversely.  
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 16 
Let L_{1}, L_{2} be any two contextfree languages and R be any regular language. Then which of the following is/are CORRECT?
I, II and IV only  
I and III only  
II and IV only  
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 17 
Identify the language generated by the following grammar, where S is the start variable.
S → XY X → aXa Y → aYbϵ
{a^{m} b^{n} │ m ≥ n, n > 0}  
{a^{m} b^{n} │ m ≥ n, n ≥ 0}  
{a^{m} b^{n} │ m > n, n ≥ 0}  
{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 18 
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 _________.
8  
9  
10  
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 19 
∅  
{q_{0},q_{1},q_{3}}  
{q_{0},q_{1},q_{2}}  
{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 20 
Consider the following languages:

L_{1} = {a^{p}│p is a prime number}
L_{2} = {a^{n} b^{m} c^{2m}  n ≥ 0, m ≥ 0}
L_{3} = {a^{n} b^{n} c^{2n} │ n ≥ 0}
L_{4} = {a^{n} b^{n} │ n ≥ 1}
Which of the following are CORRECT?

I. L_{1} is contextfree but not regular.
II. L_{2} is not contextfree.
III. L_{3} is not contextfree but recursive.
IV. L_{4} is deterministic contextfree.
I, II and IV only  
II and III only  
I and IV only  
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 21 
Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by a context free grammar G. Let L(M) be the language accepted by a Turing machine M.
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)?
I and IV only  
II and III only  
II, III and IV only  
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 22 
Which of the following languages is generated by the given grammar?
{a^{n}b^{m} n,m ≥ 0}  
{w ∈ {a,b}*  w has equal number of a’s and b’s}  
{a^{n} n ≥ 0}∪{b^{n} n ≥ 0}∪{a^{n} b(sup>nn ≥ 0}  
{a,b}* 
Question 23 
Which of the following decision problems are undecidable?

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_{1} and G_{2}, is L(G_{1}) = L(G_{2})?
IV. Given a TM M, is L(M) = Φ?
I and IV only  
II and III only  
III and IV only  
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 24 
Which one of the following regular expressions represents the language: the set of all binary strings having two consecutive 0s and two consecutive 1s?
(0 + 1)* 0011(0 + 1)* + (0 + 1)* 1100(0 + 1)*  
(0 + 1)* (00(0 + 1)* 11 + 11(0 + 1)* 00)(0 + 1)*  
(0 + 1)* 00(0 + 1)* + (0 + 1)* 11(0 + 1)*  
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 25 
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^{m} b^{n}│m > 0 or n > 0} and {a^{m} b^{n} m > 0 and n > 0}  
{a^{m} b^{n}│m > 0 and n > 0} and {a^{m} b^{n} m > 0 or n≥0}  
{a^{m} b^{n}│m≥0 or n > 0} and {a^{m} b^{n} m > 0 and n > 0}  
{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 26 
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?
L = {a^{n} b^{n}│n ≥ 0} and is not accepted by any ﬁnite automata  
L = {a^{n} n≥0} ∪ {a^{n}b^{n}n ≥ 0} and is not accepted by any deterministic PDA  
L is not accepted by any Turing machine that halts on every input  
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 27 
W can be recursively enumerable and Z is recursive.  
W can be recursive and Z is recursively enumerable.  
W is not recursively enumerable and Z is recursive.  
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 28 
The number of states in the minimum sized DFA that accepts the language deﬁned by the regular expression
2  
3  
4  
5 
So, the DFA has two states.
Question 29 
Language L_{1} is deﬁned by the grammar: S_{1} → aS_{1}bε
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?
Both P and Q are true  
P is true and Q is false  
P is false and Q is true  
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 30 
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?
I only  
I and III only  
I and IV only  
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 31 
Consider the following two statements:

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 isCORRECT?
Only I is true  
Only II is true  
Both I and II are true  
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 32 
Consider the following languages:

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 isTRUE?
Both L_{1} and L_{2} are contextfree.  
L_{1} is contextfree while L_{2} is not contextfree.  
L_{2} is contextfree while L_{1} is not contextfree.  
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 33 
Consider the following languages.

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?
L_{1} is recursive and L_{2}, L_{3} are not recursive  
L_{2} is recursive and L_{1}, L_{3} are not recursive  
L_{1}, L_{2} are recursive and L_{3} is not recursive  
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 34 
A student wrote two contextfree grammars G1 and G2 for generating a single Clike array declaration. The dimension of the array is at least one. For example,

int a[10][3];
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?
Both G1 and G2  
Only G1  
Only G2  
Neither G1 nor G2 
Question 35 
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?
I only  
III only  
III and IV only  
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 36 
1  
2  
3  
4 
Question 37 
10110  
10010  
01010  
01001 
Question 38 
Q_{1} is in NP, Q_{2} in NP hard
 
Q_{1} is in NP, Q_{2} is NP hard  
Both Q_{1} and Q_{2} are in NP
 
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 39 
Only II  
Only III  
Only I and II  
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 40 
L_{1} and L_{3} only
 
L_{2} only
 
L_{2} and L_{3} only
 
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 41 
3  
4  
5  
6 
No. of states in minimal DFA is 3.
Question 42 
10(0* + (10*)* 1  
10(0* + (10)*)* 1  
1(0 + 10)* 1  
10(0 + 10)* 1 + 110(0 + 10)* 1 
From the given diagram we can write,
X_{0} = 1(0+10)* 1
Question 43 
4  
5  
6  
8 
So, 5 states are there.
Question 44 
II only  
III only  
I and IV only  
I only 
L_{1} ≤ pL_{2}
If L_{4} ∈ P then L_{2} ∈ P hence L_{1} ∈ P, hence option C.
Question 45 
L_{1} and L_{2} only  
L_{1} and L_{3} only  
L_{2} and L_{3} only  
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 comparision 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 46 
The language L={a^{n} b^{n}│n≥0} is regular.  
The language L={a^{n}│n is prime} is regular.  
The language L={w│w has 3k+1b's for some k∈N with Σ={a,b} } is regular.  
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 47 
{q_{0},q_{1},q_{2} }  
{q_{0},q_{1} }  
{q_{0},q_{1},q_{2},q_{3} }  
{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 48 
Only (I)  
Only (II)  
Both (I) and (II)  
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 49 
If A≤_{m} B and B is recursive then A is recursive.  
If A≤_{m} Band A is undecidable then B is undecidable.  
If A≤_{m} Band B is recursively enumerable then A is recursively enumerable.  
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.
Question 50 
decidable and recursively enumerable  
undecidable but recursively enumerable  
undecidable and not recursively enumerable  
decidable but not recursively enumerable 
Now, since total number of strings of length 2014 is finite, so M1 will run the encoding of M for the string of length 2014 and if the M accept the string then M1 will halt in ACCEPT state. But if M goes for infinte loop for every string of length 2014, then M1 also will go into infinite loop. Hence language L is recursively enumerable but not recursive, as in case of rejectance halting is not guaranteed.
Question 51 
L_{1} is regular but not L_{2}  
L_{2} is regular but not L_{1}  
Both L_{1} and L_{2} are regular  
Neither nor L_{1} are L_{2} regular 
{Number of occurrences of (110)} ≥ {Number of occurrences of (011)}
Lets analyse the language, consider a string in which occurrence of (110) is more than one.
The following possibilities are: {1100110, 1101110, 110110, ….}
Please observe whenever strings start with “11” then in every situation whatever comes after “11” the string will never violate the condition. So strings of the form 11(0+1)* will always satisfy the condition.
Consider a string in which occurrence of (011) is more than one.
The following possibilities are: {011011, 0111011, 0110011, ….}
In the following possibilities please observe that number of occurrence “011” is two but number of occurrence of (110) is one, which violate the conditions.
If we add “0” in every string mentioned above, i.e. {0110110, 01110110, 01100110, ….} Now, observe that number of occurrence “011” and the number of occurrence of (110) both are equal, which satisfies the conditions.
With these analysis, we can make the DFA , which is mentioned below.
But language L_{2} requires infinite comparison to count the occurrences of (000’s) and (111’s), hence it is not regular.
Question 52 
3  
4  
5  
6 
{ϵ, a, b, aa, ab, ba, bb}
Let’s check all the string of length 3.
The given regular expression generates {aaa, aab, aba, abb, baa, bba, bbb}
But it doesn’t generate the string “bab”, hence the shortest string not generated by regular expression has length 3 (string “bab”).
Question 53 
Both 2^{Σ*} and Σ* are countable  
2^{Σ*} is countable and Σ* is uncountable  
2^{Σ*} is uncountable and Σ* is countable  
Both 2^{Σ*} and Σ* are uncountable 
Since we can enumerate all the strings of Σ*, hence Σ* is countable (countable infinite).
While 2^{Σ*} is uncountable, it has been already proved by using Diagonalization method.
Question 54 
Deciding if a given contextfree grammar is ambiguous.  
Deciding if a given string is generated by a given contextfree grammar.  
Deciding if the language generated by a given contextfree grammar is empty.  
Deciding if the language generated by a given contextfree grammar is finite. 
We have a membership algorithm which decides that whether a given string is generated by a given contextfree grammar. Similarly, the problems, whether the language generated by a given contextfree grammar is empty and the language generated by a given contextfree grammar is finite are decidable.
Question 55 
NPComplete.  
solvable in polynomial time by reduction to directed graph reachability.  
solvable in constant time since any input instance is satisfiable.  
NPhard, but not NPcomplete. 
Question 56 
None of the languages  
Only L_{1}  
Only L_{1} and L_{2}  
All the three languages 
But in L_{3}, we cannot make DPDA for it, as we cannot locate the middle of string, so DPDA for L_{3} is not possible. It can be accepted by NPDA only, so L_{3} is CFL but not DCFL.
Question 57 
Suppose you want to move from 0 to 100 on the number line. In each step, you either move right by a unit distance or you take a shortcut. A shortcut is simply a prespecified pair of integers i, j with i < j. Given a shortcut i, j if you are at position i on the number line, you may directly move to j. Suppose T(k) denotes the smallest number of steps needed to move from k to 100. Suppose further that there is at most 1 shortcut involving any number, and in particular from 9 there is a shortcut to 15. Let y and z be such that T(9) = 1 + min(T(y),T(z)). Then the value of the product yz is _____.
150  
151  
152  
153 
Now, it is given that
T(9) = 1 + min(T(y),T(z))
where,
T(y) = steps from y to 100
T(z) = steps from z to 100
where y and z are two possible values that can be reached from 9.
One number that can be reached from 9 is 10. Another no. is 15, the shortcut path from 9, as given in the question.
∴ The value of 'y' and 'z' are 10 and 15.
So, y × z = 10 × 15 = 150
Question 58 
1 and 4 only  
1 and 3 only  
2 only  
3 only 
Turing recognizable means recursively enumerable languages which is closed under UNION but they are not closed under complementation, so statement 2 is false.
Turing decidable means recursive languages and they are closed under Intersection and complementation.
Turing recognizable means recursively enumerable languages which is closed under UNION and INTERSECTION.
Question 59 
1, 2 and 3  
1 and 2 only  
2 and 3 only  
1 and 3 only 
1. Detecting cycle in a graph using DFS takes O(V+E)=O(V^{2})
Here, for complete graph E<= V^{2}. So, It runs in polynomial time.
2. Every Pproblem is NP because P subset of NP (P ⊂ NP)
3. NP – complete ∈ NP.
Hence, NPcomplete can be solved in nondeterministic polynomial time.
Question 60 
1 and 3 only  
2 and 4 only  
2 and 3 only  
3 and 4 only 
The regular expression corresponding to the given FA is
Hence we have regular expression: (11*0 +0) (0+1)*
Since we have (0+1)* at the end so if we write 0*1* after this it will not have any effect, the reason is whenever string ends with the terminals other than 1*0* there we can assume 1*0* as epsilon.
So it is equivalent to (11*0 +0) (0+1)*0*1*
The given DFA can be minimised, since the nonfinal states are equivalent and can be merged and the min DFA will have two states which is given below:
Hence statement 3 is false.
Since DFA accept string “0” whose length is one, so the statement “A accepts all strings over {0, 1} of length at least 2” is false statement.
Question 61 
3 only  
3 and 4 only  
1, 2 and 3 only  
2 and 3 only 
Completeness problem for context free language is undecidable, so 2 is undecidable.
Whether language generated by a Turing machine is regular is also undecidable, so 3 is undecidable.
Language accepted by an NFA and by a DFA is equivalent is decidable, so 4 is decidable.
Question 62 
∅  
{ε}  
a*  
{a ,ε} 
Hence the complement of language is: {a* − a^{+}} = {ϵ}
Question 63 
1, 2, 3, 4  
1, 2  
2, 3, 4  
3, 4 
Context free languages are not closed under complement operation, so compliment of CFL may or may not be CFL. Hence statement 2 is also undecidable.
Complement of Regular languages is also regular. Since a DFA that accepts the complement of L, i.e. ∑* – L, can be obtained by swapping its final states with its nonfinal states and viceversa. Hence it is decidable and if L is a regular language, then, L must also be regular.
Recursive languages are closed under complement, so if L is a recursive language then L must also be recursive, hence it is decidable.
Question 64 
1, 2 and 3  
2, 3 and 4  
1, 2 and 4  
1, 3 and 4 
String 1: abaabaaabaa : ab aa baa ab aa
String 2: aaaabaaaa : aa aa baa aa
String 3: baaaaabaaaab: baa aa ab aa aa b, because of the last “b” the string cannot belong to L*.
String 4: baaaaabaa : baa aa ab aa
Question 65 
From the state “00” it is clear that if another “0” comes then the string is going to be rejected, so from state “00” the transition with input “0” will lead to state “q”. So option A and B are eliminated.
Now option C has the self loop of “0” on state “10” which will accept any number of zeros (including greater than three zeros), hence the C option is also wrong. We left with only option D which is correct option.
Question 66 
P ∩ Q  
P – Q  
Σ* – P  
Σ* – Q 
since regular languages are closed under complementation
Question 67 
Deterministic finite automata (DFA) and Nondeterministic finite automata (NFA)  
Deterministic push down automata (DPDA) and Nondeterministic push down automata (NFDA)  
Deterministic singletape Turning machine and Nondeterministic single tape Turning machine  
Singletape Turning machine and multitape Turning machine 
Hence answer is (B)
Question 68 
k+1  
n+1  
2^{n+1}  
2^{k+1} 
So lets check of n = 2,
L = a_{2k}, k>0
Since k>0 than zero.
So L is the language accepting even no. of a's except 'ε'.
So DFA will be,
So, no. of states required is 2+1 = 3.
So for a^{nk}, (n+1) states will be required.
Question 69 
Push Down Automate (PDA) can be used to recognize L1 and L2  
L1 is a regular language  
All the three languages are context free  
Turing machines can be used to recognize all the languages 
L2: context free language
L3: context sensitive language
Question 70 
L2 – L1 is recursively enumerable
 
L1 – L3 is recursively enumerable
 
L2 ∩ L1 is recursively enumerable
 
L2 ∪ L1 is recursively enumerable 
L1 − L3 means L1 ∩ L3^{c} , since recursive enumerable is not closed under complement, so L3^{c} may or may not be recursive enumerable, hence we cannot say that L1 − L3 will always be recursive enumerable. So B is not necessarily true always.
L2 ∩ L1 means (Recursive enum ∩ Recursive) , as every recursive is recursive enum also, so it is equivalent to (Recursive enum ∩ Recursive enum) and recursive enum is closed under intersection, so L2∩ L1 must be recursive enumerable. Hence C is always true.
L2 ∪ L1 means (Recursive enum ∪ Recursive) , as every recursive is recursive enum also, so it is equivalent to (Recursive enum ∪ Recursive enum) and recursive enum is closed under union, so L2 ∪ L1 must be recursive enumerable. Hence D is always true.
Question 71 
(0 * 10 * 1)*
 
0 * (10 * 10*)*
 
0*(10 * 1*)*0*  
0 * 1(10 * 1)*10* 
Option A: (reg expr: (0*10*1)* ) doesn’t generate string such as { 110, 1100,....}
Option C: (reg expr: 0*(10*1*)*0* generate string such as {1, 111,....} which have odd number of 1’s.
Option D: (reg expr: 0*1(10*1)*10* doesn’t generate strings such as { 11101, 1111101, ….}.
Question 72 
Only L2 is context free  
Only L2 and L3 are context free  
Only L1 and L2 are context free  
All are context free 
Question 73 
n1  
n  
n+1  
2^{n1} 
Since L is set of all substrings of “w” (Substring of a string is obtained by deleting any prefix or any suffix from string), so if we consider “w” as “101” , then the substrings of w are { ϵ, 0, 1, 10, 01, 101}.
Since the string “101” is also its substring, so we require 4 states (i.e. for n length string, n+1 states are required) and the NFA would be:
Question 74 
All palindromes.  
All odd length palindromes.  
Strings that begin and end with the same symbol.  
All even length palindromes. 
Question 75 
The set of all strings containing the substring 00.
 
The set of all strings containing at most two 0’s.
 
The set of all strings containing at least two 0’s.
 
The set of all strings that begin and end with either 0 or 1.

Question 76 
There is unique minimal DFA for every regular language.  
Every NFA can be converted to an equivalent PDA.  
Complement of every contextfree language is recursive.
 
Every nondeterministic PDA can be converted to an equivalent deterministic PDA.

L= {ww^{r}  w ϵ {a,b}* } is a CFL but not DCFL, i.e. it can be recognized by NPDA but not by DPDA.
Question 77 
3  
4  
5  
6 
From the given FSM we can clearly see that, if we start from initial state (00) and follow the input “101” {highlighted in RED color},
{state 00, 1} > state “01” , output 0,
{state 01, 0} > state “10” , output 0,
{state 10, 1} > state “01” , output 1,
Hence it require an input string of minimum length 3, which will take the machine to the state A=0, B=1 with Output = 1.
Question 78 
Not recursive
 
Regular
 
Context free but not regular  
Recursively enumerable but not context free 
Clearly, L_{1} ∩ L_{2} is {a^{x}b^{x}  x ≥0}, which is CFL but not regular.
Question 79 
begin either with 0 or 1
 
end with 0
 
end with 00  
contain the substring 00 
Question 80 
It is not accepted by a Turing Machine
 
It is regular but not contextfree
 
It is contextfree but not regular
 
It is neither regular nor contextfree, but accepted by a Turing machine

Question 81 
I and II  
I and IV  
II and III
 
II and IV

Statement IV is also decidable, we need to check that whether the given grammar satisfies the CFG rule (TYPE 2 grammar productions).
But statements II and III are undecidable, as there doesn’t exist any algorithm to check whether a given contextfree language is regular and whether two pushdown automata accept the same language.
Question 82 
regular  
contextfree  
contextsensitive  
recursive 
If are recursively enumerable, then it implies that there exist a Turing Machine (lets say M2) which always HALT for the strings which is NOT in L(as L is complement of Since we can combine both Turing machines (M1 and M2) and obtain a new Turing Machine (say M3) which always HALT for the strings if it is in L and also if it is not in L. This implies that L must be recursive.
Question 83 
Every NFA can be converted to an equivalent DFA  
Every nondeterministic Turing machine can be converted to an equivalent deterministic Turing machine
 
Every regular language is also a contextfree language
 
Every subset of a recursively enumerable set is recursive 
Question 84 
Lets rename table Z (for sake of clarity)
And Table Y (same as given in question)
The product automata will have states { One1, One2, Two1, Two2} Where One1 is P , Two2 is R and One2 is Q and Two1 is S.
The transition table for Z × Y is given below:
NOTE: LAST TWO ROWS DOESN’T MATCH WITH OPTION A. BUT IF THE ASSUMPTION IN QUESTION SUCH AS STATE “11” IS P AND STATE “22” IS R, HOLDS, THEN THE ONLY OPTION MATCHES WITH PRODUCT AUTOMATA IS OPTION A, AS (FIRST ROW) , P (ON “a”) > S AND P (ON “b”) > R, IS THE ONLY OPTION MATCHING WITH OPTION A.
Question 85 
I, II, III and IV  
II, III and IV only  
I, III and IV only  
I, II and IV only 
A> BC
A> a // where “a” is any terminal and B, C are any variables.
When we draw the parse tree for the grammar in CNF, it will always have at most two childs in every step, so it always results binary tree.
But statement II is false, as if the language contains empty string then we cannot remove every epsilon production from the CFG, since at least one production (mainly S → ϵ) must be there in order to derive empty string in language.
Question 86 
E  P, F  R, G  Q, H  S  
E  R, F  P, G  S, H  Q  
E  R, F  P, G  Q, H  S
 
E  P, F  R, G  S, H  Q

F matches with P, Number of formal parameters in the declaration…. matches with {L={ a^{n} b^{m} c ^{n} d^{m}  m,n >=1}
Since, a^{n} b^{m} corresponds to formal parameter (if n=2 and m=1, and “a” is int type and “b”is float type, then it means (int,int,float)) and c^{n} d^{m} corresponds to actual parameter used in function.
Similarly other two can also be argued by their reasons, but with F matches with P and H matches with S implies that option C is the only correct option.
Question 87 
P2, Q1, R3, S4
 
P1, Q3, R2, S4
 
P1, Q2, R3, S4  
P3, Q2, R1, S4 
Similarly, The NFA represented by Q, has the form of > ϵ + 0X*0, where X is regular expression (10*1 + 00 ) {resolving the loop at middle state}. It matches with statement 2.
The NFA represented by R, has the form of > ϵ + 0X*1, where X is regular expression (10*1 + 01 ) {resolving the loop at middle state}. It matches with statement 3.
The NFA represented by S, accepts string “01” and then at final state (other than initial state) we have self loop of “0” , so we conclude that it must accept the string of the form of > ϵ + 0X* 10*, where X is regular expression (10*1 + 10 ) {resolving the loop at middle state}. It matches with statement 4.
Question 88 
I and IV only  
I and III only  
I only
 
IV only 
Statement II and III represent CFL, as it requires comparison between number of a’s and b’s.
Statement IV is also regular, and its regular expression is (a+b)* c (a+b)*.
Question 89 
m ≤ 2^{n}  
n ≤ m  
M has one accept state  
m = 2^{n} 
A state in a DFA is a proper suset of states of NFA of corresponding DFA.
→ No. of subsets with n elements = 2^{n}
→ m ≤ 2^{n}
Question 90 
Set of all strings that do not end with ab  
Set of all strings that begin with either an a or a b  
Set of all strings that do not contain the substring ab  
The set described by the regular expression b*aa*(ba)*b* 
Option B: abab is not accepted by given RE.
Option C: aba is accepted by given RE.
Option D: ab is not accepetd by RE and it belongs to b*aa*(ba)*b*.
Question 91 
L_{1} is not a CFL but L_{2} is  
L_{1} ∩ L_{2} = ∅ and L_{1} is nonregular  
L_{1} ∪ L_{2} is not a CFL but L_{2} is  
There is a 4state PDA that accepts L_{1}, but there is no DPDA that accepts L_{2} 
→ L_{1} ∩ L_{2} = ∅, True and also L1 is nonregular. Option B is true.
→ L_{1} ∪ L_{2} is not a CFL but L_{2} is CFL is closed under union. So option C is false.
→ Both L_{1} and L_{2} accepted by DPDA.
Question 92 
{0^{n} 10^{2n}  n ≥ 1}  
{0^{i} 10^{j} 10^{k}  i, j, k ≥ 0} ∪ {0^{n} 10^{2n}  n ≥ l}  
{0^{i} 10^{j}  i, j ≥ 0} ∪ {0^{n} 10^{2n}  n ≥ l}  
The set of all strings over {0, 1} containing at least two 0’s  
None of the above 
A → 0A  A0  1
B → 0B00  1
In this B → 0B00  1 which generates {0n 102n  n ≥0}
S → AA  B
A → 0A  A0  1
Which generates 0A0A → 00A0A → 00101.
Which is suitable for B and D option. D is not correct because 00 is not generated by the given grammar. So only option B is left. Nonterminal B i s generating the second part of B choice and AA is generating the first part.
{0^{i} 10^{j} 10^{k}  i, j, k ≥ 0} ∪ {0^{n} 10^{2n}  n ≥ 0}
Question 93 
L_{2} and L_{3} only  
L_{1} and L_{2} only  
L_{3} only  
L_{2} only 
L_{1} is limited to fixed range and L_{3} contains even number of 0's which is regular. No need to use more memory to implement L_{3}.
Question 94 
L_{1} = L_{2}  
L_{1} ⊂ L_{2}  
L_{1} ∩ L_{2}‘ = ∅  
L_{1} ∪ L_{2} ≠ L_{1}  
A and C 
L_{2} = (0=1)* 11(0+1)*
Both L_{1} and L_{2} are equal.
Option A is correct.
→ L_{1} ∩ L_{2}‘ = L_{1} ∩ L_{1}‘ = ∅ (option C also correct)
Question 95 
aabbaba  
aabaaba  
abababb  
aabbaab 
S→aA
S→aaAb
S→aabAab
S→aabbAaab
S→aabbaab
Question 96 
6 and 1  
6 and 2  
7 and 2  
4 and 2 
S→aA
S→aaAb
S→aabAab
S→aabbAaab
S→aabbaab
⇒ 6 steps are required
Only 1 parse tree is there.
Question 97 
Membership problem for CFGs.
 
Ambiguity problem for CFGs.
 
Finiteness problem for FSAs.  
Equivalence problem for FSAs.

Question 98 
Every subset of a regular set is regular.  
Every finite subset of a nonregular set is regular.
 
The union of two nonregular sets is not regular.
 
Infinite union of finite sets is regular. 
Every subset of regular set is regular, is false. For example L = {an bn  n ≥ 0} is subset of ∑* and L is CFL, whereas ∑* is regular. Hence, every subset of regular set need not be regular.
The union of two nonregular sets is not regular, is also a false statement.
For example, consider two CFL’s.
L = {a^{n} b^{n}  n ≥ 0} and its complement L^{c} = {a^{m} b^{n}  m ≠ n } U b*a*.
If we take UNION of L and L^{c} , we will get ∑*, which is regular. Hence the UNION of two nonregular set may or may not be regular.
The statement, Infinite union of finite sets is regular is also a false statement.
Question 99 
15 states  
11 states  
10 states  
9 states

Question 100 
not recursive.  
is recursive and is a deterministic CFL.
 
is a regular language.
 
is not a deterministic CFL but a CFL.

Question 101 
{ww^{R}w ∈ {0,1}^{+}}
 
{ww^{R}xx, w ∈ {0,1}^{+}}
 
{wxw^{R}x, w ∈ {0,1}^{+}}  
{xww^{R}x, w ∈ {0,1}^{+}}

0 (0+1)^{+} 0 + 1 (0+1)^{+} 1
Any string which begins and ends with same symbol, can be written in form of “wxw^{r}”
For example consider a string: 10010111, in this string “w=1” , “x= 001011” and w^{r} = 1. Hence any string which begins and ends with either “0” or with “1” can be written in form of “wxw^{r}” and L={wxw^{r}  x,w ϵ {0,1}^{+} } is a regular language.
Question 102 
b*ab*ab*ab*  
(a+b)*
 
b*a(a+b)*  
b*ab*ab* 
Clearly we can see that the regular expression for DFA is “ b*a (a+b)* ”.
Question 103 
1  
2  
3  
4 
Question 104 
All strings of x and y  
All strings of x and y which have either even number of x and even number of y or odd number or x and odd number of y  
All strings of x and y which have equal number of x and y  
All strings of x and y with either even number of x and odd number of y or odd number of x and even number of y 
Question 105 
(i), (ii), and (iii)  
(ii), (v), and (vi)  
(ii), (iii), and (iv)  
(i), (iii), and (iv) 
S → xB
S → xxBB
S → xxyB
S → xxyyS
S → xxyyxB
S → xxyyxy
(iii) xyxy
S → xB
S → xyS
S → xyxB
S → xyxy
(iv) yxxy
S → yA
S → yxS
S → yxxB
S → yxxy
Question 106 
G_{1} is contextfree but not regular and G_{2} is regular  
G_{2} is contextfree but not regular and G_{1} is regular  
Both G_{1} and G_{2} are regular  
Both G_{1} and G_{2} are contextfree but neither of them is regular 
Similarly, in right linear grammar, nonterminal appears at the right most position.
Here we can write a right linear grammar for G_{1} as
S → w(E
E → id)S
S → o
(wwhile, oother)
So, L(G_{1}) is regular.
Now for G_{2} also we can write a right linear grammar:
S → w(E
E → id)S
E → id+E
E → id*E
S → o
making its language regular.
So, both G_{1} and G_{2} have an equivalent regular grammar. But given in the question both these grammars are neither right linear nor left linear and hence not a regular grammar. So, (D) must be the answer.
Question 107 
Question 108 
But option (B), (C), (D) accepts aba, which do not contain aa or bb as substring.
Hence, (A) is correct.
Question 109 
(C) It is not accepting 'abb' which is in language.
(D) It is not accepting 'aa' and 'bb' which is in language.
Question 110 
(a(ba)* + b(ab)*)(a + b)^{+}  
(a(ba)* + b(ab)*)*(a + b)*  
(a(ba)* (a + bb) + b(ab)*(b + aa))(a + b)*  
(a(ba)* (a + bb) + b(ab)*(b + aa))(a + b)^{+} 
Having NFA:
Equivalent DFA:
Question 111 
L is recursively enumerable, but not recursive  
L is recursive, but not contextfree
 
L is contextfree, but not regular  
L is regular

L_{2} = {s ∈ (0 + 1)*  d(s) mod7 = 4}, we can construct the DFA for this which will have 7 states (remainders 0,1,2,3,4,5,6)
Since L_{1} and L_{2} have DFAs, hence they are regular. So the resulting Language.
L = L_{1} ∩ L_{2} (compliment) must be regular (by closure properties, INTERSECTION of two regular languages is a regular language).
Question 112 
L = {s ∈ (0+1)*  n_{0}(s) is a 3digit prime}  
L = {s ∈ (0+1)*  for every prefix s' of s,n_{0}(s')  n_{1}(s') ≤ 2}  
L = {s ∈ (0+1)* n_{0}(s)  n_{1}(s) ≤ 4}
 
L = {s ∈ (0+1)*  n_{0}(s) mod 7 = n_{1}(s) mod 5 = 0}

Option B: The DFA contains 6 states
State1: n_{0}(s')  n_{1}(s') = 0
State2: n_{0}(s')  n_{1}(s') = 1
State3: n_{0}(s')  n_{1}(s') = 2
State4: n_{0}(s')  n_{1}(s') = 1
State5: n_{0}(s')  n_{1}(s') = 2
State6: Dead state (trap state)
Hence it is regular.
Option D: Product automata concept is used to construct the DFA.
mod 7 has remainders {0,1,2,3,4,5,6} and mod 5 remainders {0,1,2,3,4}
So product automata will have 35 states.
But option C has infinite comparisons between number of 0’s and 1’s.
For ex: n_{0}(s) = 5 and n_{1}(s) = 1 then n_{0}(s)  n_{1}(s) = 4 and if n_{0}(s) = 15 and n_{1}(s) = 11 then n_{0}(s)  n_{1}(s) = 4.
Hence this is CFL.
Question 113 
L_{1} only  
L_{3} only
 
L_{1} and L_{2}
 
L_{2} and L_{3}

But for L_{2} and L_{3} PDA implementation is not possible. The reason is, in L_{2} there are two comparison at a time, first the number of 0’s in beginning should be equal to 1’s and then 0’s after 1’s must be less than or equal to number of 1’s. Suppose for initial 0’s and 1’s are matched by using stack then after matching stack will become empty and then we cannot determine the later 0’s are equal to or less than number of 1’s. Hence PDA implementation is not possible. Similarly L_{3} also has the similar reason.
Question 114 
max(l,m)+2  
l+m+2
 
l+m+3
 
max(l, m)+3

S → ACCB C → aCbϵ A → aAa B → Bbb
Assume a string: “aaabb” in this l=3 and m=2
The steps are:
Step1: S> AC
Step 2: S> aC By production: A> a
Step 3: S> aaCb By production: C> aCb
Step 4: S> aaaCbb By production: C> aCb
Step 5: S> aaabb By production: C> ϵ
Hence, it is clear that the correct option is A, i.e. max(l,m)+2
Question 115 
S→ACCB C→aCbab A→aAϵ B→Bbϵ  
S→aSSbab
 
S→ACCB C→aCbϵ A→aAϵ B→Bbϵ  
S→ACCB C→aCbϵ A→aAa B→Bbb 
Question 116 
3  
5  
8  
9 
i.e. it generates any string which can be obtained by repetition of three and five 1’s (means length 3, 6, 8, 9, 10, 11, …}
The DFA for the L = (111 + 11111)* is given below.
Question 117 
L_{1} ∩ L_{2} is a deterministic CFL  
L_{3} ∩ L_{1} is recursive  
L_{1} ∪ L_{2} is context free  
L_{1} ∩ L_{2} ∩ L_{3} is recursively enumerable 
L ∩ R = L ( i.e. L Intersection R is same type as L )
So L_{1} ∩ L_{2} is a deterministic CFL.
Option B is false, as L_{3} is recursive enumerable but not recursive, so intersection with L_{1} must be recursive enumerable, but may or may not be recursive.
Option C is true, as by closure property (R is a regular language and L is any language)
L U R = L ( i.e. L UNION R is same type as L )
So, L_{1} ∪ L_{2} is deterministic context free, hence it is also context free.
Option D is true, as L_{1} ∩ L_{2} is DCFL and DCFL ∩ L_{3} is equivalent to DCFL ∩ Recursive enumerable.
As every DCFL is recursive enumerable, so it is equivalent to Recursive enumerable ∩ Recursive enumerable. And recursive enumerable are closed under INTERSECTION so it will be recursive enumerable.
Question 118 
I only  
I and III only
 
II and III only
 
I, II and III

G doesn’t product all strings of equal number of a’s and b’s, for ex: string “aabb” doesn’t generate by grammar G.
The language generated by G can be accepted by DPDA. We can notice that grammar G generates, a’s and b’s in pair, i.e. either “ab” or “ba”, so the strings in language are {ab, ba, abab, abba, baba, ….}
We can design the DPDA:
Question 119 
The automaton accepts u and v but not w  
The automaton accepts each of u, v, and w  
The automaton rejects each of u, v, and w  
The automaton accepts u but rejects v and w 
where t is final state
(ii) v = bab
s is not final state
(iii) w = aabb
s is not final state
Question 120 
aaaa  
baba  
abba  
babaaabab 
Given string accepts all palindromes.
Option B → baba is not palindrome.
So, this is not accpeted by S.
Question 121 
(a + b)* a(a + b)b  
(abb)*  
(a + b)* a(a + b)* b(a + b)*  
(a + b)* 
Question 122 
{w ∈ (a + b)*  #a(w) is even) and {w ∈ (a + b)*  #a(w) is odd}  
{w ∈ (a + b)*  #a(w) is even) and {w ∈ (a + b)*  #b(w) is odd}  
{w ∈ (a + b)*  #a(w) = #b(w) and {w ∈ (a + b)*  #a(w) ≠ #b(w)}  
{ϵ}, {wa  w ∈ (a + b)* and {wb  w ∈ (a + b)*}

⇒ This results even number, no. of a's.
Question 123 
Every language has a regular superset  
Every language has a regular subset  
Every subset of a regular language is regular  
Every subset of a finite language is regular

Question 124 
{a^{n}b^{n}c^{n} ∣ n≥0}  
{a^{l}b^{m}c^{n} ∣ l≠m or m≠n}  
{a^{n}b^{n} ∣ n≥0}  
{a^{m}b^{n}∣ m,n≥0} 
To compare both conditions at the same time, we need a NPDA.
Question 125 
always regular  
never regular  
always a deterministic contextfree language  
always a contextfree language

Question 126 
{a^{l}b^{m}c^{n}  l = m = n}  
{a^{l}b^{m}c^{n}  l = m}  
{a^{l}b^{m}c^{n}  2l = m+n}  
{a^{l}b^{m}c^{n}  m=n} 
For every 'a' we put two X in stacks [at state S].
After that for every 'b' we pop out one X [reach to state t].
After that for every 'c' we pop out one X [reach to state u].
If all X are popped out then reached to final state f, means for every 'b' and 'c' there is 'a'. 'a' is followed by 'b' and 'b' is followed by 'c'.
Means,
Sum of no. of b's and no. of c's = twice of no. of a's
i.e., {a^{l}b^{m}c^{n}  2l = m+n}
Question 127 
((a + b)* b)*  
{a^{m}b^{n}  m ≤ n}  
{a^{m}b^{n}  m = n}  
a* b* 
((a + b)* b)* → It accepts string aa but given grammar does not accepts.
Option C&D:
→ abb accepted by given grammar but option C & D are not accepting.
Question 128 
S+ = S’ . y’ + S . x  
S+ =S. x . y’ + S’ . y . x’  
S+ =x . y’  
S+ =S’ . y + S . x’col 
From the table:
S' = S'y' + Sx
Question 129 
Both I and IV  
Only I  
Only IV  
Both II and III 
Half (L), Suffix (L) and Prefix (L) are regular languages.
Question 130 
(a + b)*  
{ϵ, a, ab, bab}  
(ab)*  
{a^{n}b^{n}  n ≥ 0} 
1) L should be regular due to demand of question.
2) L should be an infinite set of strings.
3) L should have more than one alphabet in its grammar, otherwise repeat(L) would be regular.
∴ (a + b)* is the perfect example to support the conclusions of last questions.
Question 131 
It computes 1's complement of the input number
 
It computes 2's complement of the input number
 
It increments the input number
 
It decrements the input number

Input = 1000
Output = 1111
The FSM, doesn't change until the first 1 come
I/p = 1000
1's complement = 0111
2's complement = 0111

1000 = I/p

It results 2's complement.
Question 132 
L_{1} is a deterministic CFL
 
L_{2} is a deterministic CFL
 
L_{3} is a CFL, but not a deterministic CFL
 
L_{3} is a deterministic CFL 
→ Given L_{1} is CFL but not DCFL.
→ Because, we can't predict where w ends and where it reverse is starts.
→ L_{2} = {w#w^{R}  w ∈ (0,1)*}
→ Given L_{2} is CFL and also DCFL.
→ The string w and w^{R} are separated by special symbol '#'.
→ L_{3} = {ww  w ∈ (0,1)*}
This is not even a CFL. This can be proved by using pumping lemma. So, L_{2} is DCFL. (✔️)
Question 133 
L_{1} ∩ L_{2} is a contextfree language  
L_{1} ∪ L_{2} is a contextfree language
 
L_{1} and L_{2} are contextfree languages
 
L_{1} ∩ L_{2} is a context sensitive language

CFL is not closed under Intersection.
L_{1} = {a^{n}b^{n}c^{m}  n>0 & m>0}
L_{2} = {a^{m}b^{n}c^{n}  n>0 & m>0}
L_{3} = L_{1} ∩ L_{2}
={a^{n}b^{n}c^{n}  n>0} It is not contextfree.
Question 134 
But, recursive enumerable languages are not closed under complementation.
If L_{1} is recursive, then L_{1}', is also recursive.
If L_{2} is recursive enumerable, then L_{2}', is not recursive enumerable language.
Question 135 
Let N_{f} and N_{p} denote the classes of languages accepted by nondeterministic finite automata and nondeterministic pushdown automata, respectively. Let D_{f} and D_{p} denote the classes of languages accepted by deterministic finite automata and deterministic pushdown automata, respectively. Which one of the following is TRUE?
D_{f} ⊂ N_{f} and D_{p} ⊂ N_{p}
 
D_{f} ⊂ N_{f} and D_{p} = N_{p}  
D_{f} = N_{f} and D_{p} = N_{p}
 
D_{f} = N_{f} and D_{p} ⊂ N_{p}

So D_{f} = N_{f}
NPDA can accept more languages than DPDA.
D_{p} ⊂ N_{p}
Question 136 
{w ∈ {a, b}*  every a in w is followed by exactly two b's}  
{w ∈ {a, b}* every a in w is followed by at least two b’}
 
{w ∈ {a, b}* w contains the substring 'abb'}
 
{w ∈ {a, b}* w does not contain 'aa' as a substring} 
Ex: abbbb, abbb...
Option B: It is True. If a string is to be accepted by given machine then it have atleast two b's.
Option C: It is false. Ex: abba. It contains 'abb' as a substring but not accepted by given machine.
Option D: It is false. Ex: abbab. It is not accepted by TM. It doesn't have 'aa' as a substring but not accepting.
Question 137 
P_{3} is decidable if P_{1} is reducible to P_{3}
 
P_{3} is undecidable if P_{3} is reducible to P_{2}  
P_{3} is undecidable if P_{2} is reducible to P_{3}  
P_{3} is decidable if P_{3} is reducible to P_{2}'s complement

Option B: If P_{3} is reducible to P_{2}, then P_{3} cannot be harder than P_{2}. But P_{2} being undecidable, this can't say P_{3} is undecidable.
Option C: If P_{2} is reducible to P_{3}, then P_{3} is atleast as hard as P_{2}. Since, P_{2} is undecidable. This means P_{3} is also undecidable.
Question 138 
It is necessarily regular but not necessarily contextfree.  
It is necessarily contextfree.  
It is necessarily nonregular.  
None of the above. 
Question 139 
It represents a finite set of finite strings.  
It represents an infinite set of finite strings.  
It represents a finite set of infinite strings.  
It represents an infinite set of infinite strings.

So, given regular expression represents an infinite set of finite strings.
Question 140 
regular  
contextfree but not regular  
contextfree but its complement is not contextfree  
not contextfree 
So, given language is regular.
Question 141 
None of these 
Question 142 
L1 = L2  
L1 ⊂ L2  
L2 ⊂ L1  
None of the above 
Y = X0 + Y0 + Z1
Z = X0 + Y0 + Z;
⇒ X = Z;
⇒ L1 = L2
Question 143 
Let P be a nondeterministic pushdown automaton (NPDA) with exactly one state, q, and exactly one symbol, Z, in its stack alphabet. State q is both the starting as well as the accepting state of the PDA. The stack is initialized with one Z before the start of the operation of the PDA. Let the input alphabet of the PDA be Σ. Let L(P) be the language accepted by the PDA by reading a string and reaching its accepting state. Let N(P) be the language accepted by the PDA by reading a string and emptying its stack. Which of the following statements is TRUE?
L(P) is necessarily Σ* but N(P) is not necessarily Σ*  
N(P) is necessarily Σ* but L(P) is not necessarily Σ*  
Both L(P) and N(P) are necessarily Σ*  
Neither L(P) nor N(P) are necessarily Σ*

Question 144 
2  
3  
4  
5 
The minimum string length is 2 [aa], so we require 3 states to construct DFA.
Question 145 
L is necessarily a regular language  
L is necessarily a contextfree language, but not necessarily a regular language  
L is necessarily a nonregular language  
None of the above 
Question 146 
id + id + id + id  
id + (id* (id * id))  
(id* (id * id)) + id  
((id * id + id) * id) 
Question 147 
5  
4  
3  
2 
Question 148 
E_{1} : A[i][j] and E_{2} : i = j;  
E_{1} : !A[i][j] and E_{2} : i = j + 1;  
E_{1}: !A[i][j] and E_{2} : i = j;  
E_{1} : A[i][j] and E_{2} : i = j + 1;

The first part of the code, is finding if there is any vertex which doesn't have any outgoing edge to any vertex coming after it in adjacency matrix. The smart part of the code is E_{2}, which makes rows slip when there is no edge from i to it, making it impossible for them to form a sink. This is done through
E_{1}: A[i][j]
and
E_{2}: i = j
E_{1} makes sure that there is no edge from i to j and i is a potential sink till A[i][j] becomes 1. If A[i][j] becomes 1, i can no longer be a sink. Similarly, all previous j can also not be a sink. Now, the next potential candidate for sink is j. So, in E_{2}, we must make i = j.
So, answer is (C).
Question 149 
(A[i][j] && !A[j][i])  
(!A[i][j] && A[j][i])  
(!A[i][j]   A[j][i])  
(A[i][j]   !A[j][i]) 
Now, the loop breaks when we found a potential sinkthat is a vertex which does not have any outgoing edge to any coming after it in adjacency matrix.
So, if the column in which this vertex comes is all 1's and the row is all 0's (except diagonal), this is the sink. Otherwise there is no sink in the graph. So, E_{3} is checking this condition. But in the code flag is used for storing the state that sink is present or not. And as per the usage of flag in code, by default sink is considered present.
So, the condition is E_{3} must make flag = 0, if the found i is not a sink. So, the condition should be
A[i][j]   !A[j][i]
So, option (D) is the answer.
Question 151 
>100 but finite  
∞  
3  
>3 and ≤100 
The distance between A and the nodes B, D, F respectively are:
t: 1 2 3
t + 1: 3 2 3
t + 2: 3 4 3
t + 3: 5 4 5
t + 4: 5 6 5
t + 5: 7 6 7
t + 6: 7 8 7
t + 7: 9 8 9
t + 8: 9 to 10
and this continues.
So, in every two steps they get incremented by 2.
So,
at t + 99, F is 101
at t + 100, F is 101.
Question 152 
divisible by 3 and 2
 
odd and even
 
even and odd
 
divisible by 2 and 3

For example 001 consists of even no. of zero's and odd no. of one's. It is not accepted by TM.
So, it is false.
Option C:
For example 110, contains even 1's and odd 0's but not accepted by TM.
So, it is false.
Option D:
For example 11000, where no. of 1's divisible by '2', and no. of zero's divisible by 3, but not accepted by TM.
So, it is false.
Option A:
It accepts all string where no. of 1's divisible by 3, and no. of zero's divisible by 2.
It is true.
Question 153 
regular
 
contextfree but not regular
 
context sensitive but not context free
 
type0 but not context sensitive

PUSH z_{0} into stack
PUSH K to stack of occurance of a
PUSH L to stack of occurance of b
POP K and L for the occurance of c
→ After POPno elements in the stack. So, this is context free language.
Note:
Regular:
R = {a^{n}  n ≥ 1}, Example.
CFL:
R = {a^{n}b^{m}  n,m ≥ 1}, Example.
Question 154 
Both S_{1} and S_{2} are true
 
S_{1} is true but S_{2} is not necessarily true
 
S_{2} is true but S_{1} is not necessarily true  
Neither is necessarily true

L_{1} = recursively enumerable language
L_{2} over Σ∪{#} as {w_{i}#w_{j}  w_{i}, w_{j} ∈ L_{1}, i < j}
S_{1} is True.
If L_{1} is recursive then L_{2} is also recursive. Because, to check w = w_{i}#w_{j} belongs to L_{2}, and we give w_{i} and w_{j} to the corresponding decider L_{1}, if both are to be accepted, then w∈L_{1} and not otherwise.
S_{2} is also True:
With the corresponding decider L_{2} we need to make decide L_{1}.
Question 155 
(a* + b* + c*)*  
(a*b*c*)*  
((ab)* + c*)*  
(a*b* + c*)* 
From option 'c' we cannot be able to create a without b. So option is not equivalent.
Question 156 
There exist contextfree languages such that all the contextfree grammars generating them are ambiguous  
An unambiguous context free grammar always has a unique parse tree for each string of the language generated by it  
Both deterministic and nondeterministic pushdown automata always accept the same set of languages  
A finite set of string from one alphabet is always a regular language

But nondeterministic ones can recognize all contextfree languages.
So, option C is false.
Question 157 
aaa  
aabab  
baaba  
bab 
Now, here transition ((s,a,t), (s,a)) implies reading input symbol 'a' in the state 's' we have to move 's' having any symbol on the top of stack ... epsilon here implies "anything on of Top of stack".
Now, observe the PDA carefully, it is saying that in the starting you have to push one 'a' for each of 'a' and 'b'. And in the end you have to pop one 'a' by one 'a' by one 'a' or one 'b'. Thus the count of a's and b's in first half of the string should be equal to second half of string. Now to move from first half to second half we are required one 'a', i.e., moving from s to f.
So, all odd strings in which 'a' is the middle element will be accpeted.
Thus in our question, option (B) is aabab having 'b' in the middle and thus can't be accepted.
Question 158 
{A→aB, A→bA, B→bA, B→aA, B→ε}  
{A→aA, A→bB, B→bB, B→aA, B→ε}  
{A→bB, A→aB, B→aA, B→bA, A→ε}  
{A→aA, A→bA, B→bB, B→aA, A→ε} 
Question 159 
L is recursive
 
L is recursively enumerable but not recursive  
L is not recursively enumerable
 
Whether L is recursive or not will be known after we find out if P = NP

P = NP (or) P != NP
→ If P=NP then L=(0+1)* which is recular, then it is recursive.
→ If P!=NP then L becomes ɸ which is also regular, then it is recursive.
So, finally L is recursive.
Question 160 
(1*0)*1*
 
0+(0+10)*
 
(0+1)*10(0+1)*  
None of the above

Option (B) and (C) doesn't generate 11.
Question 161 
L is necessarily finite
 
L is regular but not necessarily finite
 
L is context free but not necessarily regular  
L is recursive but not necessarily context free 
The give 'L' is recursive but not necessarily context free.
Question 162 
1  
5  
7  
8 
There are possible: 7 strings
Question 163 
G is not ambiguous
 
There exist x, y ∈ L(G) such that xy ∉ L(G)
 
There is a deterministic pushdown automaton that accepts L(G)  
We can find a deterministic finite state automaton that accepts L(G)

We can derive ϵ with more than one parse tree,
So ambiguous.
b) False
Let take x=aabb and y=ab then xy=aabbab we can produce it,
c) True
Because the language generated is no. of a's = no' of b's. So DPDA exist for this language.
d) Not possible.
Infinite memory needed to count 'a' for no. of 'b'.
Question 164 
L_{1} ∈ P and L_{2} is finite  
L_{1} ∈ NP and L_{2} ∈ P
 
L_{1} is undecidable and L_{2} is decidable
 
L_{1} is recursively enumerable and L_{2} is recursive 
Now if L_{2} is decidable then L_{1} should also be decidable. Hence, option (c) is wrong.
Question 165 
M does not halt on any string in (0+1)^{+}
 
M does not halt on any string in (00+1)*  
M halts on all strings ending in a 0
 
M halts on all strings ending in a 1

Try for any string, it will not Halt for any string other than ϵ. Hence, option (A) is correct.
Question 167 
L_{1} = {0,1}*  L
 
L_{1} = {0,1}*
 
L_{1} ⊆ L  
L_{1} = L

As in above NFA language,
L_{1} is {0,1}*.
Question 168 
Context free  
Regular  
Deterministic Context free  
Recursive 
Question 169 
Outputs the sum of the present and the previous bits of the input.  
Outputs 01 whenever the input sequence contains 11  
Outputs 00 whenever the input sequence contains 10  
None of the above 
(A,1) = (B, 01)
Previous input + Present input = 0+1 = 01
(B,0) = (A, 01)
Previous input + Present input = 1+0 = 01
(A,0) = (A, 00)
Previous input + Present input = 0+0 = 00
(A,1) = (B, 01)
Previous input + Present input = 0+1 = 01
(B,1) = (C, 10)
Previous input + Present input = 1+1 = 10
(C,1) = (C, 10)
Previous input + Present input = 1+1 = 10
Question 170 
2 states  
3 states  
4 states  
5 states 
Minimum no. of states that we require is "3".
Question 171 
The complement of a recursive language is recursive.  
The complement of a recursively enumerable language is recursively enumerable.  
The complement of a recursive language is either recursive or recursively enumerable.  
The complement of a contextfree language is contextfree. 
Question 172 
A context free language  
A context sensitive language  
A regular language  
Parsable fully only by a Turing machine 
Question 175 
S ⊂ T  
T ⊂ S  
S = T  
S ∩ T = ɸ 
Question 176 
L = 0^{+}  
L is regular but not 0^{+}  
L is context free but not regular  
L is not context free 
Question 177 
L must be {a^{n} n is odd}  
L must be {a^{n} n is even}  
L must be {a^{n}≥0}  
Either L must be {a^{n} n is odd}, or L must be {a^{n}  n is even} 
Question 178 
Both (P1) and (P2) are decidable  
Neither (P1) nor (P2) are decidable  
Only (P1) is decidable  
Only (P2) is decidable 
For P2, check if the CFG generates any string of length between n and 2n−1, where n is the pumping lemma constant. If So, L (CFG) is infinite, else finite. Finding the pumping lemma constant is not trivial. So both P1, P2 are decidable.
Question 179 
Theory Explanation is given below. 
L = (0+1)*  (0+1)* (00+11) (0+1)*
(b) i≤j as S→aSAb
There will be always for one a in left and minimum one b in right and A→bAX can generate any no. of b's including Null, if A is X then i=j and if A is generate any b then j>i. So the condition i≤j is true.
Question 180 
Theory Explanation is given below. 
(b)
Question 181 
n states  
n + 1 states  
n + 2 states  
None of the above 
DFA:
So, DFA requires (n+2) state.
NFA:
So, NFA requires (n+1) state.
So, final answer will be,
min(n+1, n+2)
= n+1
Question 182 
Union, intersection  
Union, Kleene closure  
Intersection, complement  
Complement, Kleene closure

By checking the options only option B is correct.
Question 183 
L_{D} = L_{E}  
L_{D} ⊃ L_{E}  
L_{E} = L_{D}  
None of the above 
Question 184 
L1 – L2 is not context free  
L1 ∩ L2 is context free  
~L1 is context free  
~L2 is regular  
Both A and C 
So L1  L2 = L1 ∩ (~L2)
And CFL is closed under regular intersection.
So, L1 ∩ (~L2) or L1  L2 is CFL.
So False.
(B) As we said that CFL is closed under regular intersection.
So True.
(C) CFL is not closed under complementation.
Hence False.
(D) Regular language is closed under complementation.
Hence True.
Question 185 
Ambiguous  
Unambiguous  
Information is not sufficient to decide whether it is ambiguous or unambiguous  
None of the above 
Question 186 
A ⊂ B  
B ⊂ A  
A and B are incomparable  
A = B 
Question 187 
The numbers 1, 2, 4, 8, ……………., 2^{n}, ………… written in binary  
The numbers 1, 2, 4, ………………., 2^{n}, …………..written in unary  
The set of binary string in which the number of zeros is the same as the number of ones  
The set {1, 101, 11011, 1110111, ………..} 
10, 100, 1000, 10000 .... = 10*
which is reguar and recognized by deterministic finite automata.
Question 188 
The nondeterministic finitestate automata are equivalent to deterministic finitestate automata.  
Nondeterministic Pushdown automata are equivalent to deterministic Push down automata.  
Nondeterministic Turing machines are equivalent to deterministic Pushdown automata.  
Both B and C 
C: Power (TM) > NPDA > DPDA.
Question 189 
110*(0 + 1)  
1 ( 0 + 1)* 101  
(10)* (01)* (00 + 11)*  
Both C and D 
C & D are not generate string 1101.
Question 190 
n  
n^{2}  
2^{n}  
Possible substrings are = {A, P, B, AP, PB, BA, APB}
Go through the options.
Option D:
n(n+1)/2 = 3(3+1)/2 = 6
Question 191 
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
2  
5  
8  
3 
Equivalent DFA:
Hence, 5 states.
Question 192 
Every finite subset of a nonregular set is regular  
Every subset of a regular set is regular  
Every finite subset of a regular set is regular  
The intersection of two regular sets is regular 
Question 193 
Set of all strings over Σ  
Set of all languages over Σ  
Set of all regular languages over Σ  
Set of all languages over Σ accepted by Turing machines 
Question 194 
0*(1+0)*  
0*1010*  
0*1*01  
0(10+1)* 
(B) generates 100 as substring.
(C) doesn't generate 1.
(D) answer.
Question 195 
Given a Turing machine M, a stings s and an integer k, M accepts s within k steps  
Equivalence of two given Turing machines  
Language accepted by a given finite state machine is not empty  
Language generated by a context free grammar is non empty 
In (A) the number of steps is restricted to a finite number 'k' and simulating a TM for 'k' steps is trivially decidable because we just go to step k and output the answer.
(B) Equivalence of two TM's is undecidable.
For options (C) and (D) we do have well defined algorithms making them decidable.
Question 196 
{w⊂w^{R}w ∈ {a,b}*}  
{ww^{R}w ∈ {a,b,c}*}  
{a^{n}b^{n}c^{n}n ≥ 0}  
{ww is a palindrome over {a,b,c}} 
(B) ww^{R}, is realized by NPDA because we can't find deterministically the center of palindrome string.
(C) {a^{n}b^{n}c^{n}  n ≥ 0} is CSL.
(D) {w  w is palindrome over {a,b,c}},
is realized by NPDA because we can't find deterministically the center of palindrome string.
Question 197 
(i) and (ii)  
(ii) and (iii)  
(i) and (iii)  
(iii) and (iv) 
In these two, we have any no. of 0's as well as null.
Question 198 
The Halting problem of Turing machines is undecidable.  
Determining whether a contextfree grammar is ambiguous is undecidbale.  
Given two arbitrary contextfree grammars G1 and G2 it is undecidable whether L(G1) = L(G2).  
Given two regular grammars G1 and G2 it is undecidable whether L(G1) = L(G2). 
1) Membership
2) Emtiness
3) Finiteness
4) Equivalence
5) Ambiguity
6) Regularity
7) Everything
8) Disjointness
All are decidable for Regular languages.
→ First 3 for CFL.
→ Only 1^{st} for CSL and REC.
→ None for RE.
Question 199 
L = {xx has an equal number of a's and b's } is regular  
L = {a^{n}b^{n}n≥1} is regular  
L = {xx has more a's and b's} is regular  
L = {a^{m}b^{n}m ≥ 1, n ≥ 1} is regular 
Here, m and n are independent.
So 'L' Is Regular.
Question 200 
L_{1}, L_{2}  
L_{1} ∩ L_{2}  
L_{1} ∩ R  
L_{1} ∪ L_{2} 
Question 201 
the set of all binary strings with unequal number of 0’s and 1’s  
the set of all binary strings including the null string
 
the set of all binary strings with exactly one more 0’s than the number of 1’s or one more 1 than the number of 0’s
 
None of the above 
Question 202 
the sentence if a then if b then c:=d  
the left most and right most derivations of the sentence if a then if b then c:=d give rise top different parse trees  
the sentence if a then if b then c:=d else c:=f has more than two parse trees  
the sentence if a then if then c:=d else c:=f has two parse trees 
"if a then if b then c:=d else c:=f".
Parse tree 1:
Parse tree 2:
Question 203 
4  
3  
2  
1 
Question 204 
(L ∪ D)^{+}  
L(L ∪ D)*  
(L⋅D)*  
L⋅(L⋅D)* 
L(L⋅D)*
Question 205 
Context free  
Regular  
Context sensitive  
LR(k) 
Because LHS must be single nonterminal symbol.
S ∝→ b [violates CSG]
→ Length of RHS production must be atleast same as that of LHS.
Extra information is added to the state by redefining iteams to include a terminal symbol as second component in this type of grammar.
Ex: [A → αβa]
A → αβ is a production, a is a terminal (or) right end marker $, such an object is called LR(k).
So, answer is (D) i.e., LR(k).
Question 206 
I only  
I and II  
II and III  
II only 
Question 207 
01  
10  
101  
110 
If A is the start state, shortest sequence is 10 'or' 00 to reach C.
If B is the start state, shortest sequence is 0 to reach C.
If C is the start state, shortest sequence is 10 or 00 to reach C.
If D is the start state, shortest sequence is 0 to reach C.
∴ (B) is correct.
Question 208 
regular, regular  
not regular, regular  
regular, not regular  
not regular, no regular 
Question 209 
Regular grammar to context free grammar  
Nondeterministic FSA to deterministic FSA  
Nondeterministic PDA to deterministic PDA  
Nondeterministic Turing machine to deterministic Turing machine 
Question 210 
Syntax of ifthenelse statements  
Syntax of recursive procedures  
Whether a variable has been declared before its use  
Variable names of arbitrary length 
Syntactic rules not checking the meaningful things such as if a variable is declared before it use (or) not.
Like this, things are handled by semantic analysis phase.
Question 211 
L=0*1* 
L contains all binary strings where a 1 is not followed by a 0.
Question 212 
True  
False 
Question 214 
Hamiltonian circuit problem  
The 0/1 Knapsack problem  
Finding biconnected components of a graph  
The graph colouring problem 
Question 215 
FOLLOW(A) and FOLLOW (A) may be different.  
FOLLOW(A) and FOLLOW (A) are always the same.  
All the three sets are identical.  
All the three sets are different.
 
Both A and B 
Question 216 
r(*) = r*  
(r*s*) = (r+s)*  
(r+s)* = r* + s*  
r*s* = r* + s* 
(B) RHS generates Σ* while LHS can't generate strings where r comes after s like sr, srr, etc.
LHS ⊂ RHS.
(C) LHS generates Σ* while RHS can't generate strings where r comes after an s.
RHS ⊂ LHS.
(D) LHS contains all strings where after an s, no r comes. RHS contains all strings of either r or s but no combination of them.
So, RHS ⊂ LHS.
Question 217 
2l  
2l + 1  
2l  1  
l 
2l  1
For GNF, it is
l
Question 218 
closed under union  
closed under complementation  
closed under intersection  
closed under Kleene closure  
Both A and D 
Question 219 
M_{1} is nondeterministic finite automaton  
M_{1} is a nondeterministic PDA  
M_{1} is a nondeterministic Turing machine  
For no machine M_{1} use the above statement true  
Both A and C 
For every NPDA there does not exist a deterministic PDA.
Every nondeterministic TM has an equivalent deterministic TM.
Question 220 
Only S1 is correct  
Only S2 is correct  
Both S1 and S2 are correct  
None of S1 and S2 is correct 
For S2, DFA is not possible which is not regular.
Question 221 
If a language is context free it can always be accepted by a deterministic pushdown automaton  
The union of two context free languages is context free  
The intersection of two context free languages is context free  
The complement of a context free language is context free 
Question 222 
N^{2}  
2^{N}  
2N  
N! 
If NFA have two states {1}{2} = 2
Then DFA may contain {ϕ}{1}{2}{1,2} = 4 = 2^{2} = 2^{N}
Question 223 
8  
14  
15  
48 
Same as b's divisible by 8 contains 8 state.
Total no. of states is = 8 * 6 = 48
Question 224 
Only L1 and L2  
Only L2, L3 and L4  
Only L3 and L4  
Only L3 
⇒ This is not regular language. We can't be able to identify where the 'w' will ends and where the next 'w' starts.
L2 = {ww^{R}w∈{a,b}*, w^{R} is the reverse of w}
⇒ This also not a regular language. We can't identify where 'w' ends.
L4 = {0^{i2}i is an integer}
= {0^{i}*0^{i}i is an integer}
⇒ This is also not a regular language. We can't identify where 0^{i} ends.
L3 = {0^{2i}i is an integer}
⇒ This is regular. We can easily find whether a string is even or not.
Question 225 
X is decidable  
X is undecidable but partially decidable  
X is undecidable and not even partially decidable  
X is not a decision problem 
Question 227 
Theory Explanation is given below. 
Question 229 
L(s) ⊆ L(r) and L(s) ⊆ L(t)  
L(r) ⊆ L(s) and L(s) ⊆ L(t)  
L(s) ⊆ L(t) and L(s) ⊆ L(r)  
L(t) ⊆ L(s) and L(s) ⊆ L(r)  
None of the above  
A and C 
L(s) ⊆ L(t), because 't' generates all the strings which 's' generates but 't' also generates '0' which 's' do not generates.
Question 230 
It could be undecidable  
It is Turingmachine recognizable  
It is a contextsensitive language  
It is a regular language  
None of the above  
B, C and D 
And, regular language ⊂ contextfree ⊂ contextsensitive ⊂ Turing recognizable, would imply that regular language is the strongest answer.
Question 231 
A proper superset of context free languages.  
Always recognizable by pushdown automata.  
Also called type ∅ languages.  
Recognizable by Turing machines.  
Both (A) and (D) 
B) False.
C) False, because Type0 language are actually recursively enumerable languages and not recursive languages.
D) True.
Question 232 
An arbitrary Turing machine halts after 100 steps.  
A Turing machine prints a specific letter.  
A Turing machine computes the products of two numbers.  
None of the above.  
Both (B) and (C). 
B) A TM prints a specific letter is undecidable.
C) A TM computes the products of two numbers is undecidable. Eventhough we can design a TM for calculation product of 2 numbers but here it is asking whether given TM computes product of 2 numbers, so the behaviour of TM unknown hence, undecidable.
Question 233 
R_{1} ∩ R_{2} is not regular.  
R_{1} ∪ R_{2} is regular.  
Σ* − R_{1} is regular.  
R_{1}* is not regular.  
Both (B) and (C). 
1) Intersection
2) Union
3) Complement
4) Kleenclosure
Σ*  R_{1} is the complement of R_{1}.
Hence, (B) and (C) are true.
Question 234 
Union  
Intersection  
Concatenation  
Complementation  
Both A and C 
Question 235 
Membership problem in contextfree languages.  
Whether a given contextfree language is regular.  
Whether a finite state automation halts on all inputs.  
Membership problem for type 0 languages.  
Both (A) and (C). 
→ Option C is also decidable because this is a trivial problem as finite state automaton is a specific case of halting turing machine with limited power.
Question 236 
True  
False 
Question 237 
True  
False 
Question 238 
True  
False 
Question 239 
True  
False 
Question 240 
True  
False 
Question 241 
The grammar contains useless nonterminals.  
It produces more than one parse tree for some sentence.  
Some production has two non terminals side by side on the righthand side.  
None of the above. 
Question 242 
Regular language.  
Contextfree language.  
Contextsenstive language.  
None of the above. 
Some of the features are:
1) Variable declared before use.
2) Matching formal and actual parameters of functions.