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 
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?
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 Σ 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 ______.
120  
136  
125  
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?
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 7 
The set of all recursively enumerable languages is
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 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 ______.
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 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?
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 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?
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 11 
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 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 _________.
4  
5  
6  
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?
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 14 
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 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}
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 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:
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 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?
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 18 
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 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 _________.
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 20 
Let δ denote the transition function and denote the extended transition function of the εNFA whose transition table is given below:
Then is
∅  
{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 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.}
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 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)?
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 23 
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 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) = Φ?
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 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?
(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 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^{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 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?
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 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?
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 29 
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 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?
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 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?
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 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?
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 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?
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 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?
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 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?
Both G1 and G2  
Only G1  
Only G2  
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?
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 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 __________.
1  
2  
3  
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:
10110  
10010  
01010  
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?
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 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?
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 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}
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 42 
The number of states in the minimal deterministic finite automaton corresponding to the regular expression (0 + 1) * (10) is __________.
3  
4  
5  
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}?
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 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)?
4  
5  
6  
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
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 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}
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 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?
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 48 
Consider the finite automaton in the following figure.
What is the set of reachable states for the input string 0011?
{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 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?
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 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?
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 51 
Let <M> be the encoding of a Turing machine as a string over Σ = {0, 1}. Let L = {<M> M is a Turing machine that accepts a string of length 2014}. Then, L is
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 52 
Let L_{1} = {w ∈ {0,1}* w has at least as many occurrences of (110)’s as (011)’s}. Let L_{2} = {w ∈ {0,1}*w has at least as many occurrences of (000)’s as (111)’s}. Which one of the following is TRUE?
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 53 
The length of the shortest string NOT in the language (over Σ = {a b,} of the following regular is expression is ______________.
a*b*(ba)*a*
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 54 
Let Σ be a finite nonempty alphabet and let 2^{Σ*} be the power set of Σ*. Which one of the following is TRUE?
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 55 
Which one of the following problems is undecidable?
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 56 
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 57 
Consider the following languages over the alphabet Σ = {0,1,c}:
 L_{1} = {0^{n}1^{n}  n≥0}
L_{2} = {w^{c}w^{r}  w∈{0,1}*}
L_{3} = {ww^{r}  w∈{0,1}*}
Here, w^{r} is the reverse of the string . Which of these languages are deterministic Contextfree languages?
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 58 
Consider the decision problem 2CNFSAT defined as follows:
 {ΦΦ is a satisfiable propositional formula in CNF with atmost two literals per clause}
For example, is a Boolean formula and it is in 2CNFSAT.
The decision problem 2CNFSAT is
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 59 
Which of the following statements is/are FALSE?
 1. For every nondeterministic Turing machine, there exists an equivalent deterministic Turing machine.
2. Turing recognizable languages are closed under union and complementation.
3. Turing decidable languages are closed under intersection and complementation.
4. Turing recognizable languages are closed under union and intersection.
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 60 
Which of the following statements are TRUE?
 1. The problem of determining whether there exists a cycle in an undirected graph is in P.
2. The problem of determining whether there exists a cycle in an undirected graph is in NP.
3. If a problem A is NPComplete, there exists a nondeterministic polynomial time algorithm to solve A.
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 61 
Consider the DFA given.
Which of the following are FALSE?
Which of the following are FALSE?
 1. Complement of L(A) is contextfree.
2. L(A) = L((11*0+0)(0 + 1)*0*1*)
3. For the language accepted by A, A is the minimal DFA.
4. A accepts all strings over {0, 1} of length at least 2.
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 62 
Which of the following is/are undecidable?

1. G is a CFG. Is L(G) = Φ?
2. G is a CFG. Is L(G) = Σ*?
3. M is a Turing machine. Is L(M) regular?
4. A is a DFA and N is an NFA. Is L(A) = L(N)?
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 63 
What is the complement of the language accepted by the NFA shown below?
Assume Σ={a} and ε is the empty string.
∅  
{ε}  
a*  
{a ,ε} 
Hence the complement of language is: {a* − a^{+}} = {ϵ}
Question 64 
Which of the following problems are decidable?
1) Does a given program ever produce an output?
2) If L is a contextfree language, then, is also contextfree?
3) If L is a regular language, then, is also regular?
4) If L is a recursive language, then, is also recursive?
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 65 
Given the language L ={ab,aa,baa}, which of the following strings are in L *?

1) abaabaaabaa
2) aaaabaaaa
3) baaaaabaaaab
4) baaaaabaa
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 66 
Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two zeros. For example, 001110 and 011001 are in the language, but 100010 is not. All strings of length less than 3 are also in the language. A partially completed DFA that accepts this language is shown below.
The missing arcs in the DFA are
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 67 
Let P be a regular language and Q be a contextfree language such that Q ⊆ P. (For example, let P be the language represented by the regular expression p*q* and Q be [p^{n}q^{n}  n ∈ N]). Then which of the following is ALWAYS regular?
P ∩ Q  
P – Q  
Σ* – P  
Σ* – Q 
since regular languages are closed under complementation.
Question 68 
Which of the following pairs have DIFFERENT expressive power?
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 69 
Definition of a language L with alphabet {a} is given as following.
L = {a^{nk} k>0, and n is a positive integer constant}
What is the minimum number of states needed in a DFA to recognize L?
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 70 
Consider the languages L1,L2 and L3 as given below.
 L1 = {0^{p}1^{q}p,q∈N},
L2 = {0^{p}1^{q}p,q∈N and p=q} and
L3 = {0^{p}1^{q}0^{r}p,q,r∈N and p=q=r}.
Which of the following statements is NOT TRUE?
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 71 
Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?
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 72 
Let L = {w ∈ (0 + 1)*  w has even number of 1s}, i.e. L is the set of all bit strings with even number of 1s. Which one of the regular expression below represents L?
(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 73 
Consider the languages
 L1 = {0^{i}1^{j}  i != j}.
L2 = {0^{i}1^{j}  i = j}.
L3 = {0^{i}1^{j}  i = 2j+1}.
L4 = {0^{i}1^{j}  i != 2j}.
Which one of the following statements is true?
Only L2 is context free  
Only L2 and L3 are context free  
Only L1 and L2 are context free  
All are context free 
Question 74 
Let w be any string of length n is {0, 1}*. Let L be the set of all substrings of w. What is the minimum number of states in a nondeterministic finite automaton that accepts L?
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 75 
The language generated by the above grammar over the alphabet {a,b} is the set of
all palindromes.  
all odd length palindromes.  
strings that begin and end with the same symbol.  
all even length palindromes. 
Question 76 
Which one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)*0(0+1)*0(0+1)*?
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 77 
Which one of the following is FALSE?
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 78 
Given the following state table of an FSM with two states A and B, one input and one output:
If the initial state is A = 0, B = 0, what is the minimum length of an input string which will take the machine to the state A = 0, B = 1 with Output = 1?
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 79 
Let L = L1 ∩ L2, where L1 and L2 are languages as defined below:
 L1 = {a^{m}b^{m}ca^{n}b^{n}  m,n ≥ 0 }
L2 = {a^{i}b^{j}c^{k}  i,j,k ≥ 0 }
Then L is
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 80 
The above DFA accepts the set of all strings over {0,1} that
begin either with 0 or 1  
end with 0
 
end with 00  
contain the substring 00 
Question 81 
Which of the following is true for the language {a^{p}p is a prime} ?
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 82 
Which of the following are decidable?

I. Whether the intersection of two regular languages is infinite
II. Whether a given contextfree language is regular
III. Whether two pushdown automata accept the same language
IV. Whether a given grammar is contextfree
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 83 
If L and are recursively enumerable, then L is
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 84 
Which of the following statements is false?
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 85 
Given below are two finite state automata (→ indicates the start state and F indicates a final state)
Which of the following represents the product automaton Z×Y?
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 86 
Which of the following statements are true?
 I. Every leftrecursive grammar can be converted to a
rightrecursive grammar and viceversa
II. All \epsilon productions can be removed from any contextfree grammar by suitable transformations
III. The language generated by a contextfree grammar all of whose productions are of the form X → w or X → wY (where, w is a string of terminals and Y is a nonterminal), is always regular
IV. The derivation trees of strings generated by a contextfree grammar in Chomsky Normal Form are always binary trees
I, II, III and IV  
II, III and IV only  
I, III and IV only  
I, II and IV only 
Statement III is also true, as this is the standard definition of regular grammar (TYPE 3 grammar).
Statement IV is also true, as in CNF the only productions allowed are of type:
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 87 
Match the following:
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 88 
Match the following NFAs with the regular expressions they correspond to
 1. ϵ + 0(01*1 + 00) * 01*
2. ϵ + 0(10 *1 + 00) * 0
3. ϵ + 0(10 *1 + 10) *1
4. ϵ + 0(10 *1 + 10) *10 *
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 89 
Which of the following are regular sets?
 I. {a^{n}b^{2m}  n≥0, m≥0}
II. {a^{n}b^{m}  n=2m}
III. {a^{n}b^{m}  n≠2m}
IV. {xcy  x,y∈{a,b}*}
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 90 
Which of the following problems is undecidable?
Membership problem for CFGs.  
Ambiguity problem for CFGs.  
Finiteness problem for FSAs.  
Equivalence problem for FSAs. 
Question 91 
Which of the following is TRUE?
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 92 
A minimum state deterministic finite automaton accepting the language L = {w  w ε {0,1} *, number of 0s and 1s in w are divisible by 3 and 5, respectively} has
15 states  
11 states  
10 states  
9 states 
Question 93 
The language L = {0^{i}21^{i}  i≥0} over the alphabet {0, 1, 2} is:
not recursive.  
is recursive and is a deterministic CFL.
 
is a regular language.
 
is not a deterministic CFL but a CFL. 
Question 94 
Which of the following languages is regular?
{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 95 
Consider the following Finite State Automaton.
The language accepted by this automaton is given by the regular expression
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 96 
Consider the following Finite State Automaton.
The minimum state automaton equivalent to the above FSA has the following number of states
1  
2  
3  
4 
Question 97 
Let L_{1} = {0^{n+m}1^{n}0^{m}n,m ≥ 0}, L_{2} = {0^{n+m}1^{n+m}0^{m}n,m ≥ 0}, and L_{3} = {0^{n+m}1^{n+m}0^{n+m}n,m ≥ 0}. Which of these languages are NOT context free?
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 98 
If s is a string over (0 + 1)* then let n_{0}(s) denote the number of 0’s in s and n_{1}(s) the number of 1’s in s. Which one of the following languages is not regular?
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
State 1: n_{0}(s')  n_{1}(s') = 0
State 2: n_{0}(s')  n_{1}(s') = 1
State 3: n_{0}(s')  n_{1}(s') = 2
State 4: n_{0}(s')  n_{1}(s') = 1
State 5: n_{0}(s')  n_{1}(s') = 2
State 6: 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 99 
For S ∈ (0+1) * let d(s) denote the decimal value of s (e.g. d(101) = 5). Let L = {s ∈ (0+1)*d(s)mod5 = 2 and d(s)mod7 = 4}.
Which one of the following statements is true?
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 100 
Consider the following statements about the context free grammar
G = {S → SS, S → ab, S → ba, S → ε}
 I. G is ambiguous
II. G produces all strings with equal number of a’s and b’s
III. G can be accepted by a deterministic PDA.
Which combination below expresses all the true statements about G?
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 101 
Let L_{1} be a regular language, L_{2} be a deterministic contextfree language and L_{3} a recursively enumerable, but not recursive, language. Which one of the following statements is false?
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 102 
Consider the regular language L = (111 + 11111)*. The minimum number of states in any DFA accepting this languages is:
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 103 
Which one of the following grammars generates the language L = {a^{i}b^{j}i≠j}?
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 104 
In the correct grammar of above question, what is the length of the derivation (number of steps starting from S) to generate the string a^{l}b^{m} with l≠m?
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 105 
Consider three decision problems P_{1}, P_{2} and P_{3}. It is known that P_{1} is decidable and P_{2} is undecidable. Which one of the following is TRUE?
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 106 
Consider the machine M:
The language recognized by M is:
{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 107 
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 108 
Consider the languages:
L_{1} = {a^{n}b^{n}c^{m} n,m > 0} and L_{2} = {a^{n}b^{m}c^{m} n,m > 0}
Which one of the following statements is FALSE?
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 109 
Let L_{1} be a recursive language, and let L_{2} be a recursively enumerable but not a recursive language. Which one of the following is TRUE?
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 110 
Consider the languages:
L_{1} = {ww^{R} w ∈ {0,1}*} L_{2} = {w#w^{R}  w ∈ {0,1}*}, where # is a special symbol L_{3} = {ww  w ∈ (0, 1)*}
Which one of the following is TRUE?
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 111 
The following diagram represents a finite state machine which takes as input a binary number from the least significant bit.
Which one of the following is TRUE?
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 112 
The following finite state machine accepts all those binary strings in which the number of 1's and 0's are respectively.
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 113 
The language {a^{m} b^{n} C^{m+n}  m, n ≥ 1} is
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 occurrence of a
PUSH L to stack of occurrence of b
POP K and L for the occurrence of c
→ After POP no 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 114 
L_{1} is a recursively enumerable language over Σ. An algorithm A effectively enumerates its words as w_{1}, w_{2}, w_{3}, ... Define another language L_{2} over Σ Union {#} as {w_{i} # w_{j} : w_{i}, w_{j} ∈ L_{1}, i < j}. Here # is a new symbol. Consider the following assertions.
S_{1}: L_{1} is recursive implies L_{2} is recursive S_{2}: L_{2} is recursive implies L_{1} is recursive
Which of the following statements is true?
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 115 
Nobody knows yet if P = NP. Consider the language L defined as follows:
Which of the following statements is true?
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 regular, then it is recursive.
→ If P!=NP then L becomes ɸ which is also regular, then it is recursive.
So, finally L is recursive.
Question 116 
The regular expression 0*(10*)* denotes the same set as
(1*0)*1*  
0+(0+10)*  
(0+1)*10(0+1)*  
None of the above 
Option (B) and (C) doesn't generate 11.
Question 117 
If the strings of a language L can be effectively enumerated in lexicographic (i.e., alphabetic) order, which of the following statements is true?
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 118 
Consider the following deterministic finite state automaton M.
Let S denote the set of seven bit binary strings in which the first, the fourth, and the last bits are 1. The number of strings in S that are accepted by M is
1  
5  
7  
8 
There are possible: 7 strings.
Question 119 
Let G = ({S},{a,b},R,S) be a context free grammar where the rule set R is S → aSb  SS  ε Which of the following statements is true?
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 120 
Consider two languages L_{1} and L_{2} each on the alphabet ∑. Let f: ∑ → ∑ be a polynomial time computable bijection such that (∀ x)[x ∈ L_{1} iff f(x) ∈ L_{2}]. Further, let f^{1} be also polynomial time computable.
Which of the following CANNOT be true?
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 121 
A single tape Turing Machine M has two states q_{0} and q_{1}, of which q_{0} is the starting state. The tape alphabet of M is {0, 1, B} and its input alphabet is {0, 1}. The symbol B is the blank symbol used to indicate end of an input string. The transition function of M is described in the following table.
The table is interpreted as illustrated below. The entry (q_{1}, 1, R) in row q_{0} and column 1 signifies that if M is in state q_{0} and reads 1 on the current tape square, then it writes 1 on the same tape square, moves its tape head one position to the right and transitions to state q_{1}.
Which of the following statements is true about M?
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 122 
Define languages L_{0} and L_{1} as follows:
L_{0} = {〈M, w, 0〉  M halts on w} L_{1} = {〈M, w, 1〉  M does not halts on w}
Here 〈M, w, i〉 is a triplet, whose first component. M, is an encoding of a Turing Machine, second component, w, is a string, and third component, i, is a bit.
Let L = L_{0}∪L_{1}. Which of the following is true?
Question 123 
Consider the NFA M shown below.
Let the language accepted by M be L. Let L_{1} be the language accepted by the NFA M_{1}, obtained by changing the accepting state of M to a nonaccepting state and by changing the nonaccepting state of M to accepting states. Which of the following statements is true?
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 124 
The language accepted by a Pushdown Automaton in which the stack is limited to 10 items is best described as
Context free  
Regular  
Deterministic Context free  
Recursive 
Question 125 
The Finite state machine described by the following state diagram with A as starting state, where an arc label is x/y and x stands for 1bit input and y stands for 2 bit output
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 126 
The smallest finite automaton which accepts the language {xlength of x is divisible by 3} has
2 states  
3 states  
4 states  
5 states 
Minimum no. of states that we require is "3".
Question 127 
Which of the following is true?
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 128 
The C language is:
A context free language  
A context sensitive language  
A regular language  
Parsable fully only by a Turing machine 
Question 129 
The aim of the following question is to prove that the language {M M is the code of a Turing Machine which, irrespective of the input, halts and outputs a 1}, is undecidable. This is to be done by reducing form the language {M',x M' halts on x}, which is known to be undecidable. In parts (a) and (b) describe the 2 main steps in the construction of M. in part (c) describe the key property which relates the behaviour of M on its input w to the behaviour of M′ on x.
 (a) On input w, what is the first step that M must make?
(b) On input w, based on the outcome of the first step, what is the second step that M must make?
(c) What key property relates the behaviour of M on w to the behaviour of M′ on x?
Theory Explanation is given below. 
Question 130 
We require a four state automaton to recognize the regular expression (ab)*abb.
 (a) Give an NFA for this purpose.
(b) Give a DFA for this purpose.
Theory Explanation is given below. 
Question 131 
Consider the following two statements:
 S1: {0^{2n}n≥1} is a regular language
S2: {0^{m}1^{n}0^{m+n}m≥1 and n≥1} is a regular language
Which of the following statements is correct?
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 132 
Which of the following statements is true?
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 133 
Given an arbitrary nondeterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least
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 134 
Consider a DFA over Σ = {a,b} accepting all strings which have number of a's divisible by 6 and number of b's divisible by 8. What is the minimum number of states that the DFA will have?
8  
14  
15  
48 
Same as b's divisible by 8 contains 8 state.
Total no. of states is = 8 * 6 = 48
Question 135 
Consider the following languages:
 L1 = {www ∈ {a,b}*}
L2 = {ww^{R}w ∈ {a,b}*, w^{R} is the reverse of w}
L3 = {0^{2i}i is an integer}
L3 = {0^{i2}i is an integer}
Which of the languages are regular?
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 136 
Consider the following problem X.
Given a Turing machine M over the input alphabet Σ, any state q of M And a word w∈Σ*, does the computation of M on w visit the state q?
Which of the following statements about X is correct?
X is decidable  
X is undecidable but partially decidable  
X is undecidable and not even partially decidable  
X is not a decision problem 
Question 137 
Construct DFA’s for the following languages:
(a) L = {ww ∈ {a,b}*, w has baab as a subsring } (b) L = {ww ∈ {a,b}*, w has an odd number of a's and an odd number of b's}
Theory Explanation is given below. 
Question 138 
Give a deterministic PDA for the language L = {a^{n}cb^{2n}n ≥ 1} over the alphabet Σ = {a,b,c}. Specify the acceptance state.
Theory Explanation is given below. 
Question 139 
Let a decision problem X be defined as follows:
X: Given a Turing machine M over Σ and nay word w ∈ Σ, does M loop forever on w?
You may assume that the halting problem of Turing machine is undecidable but partially decidable.
 (a) Show that X is undecidable.
(b) Show that X is not even partially decidable.
Theory Explanation is given below. 
Question 140 
Let S and T be language over Σ = {a,b} represented by the regular expressions (a+b*)* and (a+b)*, respectively. Which of the following is true?
S ⊂ T  
T ⊂ S  
S = T  
S ∩ T = ɸ 
Question 141 
Let L denotes the language generated by the grammar S → 0S0/00.
Which of the following is true?
L = 0^{+}  
L is regular but not 0^{+}  
L is context free but not regular  
L is not context free 
Question 142 
What can be said about a regular language L over {a} whose minimal finite state automation has two states?
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 143 
Consider the following decision problems:
 (P1) Does a given finite state machine accept a given string
(P2) Does a given context free grammar generate an infinite number of stings
Which of the following statements is true?
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 144 
(a) Construct as minimal finite state machine that accepts the language, over {0,1}, of all strings that contain neither the substring 00 nor the substring 11.
(b) Consider the grammar
S → aS Ab S → ε A → bA A → ε
Where S, A are nonterminal symbols with S being the start symbol; a,b are terminal symbols and ε is the empty string. This grammar generates strings of the form a^{i}b^{j} for some i,j ≥ 0, where i and j satisfy some condition. What is the condition on the values of i and j?
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 145 
A pushdown automaton (pda) is given in the following extended notation of finite state diagrams:
The nodes denote the states while the edges denote the moves of the pda. The edge labels are of the form d, s where d is the input symbol read and s, s' are the stack contents before and after the move. For example the edge labeled 1, s/1.s denotes the move from state to q_{o} to q_{0} in which the input symbol 1 is read and pushed to the stack.
(a) Introduce two edges with appropriate labels in the above diagram so that the resulting pda accepts the language
{x2x^{R}x ∈ {0,1}*, x^{R} denotes reverse of x}, by empty stack.
(b) Describe a nondeterministic pda with three states in the above notation that
accept the language {0^{n}1^{m} n ≤ m ≤ 2n} by empty stack
Theory Explanation is given below. 
(b)
Question 146 
Consider the regular expression (0 + 1) (0 + 1)…. N times. The minimum state finite automation that recognizes the language represented by this regular expression contains
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 147 
Contextfree languages are closed under:
Union, intersection  
Union, Kleene closure  
Intersection, complement  
Complement, Kleene closure 
By checking the options only option B is correct.
Question 148 
Let L_{D} be the set of all languages accepted by a PDA by final state and L_{E} the set of all languages accepted by empty stack. Which of the following is true?
L_{D} = L_{E}  
L_{D} ⊃ L_{E}  
L_{E} = L_{D}  
None of the above 
Question 149 
If L is context free language and L2 is a regular language which of the following is/are false?
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 150 
A grammar that is both left and right recursive for a nonterminal, is
Ambiguous  
Unambiguous  
Information is not sufficient to decide whether it is ambiguous or unambiguous  
None of the above 
Question 151 
(a) Given that A is regular and A∪B is regular, does it follow that B is necessarily regular? Justify your answer.
(b) Given two finite automata M1, M2, outline an algorithm to decide if L(M1)⊆L(M2). (note: strict subset)
Theory Explanation. 
Question 152 
Show that the language L = {xcx x ∈ {0,1}* and c is a terminal symbol} is not context free, c is not 0 or 1.
Theory Explanation. 
Question 153 
If the regular set A is represented by A = (01 + 1)* and the regular set ‘B’ is represented by B = ((01)*1*)*, which of the following is true?
A ⊂ B  
B ⊂ A  
A and B are incomparable  
A = B 
Question 154 
Both A and B are equal, which generates strings over {0,1}, while 0 is followed by 1.
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 regular and recognized by deterministic finite automata.
Question 155 
Regarding the power of recognition of languages, which of the following statements is false?
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 156 
The string 1101 does not belong to the set represented by
110*(0 + 1)  
1 ( 0 + 1)* 101  
(10)* (01)* (00 + 11)*  
Both C and D 
C & D are not generate string 1101.
Question 157 
How many sub strings of different lengths (nonzero) can be found formed from a character string of length n?
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 158 
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 159 
Which of the following statements is false?
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 160 
Design a deterministic finite state automaton (using minimum number of states) that recognizes the following language:
L = {w ∈ {0,1}*  w interpreted as a binary number (ignoring the leading zeros) is divisible by 5}
Theory Explanation. 
Question 161 
Let M = ({q_{0}, q_{1}}, {0, 1}, {z_{0}, x}, δ, q_{0}, z_{0}, ∅) be a pushdown automaton where δ is given by
 δ(q_{0}, 1, z_{0}) = {(q_{0}, xz_{0})}
δ(q_{0}, ε, z_{0}) = {(q_{0}, ε)}
δ(q_{0}, 1, X) = {(q_{0}, XX)}
δ(q_{1}, 1, X) = {(q_{1}, ε)}
δ(q_{0}, 0, X) = {(q_{1}, X)}
δ(q_{0}, 0, z_{0}) = {(q_{0}, z_{0})}
(a) What is the language accepted by this PDA by empty stack?
(b) Describe informally the working of the PDA.
Theory Explanation. 
Question 162 
(a) Let G_{1} = (N, T, P, S_{1}) be a CFG where,
N = {S_{1}, A, B}, T = {a,b} and
P is given by
S_{1} → aS_{1}b S_{1} → aBb S_{1} → aAb B → Bb A → aA B → b A → a
What is L(G1)?
(b) Use the grammar in part(a) to give a CFG
for L_{2} = {a^{i} b^{j} a^{k} b^{l}  i, j, k, l ≥ 1, i=j or k=l} by adding not more than 5 production rule.
(c) Is L_{2} inherently ambiguous?
Theory Explanation. 
Question 163 
(a) An identifier in a programming language consists of upto six letters and digits of which the first character must be a letter. Derive a regular expression for the identifier.
(b) Build an LL(1) parsing table for the language defined by the LL(1) grammar with productions
Program → begin d semi X end X → d semi X  sY Y → semi s Y  ε
Theory Explanation. 
Question 164 
Given Σ = {a,b}, which one of the following sets is not countable?
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 165 
Which one of the following regular expressions over {0,1} denotes the set of all strings not containing 100 as a substring?
0*(1+0)*  
0*1010*  
0*1*01  
0(10+1)* 
(B) generates 100 as substring.
(C) doesn't generate 1.
(D) answer.
Question 166 
Which one of the following is not decidable?
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 167 
Which of the following languages over {a,b,c} is accepted by a deterministic pushdown automata?
Note: w^{R} is the string obtained by reversing 'w'.
{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 168 
Which two of the following four regular expressions are equivalent? (ε is the empty string).
 (i) (00)*(ε+0)
(ii) (00)*
(iii) 0*
(iv) 0(00)*
(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 169 
Which of the following statements is false?
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 170 
Let L ⊆ Σ* where Σ = {a, b}. Which of the following is true?
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 171 
If L_{1} and L_{2} are context free languages and R a regular set, one of the languages below is not necessarily a context free language. Which one?
L_{1}, L_{2}  
L_{1} ∩ L_{2}  
L_{1} ∩ R  
L_{1} ∪ L_{2} 
Question 172 
Define for a context free language L ⊆ {0,1}*, init(L) = {u ∣ uv ∈ L for some v in {0,1}∗} (in other words, init(L) is the set of prefixes of L)
Let L = {w ∣ w is nonempty and has an equal number of 0’s and 1’s}
Then init(L) is
the 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 173 
The grammar whose productions are
→ if id then → if id then else → id := id
is ambiguous because
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 174 
Consider the given figure of state table for a sequential machine. The number of states in the minimized machine will be
4  
3  
2  
1 
Question 175 
Let G be a contextfree grammar where G = ({S, A, B, C},{a,b,d},P,S) with the productions in P given below.
S → ABAC A → aA ∣ ε B → bB ∣ ε C → d
(ε denotes null string). Transform the grammar G to an equivalent contextfree grammar G' that has no ε productions and no unit productions. (A unit production is of the form x → y, and x and y are non terminals.)
Theory Explanation. 
Question 176 
Let Q = ({q_{1},q_{2}}, {a,b}, {a,b,Z}, δ, Z, ϕ) be a pushdown automaton accepting by empty stack for the language which is the set of all non empty even palindromes over the set {a,b}. Below is an incomplete specification of the transitions δ. Complete the specification. The top of the stack is assumed to be at the right end of the string representing stack contents.
(1) δ(q_{1},a,Z) = {(q_{1},Za)} (2) δ(q_{1},b,Z) = {(q_{1},Zb)} (3) δ(q_{1},a,a) = {(.....,.....)} (4) δ(q_{1},b,b) = {(.....,.....)} (5) δ(q_{2},a,a) = {(q_{2},ϵ)} (6) δ(q_{2},b,b) = {(q_{2},ϵ)} (7) δ(q_{2},ϵ,Z) = {(q_{2},ϵ)}
Theory Explanation. 
Question 177 
In some programming languages, an identifier is permitted to be a letter following by any number of letters or digits. If L and D denote the sets of letters and digits respectively, which of the following expressions defines an identifier?
(L ∪ D)^{+}  
L(L ∪ D)*  
(L⋅D)*  
L⋅(L⋅D)* 
L(L ∪ D)*
Question 178 
Consider a grammar with the following productions
S → a∝bb∝c aB S → ∝Sb S → ∝b bab S ∝ → bd bb
The above grammar is:
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 179 
Which of the following definitions below generates the same language as L, where L = {x^{n}y^{n} such that n >= 1}?
I. E → xEyxy II. xy(x^{+}xyy^{+}) III. x^{+}y^{+}
I only  
I and II  
II and III  
II only 
Question 180 
A finite state machine with the following state table has a single input x and a single out z.
If the initial state is unknown, then the shortest input sequence to reach the final state C is:
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 181 
Let Σ = {0,1}, L = Σ* and R = {0^{n}1^{n} such that n >0} then the languages L ∪ R and R are respectively
regular, regular  
not regular, regular  
regular, not regular  
not regular, no regular 
Question 182 
Let L be a language over ∑ i.e., *L ≤ ∑ . Suppose L satisfies the two conditions given below
(i) L is in NP and
(ii) For every n, there is exactly one string of length n that belongs to L.
Let L^{c} be the complement of L over ∑*. Show that L^{c} is also in NP.
Theory Explanation. 
Question 183 
Which of the following conversions is not possible (algorithmically)?
Regular grammar to context free grammar  
Nondeterministic FSA to deterministic FSA  
Nondeterministic PDA to deterministic PDA  
Nondeterministic Turing machine to deterministic Turing machine 
Question 184 
Which of the following features cannot be captured by contextfree grammars?
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 185 
The regular expression for the language recognized by the finite state automaton of figure is __________
L = 0*1* 
L contains all binary strings where a 1 is not followed by a 0.
Question 186 
Every subset of a countable set is countable.
State whether the above statement is true or false with reason.
True  
False 
Question 187 
(a) Given a set
S = {x there is an xblock of 5's in the decimal expansion of π}
(Note: xblock is a maximal block of x successive 5’s)
Which of the following statements is true with respect to S? No reasons need to be given for the answer.
 (i) S is regular
(ii) S is recursively enumerable
(iii) S is not recursively enumerable
(iv) S is recursive
(b) Given that a language L_{1} is regular and that the language L_{1} ∪ L_{2} is regular, is the language L_{2} always regular? Prove your answer.
Theory Explanation. 
Question 188 
A grammar G is in ChomskyNormal Form (CNF) if all its productions are of the form A → BC or A → a, where A, B and C, are nonterminals and a is a terminal. Suppose G is a CFG in CNF and w is a string in L(G) of length, then how long is a derivation of w in G?
Theory Explanation. 
Question 189 
Consider the language L = {a^{n} n≥0} ∪ {a^{n}b^{n} n≥0} and the following statements.
 I. L is deterministic contextfree.
II. L is contextfree but not deterministic contextfree.
III. L is not LL(k) for any k.
Which of the above statements is/are TRUE?
II only  
III only  
I only  
I and III only 
We can make DPDA for this.
L is not LL(k) for any “k” look aheads. The reason is the language is a union of two languages which have common prefixes. For example strings {aa, aabb, aaa, aaabbb,….} present in language. Hence the LL(k) parser cannot parse it by using any lookahead “k” symbols.
Question 190 
Consider the following statements.
 I. If L_{1} ∪ L_{2} is regular, then both L_{1} and L_{2} must be regular.
II. The class of regular languages is closed under infinite union.
Which of the above statements is/are TRUE?
Both I and II
 
II only  
Neither I nor II  
I only

Assume L_{1} = {a^{n} b^{n}  n>0} and L_{2} = complement of L_{1}
L_{1} and L_{2} both are DCFL but not regular, but L_{1} U L_{2} = (a+b)* which is regular.
Hence even though L_{1} U L_{2} is regular, L_{1} and L_{2} need not be always regular.
Statement II is wrong.
Assume the following finite (hence regular) languages.
L_{1} = {ab}
L_{2} = {aabb}
L_{3} = {aaabbb}
.
.
.
L_{100} = {a^{100} b^{100}}
.
.
.
If we take infinite union of all above languages i.e,
{L_{1} U L_{2} U ……….L_{100} U ……}
then we will get a new language L = {a^{n} b^{n}  n>0}, which is not regular.
Hence regular languages are not closed under infinite UNION.
Question 191 
Which one of the following regular expressions represents the set of all binary strings with an odd number of 1’s?
10*(0*10*10*)*
 
((0 + 1)*1(0 + 1)*1)*10*
 
(0*10*10*)*10*  
(0*10*10*)*0*1

The regular expression ((0+1)*1(0+1)*1)*10* generate string “11110” which is not having odd number of 1’s , hence wrong option.
The regular expression (0*10*10*)10* is not a generating string “01”. Hence this is also wrong . It seems none of them is correct.
NOTE: Option 3 is most appropriate option as it generates the max number of strings with odd 1’s.
But option 3 is not generating odd strings. So, still it is not completely correct.
The regular expression (0*10*10*)*0*1 always generates all string ends with “1” and thus does not generate string “01110” hence wrong option.
Question 192 
Which of the following languages are undecidable? Note that
 L_{1} =
L_{2} = {
L_{3} = {
L_{4} = {
L_{2} and L_{3} only
 
L_{1} and L_{3} only
 
L_{2}, L_{3} and L_{4} only  
L_{1}, L_{3} and L_{4} only 
Only L_{3} is decidable. We can check whether a given TM reach state q in exactly 100 steps or not. Here we have to check only upto 100 steps, so here is not any case of going to infinite loop.
Question 193 
Consider the following language.
L = {x ∈ {a,b}*  number of a’s in x is divisible by 2 but not divisible by 3}
The minimum number of states in a DFA that accepts L is ______.
6 
DFA 1: No. of a’s not divisible by 3
Using product automata:
Question 194 
Consider the following languages.
 L_{1} = {wxyx  w,x,y ∈ (0 + 1)^{+}}
L_{2} = {xy  x,y ∈ (a + b)*, x = y, x ≠ y}
Which one of the following is TRUE?
L_{1} is contextfree but not regular and L_{2} is contextfree.  
Neither L_{1} nor L_{2} is contextfree.
 
L_{1} is regular and L_{2} is contextfree.
 
L_{1} is contextfree but L_{2} is not contextfree. 
So it is equivalent to
(a+b)^{+} a (a+b)^{+} a + (a+b)^{+} b (a+b)^{+} b
L_{2} is CFL since it is equivalent to complement of L=ww.
Complement of L=ww is CFL.
Question 195 
If the state machine described in figure, should have a stable state, the restriction on the inputs is given by
Question 196 
A simple Pascal like language has only three statements.
(i) assignment statement e.g. x:=expression
(ii) loop construct e.g. for i:=expression to expression do statement.
(iii) sequencing e.g. begin statement ;…; statement end
(a) Write a contextfree grammar (CFG) for statements in the above language. Assume that expression has already been defined. Do not use optional
parentheses and * operator in CFG.
(b) Show the parse tree for the following statement:
for j:=2 to 10 do begin x:=expr1; y:=expr2 end
Theory Explanation. 
Question 197 
Draw the state transition of a deterministic finite state automaton which accepts all strings from the alphabet {a,b}, such that no string has 3 consecutive occurrences of the letter b.
Theory Explanation. 
Question 198 
Which of the following problems is not NPhard?
Hamiltonian circuit problem  
The 0/1 Knapsack problem  
Finding biconnected components of a graph  
The graph colouring problem 
Question 199 
For a contextfree grammar, FOLLOW(A) is the set of terminals that can appear immediately to the right of nonterminal A in some “sentential” form. We define two sets LFOLLOW(A) and RFOLLOW(A) by replacing the word “sentential” by “left sentential” and “right most sentential” respectively in the definition of FOLLOW(A).
Which of the following statements is/are true?
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 200 
Which of the following regular expression identifies are true?
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 201 
If G is a contextfree grammar and w is a string of length l in L(G), how long is a derivation of w in G, if G is Chomsky normal form?
2l  
2l + 1  
2l  1  
l 
2l  1
For GNF, it is
l
Question 202 
Contextfree languages are
closed under union  
closed under complementation  
closed under intersection  
closed under Kleene closure  
Both A and D 
Question 203 
In which of the cases stated below is the following statement true?
“For every nondeterministic machine M_{1} there exists an equivalent deterministic machine M_{2} recognizing the same language“.
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 204 
Which of the following three statements are true? Prove your answer.
 (i) The union of two recursive languages is recursive.
(ii) The language {O"n is a prime} is not regular.
(iii) Regular languages are closed under infinite union.
Theory Explanation. 
Question 205 
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: Let r = 1(1+0)*, s = 11*0 and t = 1*0 be three regular expressions. Which one of the following is true?
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 206 
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: Which one of the following is the strongest correct statement about a finite language over some finite alphabet ∑?
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 207 
(a) Show that Turing machines, which have a read only input tape and constant size work tape, recognize precisely the class or regular languages.
(b) Let L be the language of all binary strings in which the third symbol from the right is a_{1}. Give a nondeterministic finite automaton that recognizes L. How many states does the minimized equivalent deterministic finite automaton have? Justify your answer briefly?
Theory Explanation. 
Question 208 
Choose the correct alternatives (More than one may be correct). Recursive languages are:
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 209 
Choose the correct alternatives (More than one may be correct).
It is undecidable whether: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 behavior of TM unknown hence, undecidable.
Question 210 
Choose the correct alternatives (More than one may be correct). Let R_{1} and R_{2} be regular sets defined over the alphabet Σ Then:
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 211 
Contextfree languages and regular languages are both closed under the operation(s) of:
Union  
Intersection  
Concatenation  
Complementation  
Both A and C 
Question 212 
Which of the following problems are undecidable?
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 213 
Regularity is preserved under the operation of string reversal.
True  
False 
Question 214 
All subsets of regular sets are regular.
True  
False 
Question 215 
A minimal DFA that is equivalent to an NDFA with n nodes has always 2^{n} states.
True  
False 
Question 216 
The intersection of two CFL's is also a CFL.
True  
False 
Question 217 
A is recursive if both A and its complement are accepted by Turing machines.
True  
False 
Question 218 
A contextfree grammar is ambiguous if:
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 219 
FORTRAN is a:
Regular language.  
Contextfree language.  
Contextsensitive language.  
None of the above. 
Some of the features are:
1) Variable declared before use.
2) Matching formal and actual parameters of functions.
Question 220 
Let N be an NFA with n states and let M be the minimized DFA with m states recognizing the same language. Which of the following in NECESSARILY true?
m ≤ 2^{n}  
n ≤ m  
M has one accept state  
m = 2^{n} 
A state in a DFA is a proper subset of states of NFA of corresponding DFA.
→ No. of subsets with n elements = 2^{n}
→ m ≤ 2^{n}
Question 221 
If the final states and nonfinal states in the DFA below are interchanged, then which of the following languages over the alphabet {a,b} will be accepted by the new DFA?
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 accepted by RE and it belongs to b*aa*(ba)*b*.
Question 222 
Consider the following languages.
L_{1} = {a^{i} b^{j} c^{k}  i = j, k ≥ 1} L_{1} = {a^{i} b^{j}  j = 2i, i ≥ 0}Which of the following is true?
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 223 
Consider a CFG with the following productions.
S → AA  B A → 0A  A0  1 B → 0B00  1S is the start symbol, A and B are nonterminals and 0 and 1 are the terminals. The language generated by this grammar is
{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 224 
Which of the following languages is (are) nonregular? L_{1} = {0^{m}1^{n}  0 ≤ m ≤ n ≤ 10000} L_{2} = {w  w reads the same forward and backward} L_{3} = {w ∊ {0, 1} *  w contains an even number of 0's and an even number of 1's}
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 225 
Consider the following two finite automata. M_{1} accepts L_{1} and M_{2} accepts L_{2}.
Which one of the following is TRUE?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 226 
A CFG G is given with the following productions where S is the start symbol, A is a nonterminal and a and b are terminals.
S → aS∣A A → aAb∣bAa∣ϵWhich of the following strings is generated by the grammar above?
aabbaba  
aabaaba  
abababb  
aabbaab 
S→aA
S→aaAb
S→aabAab
S→aabbAaab
S→aabbaab
Question 227 
A CFG G is given with the following productions where S is the start symbol, A is a nonterminal and a and b are terminals.
S → aS∣A A → aAb∣bAa∣ϵFor the correct answer in Q75, how many steps are required to derive the string and how many parse trees are there?
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 228 
Consider the following DFA in which s_{0} is the start state and s_{1}, s_{3} are the final states.
What language does this DFA recognize ?
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 229 
Consider the grammar given below
S → x B  y A A → x  x S  y A A B → y  y S  y B B
Consider the following strings.
(i) xxyyx (ii) xxyyxy (iii) xyxy (iv) yxxy (v) yxx (vi) xyx
Which of the above strings are generated by the grammar ?
(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 230 
Consider the following grammars. Names representing terminals have been specified in capital letters.
G_{1}: stmnt → WHILE (expr) stmnt stmnt → OTHER expr → ID G_{2}: WHILE (expr) stmnt stmnt → OTHER expr → expr + expr expr → expr * expr expr → ID
Which one of the following statements is true?
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 231 
Consider the following finite automata P and Q over the alphabet {a, b, c}. The start states are indicated by a double arrow and final states are indicated by a double circle. Let the languages recognized by them be denoted by L(P) and L(Q) respectively.
The automation which recognizes the language L(P) ∩ L(Q) is:
Question 232 
Consider the regular expression
R = (a + b)* (aa + bb) (a + b)*Which of the following nondeterministic finite automata recognizes the language defined by the regular expression R? Edges labeled λ denote transitions on the empty string.
But option (B), (C), (D) accepts aba, which do not contain aa or bb as substring.
Hence, (A) is correct.
Question 233 
Consider the regular expression
R = (a + b)* (aa + bb) (a + b)*Which deterministic finite automaton accepts the language represented by the regular expression R ?
(C) It is not accepting 'abb' which is in language.
(D) It is not accepting 'aa' and 'bb' which is in language.
Question 234 
Consider the regular expression
R = (a + b)* (aa + bb) (a + b)*Which one of the regular expressions given below defines the same language as defined by the regular expression R?
(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 235 
In the automaton below, s is the start state and t is the only final state.
Consider the strings u = abbaba, v = bab, and w = aabb. Which of the following statements is true?
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 236 
In the contextfree grammar below, S is the start symbol, a and b are terminals, and ϵ denotes the empty string
S → aSa  bSb  a  b  ϵWhich of the following strings is NOT generated by the grammar?
aaaa  
baba  
abba  
babaaabab 
Given string accepts all palindromes.
Option B → baba is not palindrome.
So, this is not accepted by S.
Question 237 
Which regular expression best describes the language accepted by the nondeterministic automaton below?
(a + b)* a(a + b)b  
(abb)*  
(a + b)* a(a + b)* b(a + b)*  
(a + b)* 
Question 238 
Consider the regular grammar below
S → bS  aA  ϵ A → aS  bA
The MyhillNerode equivalence classes for the language generated by the grammar are
{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 239 
Which of the following statements about regular languages is NOT true?
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 240 
Which of the following languages is accepted by a nondeterministic pushdown automaton (PDA) but NOT by a deterministic PDA?
{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 241 
Let L be a contextfree language and M a regular language. Then the language L ∩ M is
always regular  
never regular  
always a deterministic contextfree language  
always a contextfree language 
Question 242 
Consider the pushdown automaton (PDA) below which runs over the input alphabet (a, b, c). It has the stack alphabet {Z_{0}, X} where Z_{0} is the bottomofstack marker. The set of states of the PDA is (s, t, u, f} where s is the start state and f is the final state. The PDA accepts by final state. The transitions of the PDA given below are depicted in a standard manner. For example, the transition (s, b, X) → (t, XZ_{0}) means that if the PDA is in state s and the symbol on the top of the stack is X, then it can read b from the input and move to state t after popping the top of stack and pushing the symbols Z_{0} and X (in that order) on the stack.
(s, a, Z_{0}) → (s, XXZ_{0}) (s, ϵ, Z_{0}) → (f, ϵ) (s, a, X) → (s, XXX) (s, b, X) → (t, ϵ) (t, b, X) → (t,.ϵ) (t, c, X) → (u, ϵ) (u, c, X) → (u, ϵ) (u, ϵ, Z_{0}) → (f, ϵ)
The language accepted by the PDA is
{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 243 
In the contextfree grammar below, S is the start symbol, a and b are terminals, and ϵ denotes the empty string.
S → aSAb  ϵ A → bA  ϵ
The grammar generates the language
((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 244 
For a state machine with the following state diagram the expression for the next state S^{+} in terms of the current state S and the input variables x and y is
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 245 
Let L be a regular language. Consider the constructions on L below:
I. repeat (L) = {ww  w ∊ L}
II. prefix (L) = {u  ∃v : uv ∊ L}
III. suffix (L) = {v  ∃u : uv ∊ L}
IV. half (L) = {u  ∃v :  v  =  u  and uv ∊ L}
Which of the constructions could lead to a nonregular language?
Both I and IV  
Only I  
Only IV  
Both II and III 
Half (L), Suffix (L) and Prefix (L) are regular languages.
Question 246 
Let L be a regular language. Consider the constructions on L below:
(I) repeat (L) = {ww  w ∊ L}
(II) prefix (L) = {u  ∃v : uv ∊ L}
(III) suffix (L) = {v  ∃u uv ∊ L}
(IV) half (L) = {u  ∃v :  v  =  u  and uv ∊ L}
Which choice of L is best suited to support your answer above?
(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 247 
Let L be a regular language and M be a contextfree language, both over the alphabet Σ. Let L^{c} and M^{c} denote the complements of L and M respectively. Which of the following statements about the language if L^{c} ∪ M^{c} is TRUE?
It is necessarily regular but not necessarily contextfree.  
It is necessarily contextfree.  
It is necessarily nonregular.  
None of the above. 
Question 248 
Which of the following statements is TRUE about the regular expression 01*0?
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 249 
The language {0^{n} 1^{n} 2^{n}  1 ≤ n ≤ 10^{6}} is
regular  
contextfree but not regular  
contextfree but its complement is not contextfree  
not contextfree 
So, given language is regular.
Question 250 
Which of the following expressions is equivalent to (A⊕B)⊕C
None of these 
⇒ We know that
A⊕B = A'B + AB'
A⊙B = AB + A'B' ⇒ (A⊕B)'C + (A⊕B)C'
⇒ (A⊙B)C + (A'B + AB')C'
⇒ (AB + A'B')C + (A'B + AB')C'
⇒ ABC + A'B'C + A'BC' + AB'C'
⇒ ABC + (A'B'C + A'B'C) + A'BC' + AB'C'
[We know that A + A = A]
⇒ ABC + A'B'C + A'B'C + A'BC' + AB'C'
⇒ ABC + A'(B'C + BC') + B'(A'C + AC')
⇒ ABC + A'(B⊕C) + B'(A⊕C)
Question 251 
Consider the nondeterministic finite automaton (NFA) shown in the figure.
State X is the starting state of the automaton. Let the language accepted by the NFA with Y as the only accepting state be L1. Similarly, let the language accepted by the NFA with Z as the only accepting state be L2. Which of the following statements about L1 and L2 is TRUE? Correction in Question: There is an edge from Z>Y labeled 0 and another edge from Y>Z labeled 1  in place of double arrowed and no arrowed edges.
L1 = L2  
L1 ⊂ L2  
L2 ⊂ L1  
None of the above 
Y = X0 + Y0 + Z1
Z = X0 + Y0 + Z;
⇒ X = Z;
⇒ L1 = L2
Question 252 
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 253 
Consider the regular grammar:
S → Xa  Ya
X → Za Z → Sa  ϵ
Y → Wa W → Sa
where S is the starting symbol, the set of terminals is {a} and the set of nonterminals is {S, W, X, Y, Z}. We wish to construct a deterministic finite automaton (DFA) to recognize the same language. What is the minimum number of states required for the DFA?
2  
3  
4  
5 
The minimum string length is 2 [aa], so we require 3 states to construct DFA.
Question 254 
A language L satisfies the Pumping Lemma for regular languages, and also the Pumping Lemma for contextfree languages. Which of the following statements about L is TRUE?
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 255 
Consider the contextfree grammar
E → E + E E → (E * E) E → idwhere E is the starting symbol, the set of terminals is {id, (,+,),*}, and the set of nonterminals is {E}.
Which of the following terminal strings has more than one parse tree when parsed according to the above grammar?
id + id + id + id  
id + (id* (id * id))  
(id* (id * id)) + id  
((id * id + id) * id) 
Question 256 
Consider the contextfree grammar
E → E + E
E → (E * E)
E → id
where E is the starting symbol, the set of terminals is {id, (,+,),*}, and the set of nonterminals is {E}.
For the terminal string id + id + id + id, how many parse trees are possible?
5  
4  
3  
2 
Question 257 
A sink in a directed graph is a vertex i such that there is an edge from every vertex j ≠ i to i and there is no edge from i to any other vertex. A directed graph G with n vertices is represented by its adjacency matrix A, where A[i] [j] = 1 if there is an edge directed from vertex i to j and 0 otherwise. The following algorithm determines whether there is a sink in the graph G.
i = 0 do { j = i + 1; while ((j < n) && E_{1}) j++; if (j < n) E_{2}; } while (j < n); flag = 1; for (j = 0; j < n; j++) if ((j! = i) && E_{3}) flag = 0; if (flag) printf("Sink exists"); else printf ("Sink does not exist");Choose the correct expressions for E_{1} and E_{2}
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 258 
A sink in a directed graph is a vertex i such that there is an edge from every vertex j ≠ i to i and there is no edge from i to any other vertex. A directed graph G with n vertices is represented by its adjacency matrix A, where A[i] [j] = 1 if there is an edge directed from vertex i to j and 0 otherwise. The following algorithm determines whether there is a sink in the graph G.
i = 0 do { j = i + 1; while ((j < n) && E_{1}) j++; if (j < n) E_{2}; } while (j < n); flag = 1; for (j = 0; j < n; j++) if ((j! = i) && E_{3}) flag = 0; if (flag) printf("Sink exists"); else printf("Sink does not exist");Choose the correct expressions for E_{3}
(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 259 
Consider a simple graph with unit edge costs. Each node in the graph represents a router. Each node maintains a routing table indicating the next hop router to be used to relay a packet to its destination and the cost of the path to the destination through that router. Initially, the routing table is empty. The routing table is synchronously updated as follows. In each updation interval, three tasks are performed.
1. A node determines whether its neighbours in the graph are accessible. If so, it sets the tentative cost to each accessible neighbour as 1. Otherwise, the cost is set to ∞.
2. From each accessible neighbour, it gets the costs to relay to other nodes via that neighbour (as the next hop).
3. Each node updates its routing table based on the information received in the previous two steps by choosing the minimum cost.
For the graph given above, possible routing tables for various nodes after they have stabilized, are shown in the following options. Identify the correct table.
Question 260 
Consider a simple graph with unit edge costs. Each node in the graph represents a router. Each node maintains a routing table indicating the next hop router to be used to relay a packet to its destination and the cost of the path to the destination through that router. Initially, the routing table is empty. The routing table is synchronously updated as follows. In each updation interval, three tasks are performed.
1. A node determines whether its neighbours in the graph are accessible. If so, it sets the tentative cost to each accessible neighbour as 1. Otherwise, the cost is set to ∞.
2. From each accessible neighbour, it gets the costs to relay to other nodes via that neighbour (as the next hop).
3. Each node updates its routing table based on the information received in the previous two steps by choosing the minimum cost.
Continuing from the earlier problem, suppose at some time t, when the costs have stabilized, node A goes down. The cost from node F to node A at time (t + 100) is
>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 261 
Which one of the following regular expressions is NOT equivalent to the regular expression (a + b + c)*?
(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 262 
Which one of the following statements is FALSE?
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 263 
Which one of the following strings is not a member of L(M)?
Let M = (K,Σ,Γ,Δ,s,F) be a pushdown automaton, where
K = {s,f}, F = {f}, Σ = {a,b}, Γ = {a} and
Δ = {((s,a,ε), (s,a)), ((s,b,ε), (s,a)), ((s,a,ε), (f,ε)), ((f,a,a), (f,ε)), ((f,b,a), (f,ε))}
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 accepted.
Thus in our question, option (B) is aabab having 'b' in the middle and thus can't be accepted.
Question 264 
Let M = {K,Σ,δ,s,F} be a finite state automaton, where
K = {A,B}, Σ = {a,b}, s = A, F = {B}, δ(A,a) = A, δ(A,b) = B, δ(B,a) = B and δ(B,a) = A
A grammar to generate the language accepts by M can be specified as G = (V,Σ,R,S), where V = K∪Σ, and S = A.
Which one of the following set to rules will make L(G) = L(M)?
{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 265 
 Consider the following two statements about regular languages: S_{1}: Every infinite regular language contains an undecidable language as a subset. S_{2}: Every finite language is regular. Which one of the following choices is correct.?
Only S_{2}is true.  
Both S_{1}and S_{2}are true.  
Only S_{1}is true.  
Neither S_{1}nor S_{2}is true. 

S1 is true. We can solve this intuitively.
Suppose L=(a+b)* i.e, sigma*
We know that this is a regular language and any language is subset of this language.
As we know so many undecidable languages (not recursive languages) exist, hence S1 is true.
Take another example:
L=a* which is regular and infinite.
Take its subset L1=an  n> 0 and n is a set such that it cannot be generated by any algorithm
I.e, n is a set of natural numbers which does not have any algorithm which can generate this
So L1 is a undecidable language.
L2 is true as every finite language is regular.
Question 266 
The number of strings of length 100 accepted by the above pushdown automaton is ______
50 
Question 267 
L_{1}=〈M〉M takes more than 2021 steps on all inputs
L_{2}=〈M〉M takes more than 2021 steps on some input
Which one of the following options is correct?
Both L_{1}and L_{2} are undecidable.  
L_{1}is undecidable and L_{2}is decidable.  
L_{1}is decidable and L_{2}is undecidable.  
Both L_{1}and L_{2} are decidable. 
L1 is decidable.
We can take all strings of length zero to length 2021.
If TM takes more than 2021 steps on above inputs then definitely it will take more than 2021 steps on all input greater than length 2021.
If TM takes less than 2021 steps:
In such a case suppose TM takes less than 2021 steps (let's say 2020 steps ) for string length 2021, 2022, 2023, then definitely TM will take 2020 steps for all input greater than 2023. Hence in both cases it is decidable.
Similarly L2 is also decidable. If we can decide for all inputs then we can decide for some inputs also.
Question 268 
2 
Option A accepts string “01111” which does not end with 011 hence wrong.
Option C accepts string “0111” which does not end with 011 hence wrong.
Option D accepts string “0110” which does not end with 011 hence wrong.
Option B is correct.
The NFA for language in which all strings ends with “011”
">Question 269 
L = {  
L = {  
L = {  
L = { 
Question 270 
L1. L2
 
L1 ∪ L2  
L1 ∩ L2  
L1 − L2 
L1. L2 => regular . CFL == CFL. CFL (as every regular is CFL so we can assume regular as CFL)
Since CFL is closed under concatenation so
CFL. CFL= CFL
Hence
Regular . CFL = CFL is true
L1 ∪ L2 => Regular ∪ CFL = CFL
Regular ∪ CFL = CFL ∪ CFL (as every regular is CFL so we can assume regular as CFL)
Since CFL is closed under union
Hence Regular ∪ CFL = CFL is true
L1 ∩ L2 => Regular ∩ CFL = CFL
Regular languages are closed under intersection with any language
I.e,
Regular ∩ L = L (where L is any language such as CFL, CSL etc)
Hence Regular ∩ CFL = CFL is true
Please note this is a special property of regular languages so we will not upgrade regular into CFL (as we did in S1 and S2). We can directly use these closure properties.
L1 − L2 => Regular − CFL = CFL
=> Regular − CFL = regular ∩ CFL (complement)
Since CFL is not closed under complement so complement of CFL may or may not be CFL
Hence Regular − CFL need not be CFL
For ex:
R= (a+b+c)* and L= {am bn ck  m ≠ n or n ≠ k} which is CFL.
The complement of L = {an bn cn  n>0} which is CSL but not CFL.
So
R − L = (a+b+c)* − {am bn ck  m ≠ n or n ≠ k}
=> (a+b+c)* ∩ L (complement)
=> (a+b+c)* ∩ {an bn cn  n>0}
=> {an bn cn  n>0}
Which is CSL. Hence Regular − CFL need not be CFL.
Question 271 
(0+1 (01*0)*1)*  
(0+11+10(1+00)*01)*  
(0*(1(01*0)*1)*)*  
(0+11+11(1+00)*00)* 
Transition table
0 
1 

>*q0 
q0 
q1 
q1 
q2 
q0 
q2 
q1 
q2 
DFA of divisible by 3
The regular expression will be
Three paths to reach to final state from initial state
Path 1: self loop of 0 on q0
Path 2: q0>q1>q0 hence 11
Path 3: q0>q1>q2>q1>q0 hence 10(1+00)*01
So finally the regular expression will be
(0+11+10(1+00)*01)*
Other regular expression is (if we consider two paths)
Path 1: Path 1: self loop of 0 on q0
Path 2: q0>q1>q2*>q1>q0
Hence regular expression
(0+1 (01*0)*1)*
Another regular expression is (if we consider only one path and remaining part is present inside this path as cycles)
q0>q1>q2>q1>q0
Another regular expression is
(0*(1(01*0)*1)*)*
So A,B, C are correct.
Option D generates string 11100 which is not accepted by FA hence wrong.
Question 272 
L={w x w^{R} x^{R }  w, x ∈ {0,1}* }  
L={w w^{R} x x^{R}  w, x ∈ {0,1}* }  
L={w x x^{R} w^{R}  w, x ∈ {0,1}* }  
L={w x w^{R}  w, x ∈ {0,1}* } 
Option A: L={w x w^{R} x^{R}  w, x ∈ {0,1}* }
This is not CFL as if we push “w” then “x” then we cannot match wR with “w” as top of stack contains x.
Option B: L={w w^{R} x x^{R}  w, x ∈ {0,1}* }
This is CFL. We non deterministically guess the middle of the string. So we push “w” then match with wR and again push x and match with xR
Option C: L={