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}
       Theory-of-Computation       Regular-Language       GATE 2019       Video-Explanation
Question 1 Explanation: 
wwR cannot be recognized without using stack, so it cannot be regular.
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
       Theory-of-Computation       Regular-Language       GATE 2019       Video-Explanation
Question 2 Explanation: 
Pumping Lemma for Regular Languages:
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
       Theory-of-Computation       Countability       GATE 2019       Video-Explanation
Question 3 Explanation: 
S1 is countable, set of all recursively enumerable languages means set of all Turing machines and we can enumerate TM and have one to one correspondence between natural number.
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}
       Theory-of-Computation       Context-Free-Language       GATE 2019       Video-Explanation
Question 4 Explanation: 
{wanwRbn |w ∈ {a,b}*, n ≥ 0} cannot be CFL.
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
       Theory-of-Computation       Finite-Automata       GATE 2019       Video-Explanation
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
       Theory-of-Computation       Finite-Automata       GATE 2018       Video-Explanation
Question 6 Explanation: 
The number of states in DFA is always less than equal to 2no. of states in NFA.
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.
       Theory-of-Computation       Closure-Property       GATE 2018       Video-Explanation
Question 7 Explanation: 
Recursive enumerable languages are closed under intersection.
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
Given a language L, define Li as follows:
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
       Theory-of-Computation       Finite-Automata       GATE 2018       Video-Explanation
Question 8 Explanation: 
The regular expression for L1 : ϵ + 0 (00)*
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
Consider the following languages:
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
       Theory-of-Computation       Context-Free-Language       GATE 2018       Video-Explanation
Question 9 Explanation: 
i) am bn cp dq | m+p = n+q,
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
Consider the following problems. L(G) denotes the language generated by a grammar G. L(M) denotes the language accepted by a machine M.
(I) For an unrestricted grammar G and a string w, whether w∈L(G)
(II) Given a Turing machine M, whether L(M) is regular
(III) Given two grammar 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
       Theory-of-Computation       Decidability-and-Undecidability       GATE 2018       Video-Explanation
Question 10 Explanation: 
IV is trivial property, as every regular language is CFL also, so a language which has NFA must be regular and for every regular language we can have a deterministic PDA (as every regular language is DCFL).
I, II and III is undecidable.
Question 11
Consider the following context-free grammar over the alphabet Σ = {a, b, c} with S as the start symbol:
S → abScT | abcT
T → bT | b
Which one of the following represents the language generated by the above grammar?
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}
       Theory-of-Computation       Contest-Free-Grammar       GATE 2017 [Set-1]       Video-Explanation
Question 11 Explanation: 
T→ bT | b, this production will generate any number of b’s > 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
       Theory-of-Computation       Finite-Automata       GATE 2017 [Set-1]       Video-Explanation
Question 12 Explanation: 
The NFA for regular expression: (a+b)*b(a+b)

After converting the NFA into DFA:

After converting the NFA into DFA:
Question 13
If G is a grammar with productions
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
       Theory-of-Computation       Membership-Function       GATE 2017 [Set-1]       Video-Explanation
Question 13 Explanation: 
The strings “abab”, “aaab” and “abbaa” can be generated by the given grammar.

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
Consider the context-free grammars over the alphabet {a, b, c} given below. S and T are non-terminals.
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
       Theory-of-Computation       Context-Free-Language       GATE 2017 [Set-1]       Video-Explanation
Question 14 Explanation: 
Strings generated by G1:
{ϵ, 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
Consider the following languages over the alphabet Σ = {a, b, c}.
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
       Theory-of-Computation       Context-Free-Language       GATE 2017 [Set-1]       Video-Explanation
Question 15 Explanation: 
Strings in L1 = {ϵ, c, cc, …., ab, aabb,…., abc, abcc,…, aabbc, aabbcc, aabbccc,..}
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.
       Theory-of-Computation       Computability-and-Decidability       GATE 2017 [Set-1]       Video-Explanation
Question 16 Explanation: 
Total function is synonym of function.
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
       Theory-of-Computation       Context-Free-Language       GATE 2017 [Set-2]       Video-Explanation
Question 17 Explanation: 
Since CFL is closed under UNION so L1 ∪ L2 is CFL, is a true statement.
CFL is not closed under complementation.
So L1 compliment may or may not be CFL. Hence is Context free, is a false statement.
L1 – R means and Regular language is closed under compliment, so
is also a regular language, so we have now L1 ∩ R .
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}
       Theory-of-Computation       Finite-Automata       GATE 2017 [Set-2]       Video-Explanation
Question 18 Explanation: 
The production X→ aX | a can generate any number of a’s ≥ 1 and the production Y→ aYb | ϵ will generate equal number of a’s and b’s.
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
       Theory-of-Computation       DFA       GATE 2017 [Set-2]       Video-Explanation
Question 19 Explanation: 
|w1 | = 2 means the length of w1 is two.
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}
       Theory-of-Computation       NFA       GATE 2017 [Set-2]       Video-Explanation
Question 20 Explanation: 
Extended transition function describes, what happens when we start in any state and follow any sequence of inputs.
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
Consider the following languages:
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
       Theory-of-Computation       Context-Free-Language       GATE 2017 [Set-2]       Video-Explanation
Question 21 Explanation: 
L1 = {ap│p is a prime number} is a context sensitive language. So I is false.
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
Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by a context free grammar G. Let L(M) be the language accepted by a Turing machine M.
Which of the following decision problems are undecidable?
I. Given a regular expression R and a string w, is w ∈ L(R)?
II. Given a 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
       Theory-of-Computation       Decidability-and-Undecidability       GATE 2017 [Set-2]       Video-Explanation
Question 22 Explanation: 
Since membership problem for regular language is decidable, so I is decidable.
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?

S→ aS|bS|ε
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}*
       Theory-of-Computation       Regular-Language       GATE 2016 [Set-1]       Video-Explanation
Question 23 Explanation: 
From the given grammar we can draw the DFA,
Question 24
Which of the following decision problems are undecidable?
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
       Theory-of-Computation       Decidability-and-Undecidability       GATE 2016 [Set-1]       Video-Explanation
Question 24 Explanation: 
Statement I is decidable, as we can make product automata by using N1 and N2 and can decide whether the resulting Product automata’s language is phi or not.
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
       Theory-of-Computation       Regular-Expressions       GATE 2016 [Set-1]       Video-Explanation
Question 25 Explanation: 
Option A doesn’t generate string “001011” as it has two consecutive 0’s and two consecutive 1’s.
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}
       Theory-of-Computation       Membership-Function       GATE 2016 [Set-1]       Video-Explanation
Question 26 Explanation: 
G1:
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
       Theory-of-Computation       Push-Down-Automata       GATE 2016 [Set-1]       Video-Explanation
Question 27 Explanation: 
In this PDA, we can give labels to state as q0, q1, q2
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.
       Theory-of-Computation       Recursive-Enumerable-Languages       GATE 2016 [Set-1]       Video-Explanation
Question 28 Explanation: 
The rules are:
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

(0+1)*(0+1)(0+1)*
is_________.
A
2
B
3
C
4
D
5
       Theory-of-Computation       DFA       GATE 2016 [Set-2]       Video-Explanation
Question 29 Explanation: 
The regular expression generates the min string “0” or “1” and then any number of 0’s and 1’s .
So, the DFA has two states.
Question 30
Language L1 is defined by the grammar: S1 → aS1b|ε
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
       Theory-of-Computation       Regular-Language       GATE 2016 [Set-2]       Video-Explanation
Question 30 Explanation: 
The language L1 generated by the grammar contains equal number of a’s and b’s, but b’s comes after a’s.
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
       Theory-of-Computation       Closure-Property       GATE 2016 [Set-2]       Video-Explanation
Question 31 Explanation: 
I.
L3 is recursive, so is also recursive (because recursive language closed under complementation), so is recursive enumerable.
L4 is recursive enumerable.
So is also recursive enumerable (closed under union).
II.
L2 is context free, so L2 is recursive.
Since L2 is recursive. So is recursive.
L3 is recursive.
So is also recursive (closed under union)
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 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
Consider the following two statements:
I. If all states of an NFA are accepting states then the language accepted by the NFA is Σ*.
II. There exists a regular language A such that for all languages B, A∩B is regular.
Which one of the following 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
       Theory-of-Computation       Regular-and-Finite-Automata       GATE 2016 [Set-2]       Video-Explanation
Question 32 Explanation: 
Statement I is 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
Consider the following languages:
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.
       Theory-of-Computation       Context-Free-Language       GATE 2016 [Set-2]       Video-Explanation
Question 33 Explanation: 
L1 can be recognized by PDA, we have to push a’s and b’s in stack and when c’s comes then pop every symbol from stack for each c’s.
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
Consider the following languages.
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
       Theory-of-Computation       Turing Machine       GATE 2016 [Set-2]       Video-Explanation
Question 34 Explanation: 
L1 is 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
A student wrote two context-free grammars G1 and G2 for generating a single C-like array declaration. The dimension of the array is at least one. For example,
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
       Theory-of-Computation       Membership-Function       GATE 2016 [Set-2]       Video-Explanation
Question 35 Explanation: 
Both grammars G1 and G2 generate C-array like declaration:
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
       Theory-of-Computation       Closure-Property       GATE 2015 [Set-1]
Question 36 Explanation: 
1 ⇒ is recursive,
This one is true, because L1 is context free which is nothing but recursive, recursive language is closed under complement hence true.
2 ⇒ (complement of L2) is recursive
If L2 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 ⇒ ∪L2 is recursive enumerable
⇒ recursive
Every recursive language is also recursive enumerable
L2 ⇒ 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
       Theory-of-Computation       DFA       GATE 2015 [Set-1]
Question 37 Explanation: 
M accepts the strings which end with a and N accepts the strings which end with B. Their intersection should accept empty language.
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
       Theory-of-Computation       PDA       GATE 2015 [Set-1]
Question 38 Explanation: 
In q0 state for ‘1’, a ‘1’ is pushed and for a ‘0’, a ‘0’ is pushed. In q1 state, for a ‘0’ a ‘1’ is popped, and for ‘1’ a ‘0’ is popped. So the given PDA is accepting all strings of form x0(xr)’ or x1(xr)’ or x(xr)’ , where (xr)’ is the complement of reverse of x.
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
       Theory-of-Computation       P-NP       GATE 2015 [Set-2]
Question 39 Explanation: 
3-SAT ⇒ NPC problem
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
       Theory-of-Computation       Decidability-and-Undecidability       GATE 2015 [Set-2]
Question 40 Explanation: 
I. True.
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
       Theory-of-Computation       Regular-Language       GATE 2015 [Set-2]
Question 41 Explanation: 
L1: All strings of length 3 or more with same start and end symbol, as everything in middle is consumed by x as per the definition.
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
       Theory-of-Computation       DFA       GATE 2015 [Set-2]
Question 42 Explanation: 

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
       Theory-of-Computation       Regular-Grammar       GATE 2015 [Set-2]
Question 43 Explanation: 
Convert the given transitions to a state diagram.

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
       Theory-of-Computation       Regular-Expressions       GATE 2015 [Set-3]
Question 44 Explanation: 
No. of states in DFA accepting L and complement of L is same. So let’s draw minimal DFA for L,

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
       Theory-of-Computation       Reducibility       GATE 2015 [Set-3]
Question 45 Explanation: 
L2 ≤ pL4
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
       Theory-of-Computation       Context-Free-Language       GATE 2015 [Set-3]
Question 46 Explanation: 
L1: First push all the a’s in the stack then push all the b’s in the stack. Now pop all the b’s from the stack watching next no. of a’s. And then pop all the a’s from the stack watching next no. of b’s. So can be done by PDA, hence CFL.
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.
       Theory-of-Computation       Regular Languages       GATE 2014 [Set-1]
Question 47 Explanation: 
The Language L= {an bn | n>=0} is CFL but not regular, as it requires comparison between a’s and b’s.
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}
       Theory-of-Computation       Finite-Automata       GATE 2014 [Set-1]
Question 48 Explanation: 
{q0 , 0 → q0} , { q0 , 0 → q0 }, {q0 , 1 → q0}, {q0 , 1 → q0} . Hence δ (q0, 0011) = q0
{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)
       Theory-of-Computation       Regular Languages       GATE 2014 [Set-2]
Question 49 Explanation: 
The regular expression equivalent to L1 and L2 are a* and b* respectively.
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.
       Theory-of-Computation       Reducibility       GATE 2014 [Set-2]
Question 50 Explanation: 
The rules are: 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.
Rule 4: If A is undecidable then B is undecidable.
Other than these rules, all conclusion are false.
There are 50 questions to complete.

Access subject wise (1000+) question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

Register Now