Theory-of-Computation
Question 1 |
If L is a regular language over Σ = {a,b}, which one of the following languages is NOT regular?
A | Suffix (L) = {y ∈ Σ* such that xy ∈ L} |
B | {wwR │w ∈ L} |
C | Prefix (L) = {x ∈ Σ*│∃y ∈ Σ* such that xy ∈ L} |
D | L ∙ LR = {xy │ x ∈ L, yR ∈ L} |
Question 2 |
For Σ = {a,b}, let us consider the regular language L = {x|x = a2+3k or x = b10+12k, k ≥ 0}. Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for L?
A | 3 |
B | 9 |
C | 5 |
D | 24 |
For any language L, there exists an integer n, such that for all x ∈ L with |x| ≥ n, there exists u,v, w ∈ Σ*, such that x = uvw, and
(1) |uv| ≤ n
(2) |v| ≥ 1
(3) for all i ≥ 0: uviw ∈ L
We have to find “n” which satisfies for all the strings in L.
Considering strings derived by b10+12k.
The minimum string in L = “bbbbbbbbbb” but this string b10 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 non-regular languages over the alphabet {0,1}
Which of the above sets are uncountable?
A | S2 and S3 |
B | S3 and S4 |
C | S1 and S4 |
D | S1 and S2 |
S2 is countable, since a valid C program represents a valid algorithm and every algorithm corresponds to a Turing Machine, so S2 is equivalent to set of all Turing Machines.
S3 is is uncountable, it is proved by diagonalization method.
S4 is uncountable, as set of non-regular 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 context-free?
A | {wwR |w ∈ {a,b}*} |
B | {wanwRbn |w ∈ {a,b}*, n ≥ 0} |
C | {anbi | i ∈ {n, 3n, 5n}, n ≥ 0} |
D | {wanbnwR |w ∈ {a,b}*, n ≥ 0} |
This is similar to language
L = {anbmcndm | n, m > 0}
Suppose we push “w” then an and then wR, now we cannot match bn with an, because in top of stack we have wR.
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 = x1 x2 … xn ∈ Σn, n ≥ 0. Let π(x) = x1 º x2 º … º xn.
Consider the language L = {x ∈ Σ* | π(x) = id}. The minimum number of states in any DFA accepting L is ______.
A | 120 |
B | 136 |
C | 125 |
D | 132 |
Question 6 |
Let N be an NFA with n states. Let k be the number of states of a minimal DFA which is equivalent to N. Which one of the following is necessarily true?
A | k ≥ 2n |
B | k ≥ n |
C | k ≤ n2 |
D | k ≤ 2n
|
In other words, if number of states in NFA is “n” then the corresponding DFA have at most 2n states.
Hence k ≤ 2n is necessarily true.
Question 7 |
The set of all recursively enumerable languages is
A | closed under complementation. |
B | closed under intersection. |
C | a subset of the set of all recursive languages. |
D | an uncountable set. |
Recursive enumerable languages are not closed under Complementation.
Recursive enumerable languages are a countable set, as every recursive enumerable language has a corresponding Turing Machine and set of all Turing Machine is countable.
Recursive languages are subset of recursive enumerable languages.
Question 8 |
L0 = {ε}
Li = Li-1∙L for all i>0
The order of a language L is defined as the smallest k such that Lk = Lk+1.
Consider the language L1 (over alphabet 0) accepted by the following automaton.

The order of L1 is ______.
A | 2 |
B | 3 |
C | 4 |
D | 5 |
Now L10 = ϵ and L11 = ϵ . (ϵ+0 (00)*) = ϵ + 0 (00)* = L1
Now L12 = L11 .
L1 = L1 .
L1 = (ϵ + 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 L13 = L12 .
L1 = 0* (ϵ + 0 (00)*) = 0* + 0*0(00)* = 0*
Hence L12 = L13
Or L12 = L12+1 ,
hence the smallest k value is 2.
Question 9 |
I. {am bn cp dq ∣ m + p = n + q, where m, n, p, q ≥ 0}
II. {am bn cp dq ∣ m = n and p = q, where m, n, p, q ≥ 0}
III. {am bn cp dq ∣ m = n = p and p ≠ q, where m, n, p, q ≥ 0}
IV. {am bn cp dq ∣ mn = p + q, where m, n, p, q ≥ 0}
Which of the above languages are context-free?
A | I and IV only |
B | I and II only |
C | II and III only |
D | II and IV only |
m-n = q-p
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) am bn cp dq | 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) am bn cp dq | 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 G1 and G2 whether L(G1) = L(G2)
(IV) Given an NFA N, whether there is a deterministic PDA P such that N and P accept the same language
Which one of the following statement is correct?
A | Only I and II are undecidable |
B | Only III is undecidable |
C | Only II and IV are undecidable |
D | Only I, II and III are undecidable |
I, II and III is undecidable.
Question 11 |
S → abScT | abcT
T → bT | b
Which one of the following represents the language generated by the above grammar?
A | {(ab)n (cb)n│n ≥ 1} |
B | {(ab)n cb(m1 ) cb(m2 )…cb(mn )│n,m1,m2,…,mn ≥ 1} |
C | {(ab)n (cbm)n│m,n ≥ 1} |
D | {(ab)n (cbn)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,m1,m2,…,mn ≥ 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 finite-state automation (DFA) accepting L is _________.
A | 4 |
B | 5 |
C | 6 |
D | 7 |

After converting the NFA into DFA:

After converting the NFA into DFA:

Question 13 |
S → SaS | aSb | bSa | SS | ϵ
where S is the start variable, then which one of the following strings is not generated by G?
A | abab |
B | aaab |
C | abbaa |
D | babba |

But the string “babba” can’t be generated by the given grammar.
The reason behind this is, we can generate any number of a’s with production S→ SaS, but for one “b” we have to generate one “a”, as the production which is generating “b” is also generating “a” together (S→ aSb and S→ bSa).
So in string “babba” the first and last “ba” can be generated by S→ bSa, but we can’t generate a single “b” in middle.
In other words we can say that any string in which number of “b’s” is more than number of “a’s” can’t be generated by the given grammar.
Question 14 |
G1: S → aSb|T, T → cT|ϵ
G2: S → bSa|T, T → cT|ϵ
The language L(G1) ∩ L(G2) is
A | Finite |
B | Not finite but regular |
C | Context-Free but not regular |
D | Recursive but not context-free |
{ϵ, c, cc, ccc, … ab, aabb, aaabbb….acb, accb… aacbb, aaccbb, …}
Strings generated by G2:
{ϵ, c, cc, ccc, … ba, bbaa, bbbaaa….bca, bcca… bbcaa, bbccaa, …}
The strings common in L (G1) and L (G2) are:
{ϵ, c, cc, ccc…}
So, L (G1) ∩ L (G2) can be represented by regular expression: c*
Hence the language L (G1) ∩ L (G2) is “Not finite but regular”.
Question 15 |
Let L1 = {an bn cm│m,n ≥ 0} and L2 = {am bn cn│m,n ≥ 0}
Which of the following are context-free languages?
I. L1 ∪ L2
II. L1 ∩ L2
A | I only |
B | II only |
C | I and II |
D | Neither I nor II |
Strings in L2 = {ϵ, a, aa, …., bc, bbcc,…., abc, aabc,…, abbcc, aabbcc, aaabbcc,..}
Strings in L1 ∪ L2 ={ϵ, a, aa, .., c, cc,.. ab, bc, …, aabb, bbcc,.., abc, abcc, aabc,…}
Hence (L1 ∪ L2) will have either (number of a’s = equal to number of b’s) OR (number of b’s = number of c’s).
Hence (L1 ∪ L2) is CFL.
Strings in L1 ∩ L2 = {ϵ, abc, aabbcc, aaabbbccc,…}
Hence (L1 ∩ L2) will have (number of a’s = number of b’s = number of c’s)
i.e., (L1 ∩ L2) = {anbncn | 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 Lf denote the language {x # f(x)│x ∈ A*}. Which of the following statements is true:
A | f is computable if and only if Lf is recursive. |
B | f is computable if and only if Lf is recursively enumerable. |
C | If f is computable then Lf is recursive, but not conversely. |
D | If f is computable then Lf 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 Lf is recursive.
Question 17 |
Let L1, L2 be any two context-free languages and R be any regular language. Then which of the following is/are CORRECT?

A | I, II and IV only |
B | I and III only |
C | II and IV only |
D | I only |
CFL is not closed under complementation.
So L1 compliment may or may not be CFL. Hence

L1 – R means


Regular language is closed with intersection with any language, i.e. L∩R is same type as L.
So L1∩R is context free.
CFL is not closed under INTERSECTION, so L1 ∩ L2 may or may not be CFL and hence IVth is false.
Question 18 |
Identify the language generated by the following grammar, where S is the start variable.
S → XY X → aX|a Y → aYb|ϵ
A | {am bn │ m ≥ n, n > 0} |
B | {am bn │ m ≥ n, n ≥ 0} |
C | {am bn │ m > n, n ≥ 0} |
D | {am bn │ 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 {am bn│m>n,n≥0}.
Question 19 |
The minimum possible number of a deterministic finite automation that accepts the regular language L = {w1aw2 | w1, w2 ∈ {a,b}*, |w1| = 2,|w2| ≥ 3} is _________.
A | 8 |
B | 9 |
C | 10 |
D | 11 |
So we have four possibilities of w1 = {aa, ab, ba, bb}.
|w2 | ≥ 3 means the w2 will have at least three length string from {a,b}.
w2 will have {aaa, aab, aba, abb, baa, bab, bba, bbb, ……….}
So, the required DFA is

Question 20 |
Let δ denote the transition function and denote the extended transition function of the ε-NFA whose transition table is given below:

Then is
A | ∅ |
B | {q0,q1,q3} |
C | {q0,q1,q2} |
D | {q0,q2,q3} |
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 q2, from q2, transition with input “a” is dead so we have to use epsilon transition to go to other state.
With epsilon transition we reach to q0, at q0 we have a transition with input symbol “a” so we reach to state q1.
From q1, we can take transition with symbol “b” and reach state q2 but from q2, again we have no further transition with symbol “a” as input, so we have to take another transition from state q1, that is, the epsilon transition which goes to state q2.
From q2 we reach to state q0 and read input “b” and then read input “a” and reach state q1. So q1 is one of the state of extended transition function.
From q1 we can reach q2 by using epsilon transition and from q2 we can reach q0 with epsilon move so state q2 and q0 are also part of extended transition function.
So state q0,q1,q2.
Question 21 |
L1= {ap│p is a prime number}
L2= {anbmc2m| n ≥ 0, m ≥ 0}
L3= {anbnc2n│ n ≥ 0}
L4= {anbn│ n ≥ 1}
Which of the following are CORRECT?
I. L1 is context-free but not regular.
II. L2 is not context-free.
III. L3 is not context-free but recursive.
IV. L4 is deterministic context-free.
A | I, II and IV only |
B | II and III only |
C | I and IV only |
D | III and IV only |
L2 = {an bm c2m│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 L2 is Context free and II is true.
L3 = {an bn c2n│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
L4 = {an bn│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 context-free grammar G, is L(G) = ∅?
III. Given a context-free grammar G, is L(G) = Σ* for some alphabet Σ?
IV. Given a Turing machine M and a string w, is w ∈ L(M)?
A | I and IV only |
B | II and III only |
C | II, III and IV only |
D | III and IV only |
Emptiness problem for Context free language is decidable, so II is decidable.
Completeness problem (i.e. L(G) = Σ* for a CFG G) is undecidable.
Membership problem for recursive enumerable language (as language of Turing Machine is recursive enumerable) is undecidable.
So IV is undecidable.
Question 23 |
Which of the following languages is generated by the given grammar?
A | {anbm |n,m ≥ 0} |
B | {w ∈ {a,b}* | w has equal number of a’s and b’s} |
C | {an |n ≥ 0}∪{bn |n ≥ 0}∪{an b(sup>n|n ≥ 0} |
D | {a,b}* |

Question 24 |
I. Given NFAs N1 and N2, is L(N1)∩L(N2)= Φ?
II. Given a CFG G = (N,Σ,P,S) and a string x ∈ Σ*, does x ∈ L(G)?
III. Given CFGs G and G2, is L(G1) = L(G2)?
IV. Given a TM M, is L(M) = Φ?
A | I and IV only |
B | II and III only |
C | III and IV only |
D | II and IV only |
Statement II is decidable, as for CFG we have membership algorithm, hence it is decidable.
But for problems in statement III and IV, there doesn’t exist any algorithm which can decide it.
Question 25 |
Which one of the following regular expressions represents the language: the set of all binary strings having two consecutive 0s and two consecutive 1s?
A | (0 + 1)* 0011(0 + 1)* + (0 + 1)* 1100(0 + 1)* |
B | (0 + 1)* (00(0 + 1)* 11 + 11(0 + 1)* 00)(0 + 1)* |
C | (0 + 1)* 00(0 + 1)* + (0 + 1)* 11(0 + 1)* |
D | 00(0 + 1)* 11 + 11(0 + 1)* 00 |
Option C generates string “00” which doesn’t have two consecutive 1’s.
Option D doesn’t generate string “00110” which has two consecutive 0’s and two consecutive 1’s.
Question 26 |
Consider the following context-free grammars:
G1: S → aS|B, B → b|bB G2: S → aA|bB, A → aA|B|ε, B → bB|ε
Which one of the following pairs of languages is generated by G1 and G2, respectively?
A | {am bn│m > 0 or n > 0} and {am bn |m > 0 and n > 0} |
B | {am bn│m > 0 and n > 0} and {am bn |m > 0 or n≥0} |
C | {am bn│m≥0 or n > 0} and {am bn |m > 0 and n > 0} |
D | {am bn│m≥0 and n > 0} and {am bn |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→b|bB
G2:
By using S→aA and then A→aA | ϵ we can have only any number of a’s (greater than zero) OR we can use A→B and B→bB | ϵ to add any number of b’s after a’s OR by using S→bB and B→bB | ϵ we can have only any number of b’s (greater than zero).
Question 27 |
Consider the transition diagram of a PDA given below with input alphabet Σ = {a,b} and stack alphabet Γ = {X,Z}. Z is the initial stack symbol. Let L denote the language accepted by the PDA.

Which one of the following is TRUE?
A | L = {an bn│n ≥ 0} and is not accepted by any finite automata |
B | L = {an |n≥0} ∪ {anbn|n ≥ 0} and is not accepted by any deterministic PDA |
C | L is not accepted by any Turing machine that halts on every input |
D | L = {an |n ≥ 0} ∪ {an bn |n ≥ 0} and is deterministic context-free |
where q0 and q2 are final states.
This PDA accepts the string by both ways i.e. by using q0 accepts as final state and by using q2 it accepts as empty stack.
Since q0 is initial as well as final state, so it can accept any number of a’s (including zero a’s) and by using q2 as empty stack it accept strings which has equal number of a’s and b’s (b’s comes after a’s).
Hence, L = {an | n≥0} ∪ { an bn | 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 many-one reduction). Which one of the following statements is TRUE?
A | W can be recursively enumerable and Z is recursive. |
B | W can be recursive and Z is recursively enumerable. |
C | W is not recursively enumerable and Z is recursive. |
D | W is not recursively enumerable and Z is not recursive. |
If A ≤ p B
Rule 1: If B is recursive then A is recursive
Rule 2: If B is recursively enumerable then A is recursively enumerable
Rule 3: If A is not recursively enumerable then B is not recursively enumerable
Since X is recursive and recursive language is closed under compliment, so is also recursive.
: By rule 3, W is not recursively enumerable.
: By rule 1, Z is recursive.
Hence, W is not recursively enumerable and Z is recursive.
Question 29 |
The number of states in the minimum sized DFA that accepts the language defined by the regular expression
A | 2 |
B | 3 |
C | 4 |
D | 5 |
So, the DFA has two states.

Question 30 |
Language L2 is defined by the grammar: S2 → abS2|ε
Consider the following statements:
P: L1is regular
Q: L2is regular
Which one of the following is TRUE?
A | Both P and Q are true |
B | P is true and Q is false |
C | P is false and Q is true |
D | Both P and Q are false
|
So, in order to compare equality between a’s and b’s memory (stack) is required.
Hence, L1 is not regular.
Moreover, L1 = {an bn | n ≥ 0} which is DCFL.
The language L2 generated by grammar contains repetition of “ab” i.e. L2 = (ab)* which is clearly a regular language.
Question 31 |
Consider the following types of languages: L1: Regular, L2: Context-free, L3 : Recursive, L4 : Recursively enumerable. Which of the following is/are TRUE?

A | I only |
B | I and III only |
C | I and IV only |
D | I, II and III only |

L3 is recursive, so


L4 is recursive enumerable.
So

II.

L2 is context free, so L2 is recursive.
Since L2 is recursive. So

L3 is recursive.
So

III.

L1 is regular, so L1* is also regular.
L2 is context free.
So, L1*∩L2 is also context free (closed under regular intersection).
IV.

L1 is regular.
L2 is context free, so

So,

Hence, answer is (D).
Question 32 |
I. If all states of an NFA are accepting states then the language accepted by the NFA is Σ*.
II. There exists a regular language A such that for all languages B, A∩B is regular.
Which one of the following is CORRECT?
A | Only I is true |
B | Only II is true |
C | Both I and II are true |
D | Both I and II are false |
The reason is NFA doesn’t have dead state, so even though all states are final state in NFA, the NFA will reject some strings.
For ex:
Consider L = a*b*
The NFA would be:

Even though all states are final states in above NFA, but it doesn’t accept string “aba”.
Hence its language can’t be ∑*.
Statement II is true:
Since A= Φ is a regular language and its intersection with any language B will be Φ (which is regular).
Question 33 |
L1 = {an bm cn+m: m,n ≥ 1}
L2= {an bn c2n: n ≥ 1}
Which one of the following is TRUE?
A | Both L1 and L2 are context-free. |
B | L1 is context-free while L2 is not context-free. |
C | L2 is context-free while L1 is not context-free. |
D | Neither L1 nor L2 is context-free. |
At the end if input and stack is empty then accept.
Hence, it is CFL.
But L2 can’t be recognized by PDA, i.e. by using single stack.
The reason is, it has two comparison at a time,
1st comparison:
number of a’s = number of b’s
2nd comparison:
number of c’s must be two times number of a’s (or b’s)
It is CSL.
Question 34 |
L1 = {〈M〉|M takes at least 2016 steps on some input},
L2 = {〈M〉│M takes at least 2016 steps on all inputs} and
L3 = {〈M〉|M accepts ε},
where for each Turing machine M, 〈M〉 denotes a specific encoding of M. Which one of the following is TRUE?
A | L1 is recursive and L2, L3 are not recursive |
B | L2 is recursive and L1, L3 are not recursive |
C | L1, L2 are recursive and L3 is not recursive |
D | L1, L2, L3 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).
L2 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).
L3 is not recursive:
If L3 is recursive then we must have a Turing machine for L3, which accept epsilon and reject all strings and always HALT.
Since Halting of Turing machine can’t be guaranteed in all the case.
Hence this language is not recursive.
Question 35 |
int a[10][3];
The grammars use D as the start symbol, and use six terminal symbols int; id[] num.
Grammar G1 Grammar G2
D → intL; D → intL;
L → id[E L → idE
E → num] E → E[num]
E → num][E E → [num]
Which of the grammars correctly generate the declaration mentioned above?
A | Both G1 and G2 |
B | Only G1 |
C | Only G2 |
D | Neither G1 nor G2 |

Question 36 |
For any two languages L1 and L2 such that L1 is context-free and L2 is recursively enumerable but not recursive, which of the following is/are necessarily true?

A | I only |
B | III only |
C | III and IV only |
D | I and IV only |

This one is true, because L1 is context free which is nothing but recursive, recursive language is closed under complement hence true.
2 ⇒

If L2 and


Hence option 2 is false
3 ⇒

Which is false because context free language does not closed under complement
4 ⇒


Every recursive language is also recursive enumerable
L2 ⇒ recursive enumerable

Because recursive enumerable language closed under union.
Question 37 |

Consider the DFAs M and N given above. The number of states in a minimal DFA that accepts the language L(M) ∩ L(N) is __________.
A | 1 |
B | 2 |
C | 3 |
D | 4 |
Question 38 |
Consider the NPDA 〈Q = {q0, q1, q2}, Σ = {0, 1}, Γ = {0, 1, ⊥}, δ, q0, ⊥, F = {q2}〉, where (as per usual convention) Q is the set of states, Σ is the input alphabet, Γ is stack alphabet, δ is the state transition function, q0 is the initial state, ⊥ is the initial stack symbol, and F is the set of accepting states, The state transition is as follows:

A | 10110 |
B | 10010 |
C | 01010 |
D | 01001 |
Question 39 |
Consider two decision problems Q1, Q2 such that Q1 reduces in polynomial time to 3-SAT and 3 -SAT reduces in polynomial time to Q2. Then which one of following is consistent with the above statement?
A | Q1 is in NP, Q2 in NP hard |
B | Q1 is in NP, Q2 is NP hard |
C | Both Q1 and Q2 are in NP |
D | Both Q1 and Q2 are NP hard |
Q1≤p 3-SAT≤p Q2 ≤p ≤p hence → Q1 is in NP
but Q2 is not given in NP
Hence Q2 is in NP-Hard.
Question 40 |
Consider the following statements:
-
I. The complement of every Turning decidable language is Turning decidable
II. There exists some language which is in NP but is not Turing decidable
III. If L is a language in NP, L is Turing decidable
Which of the above statements is/are True?
A | Only II |
B | Only III |
C | Only I and II |
D | Only I and III |
Turing decidable language are recursive language which is closed under complementation.
II. False.
All language which is in NP are turing decidable.
III. True.
Question 41 |
Which of the following language is/are regular ?
- L1: {wxwR ⎪ w, x ∈ {a, b}* and ⎪w⎪, ⎪x⎪ >0} wR is the reverse of string w
L2: {anbm ⎪m ≠ n and m, n≥0}
L3: {apbqcr ⎪ p, q, r ≥ 0}
A | L1 and L3 only |
B | L2 only |
C | L2 and L3 only |
D | L3 only |
L2: In this number of a’s is dependent on number of b’s. So PDA is needed.
L3: Any number of a’s followed by any number of b’s followed by any number of c’s. Hence Regular.
Question 42 |
The number of states in the minimal deterministic finite automaton corresponding to the regular expression (0 + 1) * (10) is __________.
A | 3 |
B | 4 |
C | 5 |
D | 6 |

No. of states in minimal DFA is 3.
Question 43 |
Consider alphabet ∑ = {0, 1}, the null/empty string λ and the sets of strings X0, X1 and X2 generated by the corresponding non-terminals of a regular grammar. X0, X1 and X2 are related as follows:
-
X0 = 1 X1
X1 = 0 X1 + 1 X2
X2 = 0 X1 + {λ}
Which one of the following choices precisely represents the strings in X0?
A | 10(0* + (10*)* 1 |
B | 10(0* + (10)*)* 1 |
C | 1(0 + 10)* 1 |
D | 10(0 + 10)* 1 + 110(0 + 10)* 1 |

From the given diagram we can write,
X0 = 1(0+10)* 1
Question 44 |
Let L be the language represented by the regular expression Σ*0011Σ* where Σ = {0,1}. What is the minimum number of states in a DFA that recognizes (complement of L)?
A | 4 |
B | 5 |
C | 6 |
D | 8 |

So, 5 states are there.
Question 45 |
Language L1 is polynomial time reducible to language L2. Language L3 is polynomial time reducible to L2, which in turn is polynomial time reducible to language L4. Which of the following is/are True?
- I. If L4 ∈ P, L2 ∈ P
II. If L1 ∈ P or L3 ∈ P, then L2 ∈ P
III. L1 ∈ P, if and only if L3 ∈ P
IV. If L4 ∈ P, then L1 ∈ P and L3 ∈ P
A | II only |
B | III only |
C | I and IV only |
D | I only |
L1 ≤ pL2
If L4 ∈ P then L2 ∈ P hence L1 ∈ P, hence option C.
Question 46 |
Which of the following languages are context-free?
- L1 = {ambnanbm ⎪ m, n ≥ 1}
L2 = {ambnambn ⎪ m, n ≥ 1}
L3 = {ambn ⎪ m = 2n + 1}
A | L1 and L2 only |
B | L1 and L3 only |
C | L2 and L3 only |
D | L3 only |
L2: 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.
L3: First simply read one ‘a’, then push one ‘a’ in the stack after reading two a’s and then pop all the a’s by reading the b’s. Since can be done by PDA hence CFL.
Question 47 |
Which one of the following is TRUE?
A | The language L={an bn│n≥0} is regular. |
B | The language L={an│n is prime} is regular. |
C | The language L={w│w has 3k+1b’s for some k∈N with Σ={a,b} } is regular. |
D | The language L={ww│w∈Σ* with Σ={0,1} } is regular. |
L = {an | n is prime} is CSL, as calculation of “n is prime” can be done by LBA (Turing machine)
L = {ww | w ∈ ∑*} is CSL.
But L = { w | w has 3k+1 b’s for some k ∈ natural number} is regular.
Lets take values of k={1,2,3,….}
So number of b’s will be {4, 7, 10,……….} and number of a’s can be anything.
The DFA will be

Question 48 |
Consider the finite automaton in the following figure.

What is the set of reachable states for the input string 0011?
A | {q0, q1, q2} |
B | {q0, q1} |
C | {q0, q1, q2, q3} |
D | {q3} |
{q0 , 0 → q0} , { q0 , 0 → q0 }, {q0 , 1 → q0}, {q0 , 1 → q1} . Hence δ (q0, 0011) = q1
{q0 , 0 → q0} , { q0 , 0 → q0 }, {q0 , 1 → q1}, {q1 , 1 → q2} . Hence δ (q0, 0011) = q2
Hence δ (q0, 0011) = {q0, q1, q2}
Question 49 |
If L1 = {an|n≥0} and L2 = {bn|n≥0}, consider
-
(I) L1·L2 is a regular language
(II) L1·L2 = {anbn|n≥0}
Which one of the following is CORRECT?
A | Only (I) |
B | Only (II) |
C | Both (I) and (II) |
D | Neither (I) nor (II) |
Since L1 and L2 both are regular languages and regular languages are closed under concatenation. So their concatenation (i.e., L1⋅ L2) must also be a regular language.
So, L1⋅L2 = { anbn | n ≥ 0}
Hence, statement (i) is True but statement (ii) is False.
Question 50 |
Let A≤mB denotes that language A is mapping reducible (also known as many-to-one reducible) to language B. Which one of the following is FALSE?
A | If A≤m B and B is recursive then A is recursive. |
B | If A≤m Band A is undecidable then B is undecidable. |
C | If A≤m Band B is recursively enumerable then A is recursively enumerable. |
D | If A≤m B and B is not recursively enumerable then A is not recursively enumerable. |
Rule 1: If B is recursive then A is recursive.
Rule 2: If B is recursively enumerable then A is recursively enumerable.
Rule 3: If A is not recursively enumerable then B is not recursively enumerable.
Rule 4: If A is undecidable then B is undecidable.
Other than these rules, all conclusion are false.