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
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
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
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
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
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
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
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
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. {ambncpdq ∣ m + p = n + q, where m, n, p, q ≥ 0}
    II. {ambncpdq ∣ m = n and p = q, where m, n, p, q ≥ 0}
    III. {ambncpdq ∣ m = n = p and p ≠ q, where m, n, p, q ≥ 0}
    IV. {ambncpdq ∣ 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
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
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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 = {an bm c2m | n ≥ 0, m ≥ 0}
    L3 = {an bn c2n │ n ≥ 0}
    L4 = {an bn │ 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]
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]
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]
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 G1 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]
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]
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]
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]
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]
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]
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: L1 is regular
    Q: L2 is regular

Which one of the following is TRUE?

A
Both P and Q are true
B
P is true and Q is false
C
P is false and Q is true
D
Both P and Q are false
       Theory-of-Computation       Regular-Language       GATE 2016 [Set-2]
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]
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]
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]
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]
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]
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.
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

A
decidable and recursively enumerable
B
undecidable but recursively enumerable
C
undecidable and not recursively enumerable
D
decidable but not recursively enumerable
       Theory-of-Computation       Turing Machine       GATE 2014 [Set-2]
Question 51 Explanation: 
If L is recursive language then there must exist a Turing Machine which always HALT for every case (either acceptance or rejectance of string). Let the Turing Machine for L is M1.
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 L1 = {w ∈ {0,1}* |w has at least as many occurrences of (110)’s as (011)’s}. Let L2 = {w ∈ {0,1}*|w has at least as many occurrences of (000)’s as (111)’s}. Which one of the following is TRUE?

A
L1 is regular but not L2
B
L2 is regular but not L1
C
Both L1 and L2 are regular
D
Neither nor L1 are L2 regular
       Theory-of-Computation       Regular languages       GATE 2014 [Set-2]
Question 52 Explanation: 
In L1 any string “w” must satisfy the condition:
{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 L2 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* 

A
3
B
4
C
5
D
6
       Theory-of-Computation       Regular Languages and Finite Automata       GATE 2014 [Set-3]
Question 53 Explanation: 
The regular expression generate all the strings of length 0 , 1 and 2
{ϵ, 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 non-empty alphabet and let 2Σ* be the power set of Σ*. Which one of the following is TRUE?

A
Both 2Σ* and Σ* are countable
B
2Σ* is countable and Σ* is uncountable
C
2Σ* is uncountable and Σ* is countable
D
Both 2Σ* and Σ* are uncountable
       Theory-of-Computation       Decidability-and-Undecidability       GATE 2014 [Set-3]
Question 54 Explanation: 
If = {0,1} then Σ* = {ϵ, 0, 1, 00, 01, 10, 11, 000, ...............}
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?

A
Deciding if a given context-free grammar is ambiguous.
B
Deciding if a given string is generated by a given context-free grammar.
C
Deciding if the language generated by a given context-free grammar is empty.
D
Deciding if the language generated by a given context-free grammar is finite.
       Theory-of-Computation       Unecidability       GATE 2014 [Set-3]
Question 55 Explanation: 
The problem, whether a given CFG is ambiguous is undecidable, as we don’t have any algorithm which decides it.
We have a membership algorithm which decides that whether a given string is generated by a given context-free grammar. Similarly, the problems, whether the language generated by a given context-free grammar is empty and the language generated by a given context-free 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 pre-specified 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 _____.

A
150
B
151
C
152
D
153
       Theory-of-Computation       Time-Complexity       GATE 2014 [Set-3]
Question 56 Explanation: 
T(k) is the smallest no. of steps needed to move from k to 100.
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}:

    L1 = {0n1n | n≥0}
    L2 = {wcwr | w∈{0,1}*}
    L3 = {wwr | w∈{0,1}*}

Here, wr is the reverse of the string . Which of these languages are deterministic Context-free languages?

A
None of the languages
B
Only L1
C
Only L1 and L2
D
All the three languages
       Theory-of-Computation       Context-Free-and-pushdown-Automata       GATE 2014 [Set-3]
Question 57 Explanation: 
L1 and L2 are DCFL, as we can design DPDA for them. For L1, DPDA will first push all zero’s in stack and when one appears in string, it will pop zero for every one and at the end if input string as well as stack is empty then accept the string else reject the string. Similarly for L2, DPDA will push all the string till it encounter the terminal “c” and once “c” appears in string, DPDA will ignore this “c” and then for every terminal in string (after “c”) it will pop one symbol from stack and match, if matched then pop next and continue. If didn’t match at any stage then reject the string. Since push and pop is clearly defined (i.e., every transition is deterministic), so both L1 and L2 is DCFL.
But in L3, we cannot make DPDA for it, as we cannot locate the middle of string, so DPDA for L3 is not possible. It can be accepted by NPDA only, so L3 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

A
NP-Complete.
B
solvable in polynomial time by reduction to directed graph reachability.
C
solvable in constant time since any input instance is satisfiable.
D
NP-hard, but not NP-complete.
       Theory-of-Computation       NP-Complete       GATE 2014 [Set-3]
Question 58 Explanation: 
Note: Out of Syllabus.
Question 59

Which of the following statements is/are FALSE?

    1. For every non-deterministic 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.
A
1 and 4 only
B
1 and 3 only
C
2 only
D
3 only
       Theory-of-Computation       REL&Turing-Machines       GATE 2013
Question 59 Explanation: 
As we can convert a non-deterministic TM into an equivalent deterministic Turing machine so the statement “for every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine” is true.
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 NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A.
A
1, 2 and 3
B
1 and 2 only
C
2 and 3 only
D
1 and 3 only
       Theory-of-Computation       NP-Complete       GATE 2013
Question 60 Explanation: 
Note: Out of syllabus.
1. Detecting cycle in a graph using DFS takes O(V+E) = O(V2)
Here, for complete graph E <= V2. So, It runs in polynomial time.
2. Every P-problem is NP because P subset of NP (P ⊂ NP)
3. NP – complete ∈ NP.
Hence, NP-complete can be solved in non-deterministic 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 context-free.
    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.
A
1 and 3 only
B
2 and 4 only
C
2 and 3 only
D
3 and 4 only
       Theory-of-Computation       Regular Languages and Finite Automata       GATE 2013
Question 61 Explanation: 
L(A) is regular and its complement is also regular (by closure property) and every regular is CFL also. So Complement of LA is context-free.
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 non-final 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)?
A
3 only
B
3 and 4 only
C
1, 2 and 3 only
D
2 and 3 only
       Theory-of-Computation       Undecidability       GATE 2013
Question 62 Explanation: 
Emptiness problem for context free language is decidable, so 1 is decidable.
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
B
{ε}
C
a*
D
{a ,ε}
       Theory-of-Computation       Finite-Automata       GATE 2012
Question 63 Explanation: 
The Σ= {a} and the given NFA accepts the strings {a, aa, aaa, aaaa, ……….} i.e. the language accepted by the NFA can be represented by the regular expression: {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 context-free language, then, is also context-free?

3) If L is a regular language, then, is also regular?

4) If L is a recursive language, then, is also recursive?

A
1, 2, 3, 4
B
1, 2
C
2, 3, 4
D
3, 4
       Theory-of-Computation       Decidability-and-Undecidability       GATE 2012
Question 64 Explanation: 
The statement “Does a given program ever produce an output?” is same as the statement “Does a Turing Machine will halt for any arbitrary string?”, which is nothing but the “halting problem of Turing Machine”, hence statement 1 is undecidable.
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 non-final states and vice-versa. 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
A
1, 2 and 3
B
2, 3 and 4
C
1, 2 and 4
D
1, 3 and 4
       Theory-of-Computation       Regular Languages       GATE 2012
Question 65 Explanation: 
L* will contain all those strings which can be obtained by any combination (and repetition) of the strings in language i,e, from L= {ab, aa, baa}
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

A
B
C
D
       Theory-of-Computation       Finite-Automata       GATE 2012
Question 66 Explanation: 
All states are final states except “q” which is trap state. The strings in language are such that every substring of 3 symbol has at most two zeros. It means that we cannot have 3 consecutive zeros anywhere in string. In the given DFA total four transition is missing, so we have to create the missing transition keeping the criteria in mind that “three consecutive zeros” will lead to trap state “q” as after 3 consecutive zeros whatever comes after that in the string, the string is going to be rejected by DFA.
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 context-free language such that Q ⊆ P. (For example, let P be the language represented by the regular expression p*q* and Q be [pnqn | n ∈ N]). Then which of the following is ALWAYS regular?

A
P ∩ Q
B
P – Q
C
Σ* – P
D
Σ* – Q
       Theory-of-Computation       Regular-Language       GATE 2011
Question 67 Explanation: 
Exp: Σ* - P is the complement of P so it is always regular,
since regular languages are closed under complementation.
Question 68

Which of the following pairs have DIFFERENT expressive power?

A
Deterministic finite automata (DFA) and Non-deterministic finite automata (NFA)
B
Deterministic push down automata (DPDA) and Non-deterministic push down automata (NFDA)
C
Deterministic single-tape Turning machine and Non-deterministic single tape Turning machine
D
Single-tape Turning machine and multi-tape Turning machine
       Theory-of-Computation       NFA       GATE 2011
Question 68 Explanation: 
NPDA is more powerful than DPDA.
Hence answer is (B).
Question 69

Definition of a language L with alphabet {a} is given as following.

L = {ank| k>0, and n is a positive integer constant}

What is the minimum number of states needed in a DFA to recognize L?

A
k+1
B
n+1
C
2n+1
D
2k+1
       Theory-of-Computation       Finite-Automata       GATE 2011
Question 69 Explanation: 
Given that n is a constant.
So lets check of n = 2,
L = a2k, 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 ank, (n+1) states will be required.
Question 70

Consider the languages L1,L2 and L3 as given below.

    L1 = {0p1q|p,q∈N},
    L2 = {0p1q|p,q∈N and p=q} and
    L3 = {0p1q0r|p,q,r∈N and p=q=r}.

Which of the following statements is NOT TRUE?

A
Push Down Automate (PDA) can be used to recognize L1 and L2
B
L1 is a regular language
C
All the three languages are context free
D
Turing machines can be used to recognize all the languages
       Theory-of-Computation       Identify-Class-Language       GATE 2011
Question 70 Explanation: 
L1: regular language
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?

A
L2 – L1 is recursively enumerable
B
L1 – L3 is recursively enumerable
C
L2 ∩ L1 is recursively enumerable
D
L2 ∪ L1 is recursively enumerable
       Theory-of-Computation       Recursive-Enumerable-Languages       GATE 2010
Question 71 Explanation: 
L2 − L1 means L2 ∩ L1c, since L1 is recursive hence L1c must also be recursive, So L2 ∩ L1c is equivalent to (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 A is always true.
L1 − L3 means L1 ∩ L3c, since recursive enumerable is not closed under complement, so L3c 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?

A
(0*10*1)*
B
0*(10*10*)*
C
0*(10*1*)*0*
D
0*1(10*1)*10*
       Theory-of-Computation       Regular-Expressions       GATE 2010
Question 72 Explanation: 
The best way to find correct answer is option elimination method. We will guess strings which has even number of 1’s and that is not generated by wrong options OR which generate strings which doesn’t have even number of 1’s.
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 = {0i1j | i != j}.
    L2 = {0i1j | i = j}.
    L3 = {0i1j | i = 2j+1}.
    L4 = {0i1j | i != 2j}.

Which one of the following statements is true?

A
Only L2 is context free
B
Only L2 and L3 are context free
C
Only L1 and L2 are context free
D
All are context free
       Theory-of-Computation       Context-Free-Language       GATE 2010
Question 73 Explanation: 
All languages viz L1, L2, L3 and L4 has only one comparison and it can be accepted by PDA (single stack), hence all are Context Free Languages.
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 non-deterministic finite automaton that accepts L?

A
n-1
B
n
C
n+1
D
2n-1
       Theory-of-Computation       Finite-Automata       GATE 2010
Question 74 Explanation: 
In order to accept any string of length “n” with alphabet {0,1}, we require an NFA with “n+1” states. For example, consider a strings of length “3” such as “101”, the NFA with 4 states is given below:

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
S→aSa|bSb|a|b

The language generated by the above grammar over the alphabet {a,b} is the set of

A
all palindromes.
B
all odd length palindromes.
C
strings that begin and end with the same symbol.
D
all even length palindromes.
       Theory-of-Computation       Context-Free-Language       GATE 2009
Question 75 Explanation: 
From the grammar, we can easily infer that it generates all the palindromes of odd length, for ex: strings {aba, bab, aaa, bbb, ….}
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)*?

A
The set of all strings containing the substring 00.
B
The set of all strings containing at most two 0’s.
C
The set of all strings containing at least two 0’s.
D
The set of all strings that begin and end with either 0 or 1.
       Theory-of-Computation       Regular-Expressions       GATE 2009
Question 76 Explanation: 
Option A is false, as the regular expression generates string “010” which doesn’t have “00” as substring. Option B is false, as we can have the string “000” from the given regular expression, which has more than two 0’s. Option D is false, as we cannot generate the string “01” from the given regular expression and according to option D, string “01” must be generated by regular expression, which clearly shows option D is not correct language as per regular expression.
Question 77

Which one of the following is FALSE?

A
There is unique minimal DFA for every regular language.
B
Every NFA can be converted to an equivalent PDA.
C
Complement of every context-free language is recursive.
D
Every non-deterministic PDA can be converted to an equivalent deterministic PDA.
       Theory-of-Computation       NFA       GATE 2009
Question 77 Explanation: 
As we know there are several languages (CFL) for which we only have NPDA, i.e. these languages cannot be recognized by DPDA. For example
L = {wwr | 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?

A
3
B
4
C
5
D
6
       Theory-of-Computation       Finite-Automata       GATE 2009
Question 78 Explanation: 
Consider the below given FSM (represented as graph)

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 = {ambmcanbn | m,n ≥ 0 }
    L2 = {aibjck | i,j,k ≥ 0 }

Then L is

A
Not recursive
B
Regular
C
Context free but not regular
D
Recursively enumerable but not context free
       Theory-of-Computation       Identify-Class-Language       GATE 2009
Question 79 Explanation: 
The strings in L1 are {c, abc, cab, abcab, aabbcab, abcaabb, aabbcaabb,.....} and the strings in L2 are {ϵ, a, b, c, ab, bc, ac, abc, aabc, abbc, abcc, aabbcc, …..}
Clearly, L1 ∩ L2 is {axbx | x ≥0}, which is CFL but not regular.
Question 80

The above DFA accepts the set of all strings over {0,1} that

A
begin either with 0 or 1
B
end with 0
C
end with 00
D
contain the substring 00
       Theory-of-Computation       Finite-Automata       GATE 2009
Question 80 Explanation: 
Option A is false, as the DFA is not accepting the string “10”, option B is false as the DFA is not accepting the string “10” . Option D is false as the DFA doesn’t accept the string “1001” which has “00” as substring. Hence option C , every strings end with “00” is correct.
Question 81

Which of the following is true for the language {ap|p is a prime} ?

A
It is not accepted by a Turing Machine
B
It is regular but not context-free
C
It is context-free but not regular
D
It is neither regular nor context-free, but accepted by a Turing machine
       Theory-of-Computation       Identify-Class-Language       GATE 2008
Question 81 Explanation: 
Finding prime number cannot be done by FA or PDA, so it cannot be regular or CFL. This language can be recognized by LBA, hence it can be accepted by Turing Machine.
Question 82

Which of the following are decidable?

    I. Whether the intersection of two regular languages is infinite
    II. Whether a given context-free language is regular
    III. Whether two push-down automata accept the same language
    IV. Whether a given grammar is context-free
A
I and II
B
I and IV
C
II and III
D
II and IV
       Theory-of-Computation       Decidability-and-Undecidability       GATE 2008
Question 82 Explanation: 
The intersection of two regular languages is always a regular language (by closure property of regular language) and testing infiniteness of regular language is decidable. Hence statement I is decidable.
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 context-free language is regular and whether two push-down automata accept the same language.
Question 83

If L and are recursively enumerable, then L is

A
regular
B
context-free
C
context-sensitive
D
recursive
       Theory-of-Computation       Recursive-Enumerable-Languages       GATE 2008
Question 83 Explanation: 
If L is recursive enumerable, then it implies that there exist a Turing Machine (lets say M1) which always HALT for the strings which is in L.
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?

A
Every NFA can be converted to an equivalent DFA
B
Every non-deterministic Turing machine can be converted to an equivalent deterministic Turing machine
C
Every regular language is also a context-free language
D
Every subset of a recursively enumerable set is recursive
       Theory-of-Computation       Recursive-Enumerable-Languages       GATE 2008
Question 84 Explanation: 
Every NFA can be converted into DFA (as there exist a standard procedure to convert NFA into DFA). Also, every non-deterministic Turing machine can be converted to an equivalent deterministic Turing machine. Every regular language is also a CFL , since if a language can be recognized by Finite automata, then it must also be recognize by PDA (as PDA is more powerful than FA). But every subset of recursively enumerable need not be 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?

A
B
C
D
       Theory-of-Computation       Finite-Automata       GATE 2008
Question 85 Explanation: 
The product automata will have states {11, 12, 21, 22} and “11” is inItial state and “22” is final state. By comparison we can easily infer that state {11, 12, 21, 22} is renamed as {P, Q, S, R}, where P is initial state (state “11”) and R is final state (state “22”).
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 left-recursive grammar can be converted to a right-recursive grammar and vice-versa
    II. All \epsilon productions can be removed from any context-free grammar by suitable transformations
    III. The language generated by a context-free 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 non-terminal), is always regular
    IV. The derivation trees of strings generated by a context-free grammar in Chomsky Normal Form are always binary trees
A
I, II, III and IV
B
II, III and IV only
C
I, III and IV only
D
I, II and IV only
       Theory-of-Computation       Contest-Free-Grammar       GATE 2008
Question 86 Explanation: 
Every left recursive grammar can be converted to a right-recursive grammar and vice-versa, the conversion of a left recursive grammar into right recursive is also known as eliminating left recursion from the grammar.
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:

A
E - P, F - R, G - Q, H - S
B
E - R, F - P, G - S, H - Q
C
E - R, F - P, G - Q, H - S
D
E - P, F - R, G - S, H - Q
       Theory-of-Computation       Match-the-Following       GATE 2008
Question 87 Explanation: 
The grammar in S {X →bXb | cXc | ϵ} derives all even length Palindromes, So H matches with S.
F matches with P, Number of formal parameters in the declaration…. matches with {L = { an bm c n dm | m,n >=1}
Since, an bm 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 cn dm 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 *
A
P-2, Q-1, R-3, S-4
B
P-1, Q-3, R-2, S-4
C
P-1, Q-2, R-3, S-4
D
P-3, Q-2, R-1, S-4
       Theory-of-Computation       Finite-Automata       GATE 2008
Question 88 Explanation: 
The NFA represented by P, accepts string “00” and then at final state (other than initial state) we have self loop of “1” , so we conclude that it must accept the string of the form of -> ϵ + 0 X* 01*, where X is regular expression (01*1 + 00) {resolving the loop at middle state}. It matches with statement 1.
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. {anb2m | n≥0, m≥0}
    II. {anbm | n=2m}
    III. {anbm | n≠2m}
    IV. {xcy | x,y∈{a,b}*}
A
I and IV only
B
I and III only
C
I only
D
IV only
       Theory-of-Computation       Regular Languages       GATE 2008
Question 89 Explanation: 
Statement I represents a regular language whose regular expression is a* (bb)*. Also it doesn’t require any comparison between “a” and “b” , so it can be recognized by DFA and hence regular.
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?

A
Membership problem for CFGs.
B
Ambiguity problem for CFGs.
C
Finiteness problem for FSAs.
D
Equivalence problem for FSAs.
       Theory-of-Computation       Decidability-and-Undecidability       GATE 2007
Question 90 Explanation: 
Whether a given CFG is ambiguous, this problem is undecidable. The reason is there is no algorithm exist for this. Remaining all are decidable.
Question 91

Which of the following is TRUE?

A
Every subset of a regular set is regular.
B
Every finite subset of a non-regular set is regular.
C
The union of two non-regular sets is not regular.
D
Infinite union of finite sets is regular.
       Theory-of-Computation       Regular-Language       GATE 2007
Question 91 Explanation: 
If a set is finite then it must be regular , as every language which contains finite elements is regular. Hence, every finite subset of a non-regular set 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 non-regular sets is not regular, is also a false statement.
For example, consider two CFL’s.
L = {an bn | n ≥ 0} and its complement Lc = {am bn | m ≠ n } U b*a*.
If we take UNION of L and Lc , we will get ∑*, which is regular. Hence the UNION of two non-regular 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

A
15 states
B
11 states
C
10 states
D
9 states
       Theory-of-Computation       Finite-Automata       GATE 2007
Question 92 Explanation: 
Given that number of 0’s and 1’s are divisible by 3 and 5, it means that the number of 0’s and 1’s must be divisible by 15. As the LCM of 3 and 5 is 15, so number of 0’s and 1’s are divisible by 3 and 5 is only possible if of 0’s and 1’s are divisible by 15. Also modulo 3 will leave a remainder of 0,1,2 (3 states required) and modulo 5 will leave remainder of 0,1,2,3,4 (5 states required), so product automata will require (3 × 5=15 states).
Question 93

The language L = {0i21i | i≥0} over the alphabet {0, 1, 2} is: 

A
not recursive.
B
is recursive and is a deterministic CFL.
C
is a regular language.
D
is not a deterministic CFL but a CFL.
       Theory-of-Computation       Identify-Class-Language       GATE 2007
Question 93 Explanation: 
We have to match number 0’s before 2 and number of 1’s after 2, both must be equal in order to string belongs to language. This can be done by deterministic PDA. First we have to push 0’s in stack, when “2” comes , ignore it and after for each 1’s we have to pop one “0” from stack. If stack and input string both are empty at the same time then the string will be accepted else rejected. NOTE: i>=0 , so a single “2” is also accepted by DPDA. Hence this language is DCFL and every DCFL is recursive also, so it is also a recursive language.
Question 94

Which of the following languages is regular? 

A
{wwR|w ∈ {0,1}+}
B
{wwRx|x, w ∈ {0,1}+}
C
{wxwR|x, w ∈ {0,1}+}
D
{xwwR|x, w ∈ {0,1}+}
       Theory-of-Computation       Regular-Language       GATE 2007
Question 94 Explanation: 
The regular expression corresponding to option C is:
0 (0+1)+ 0 + 1 (0+1)+ 1
Any string which begins and ends with same symbol, can be written in form of “wxwr
For example consider a string: 10010111, in this string “w=1” , “x= 001011” and wr = 1.
Hence any string which begins and ends with either “0” or with “1” can be written in form of “wxwr” and L = {wxwr | 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

A
b*ab*ab*ab*
B
(a+b)*
C
b*a(a+b)*
D
b*ab*ab*
       Theory-of-Computation       Finite-Automata       GATE 2007
Question 95 Explanation: 
State q3 is unreachable and state q1 and q2 are equivalent, so we can merge q1 and q2 as one state. The resulting DFA will be:

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

A
1
B
2
C
3
D
4
       Theory-of-Computation       Finite-Automata       GATE 2007
Question 96 Explanation: 
The minimum state automaton for problem 74 is:
Question 97

Let L1 = {0n+m1n0m|n,m ≥ 0}, L2 = {0n+m1n+m0m|n,m ≥ 0}, and L3 = {0n+m1n+m0n+m|n,m ≥ 0}. Which of these languages are NOT context free?

A
L1 only
B
L3 only
C
L1 and L2
D
L2 and L3
       Theory-of-Computation       Context-Free-Language       GATE 2006
Question 97 Explanation: 
L1 can be accepted by PDA, we need to push all 0’s before 1’s and when 1’s comes in input string we need to pop every 0’s from stack for every 1’s and then for every 0’s. If stack and input string is empty at the same time then the string belongs to L1.
But for L2 and L3 PDA implementation is not possible. The reason is, in L2 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 L3 also has the similar reason.
Question 98

If s is a string over (0 + 1)* then let n0(s) denote the number of 0’s in s and n1(s) the number of 1’s in s. Which one of the following languages is not regular?

A
L = {s ∈ (0+1)* | n0(s) is a 3-digit prime}
B
L = {s ∈ (0+1)* | for every prefix s' of s,|n0(s') - n1(s')| ≤ 2}
C
L = {s ∈ (0+1)* |n0(s) - n1(s)| ≤ 4}
D
L = {s ∈ (0+1)* | n0(s) mod 7 = n1(s) mod 5 = 0}
       Theory-of-Computation       Regular-Language       GATE 2006
Question 98 Explanation: 
Since 3-digit prime numbers are finite so language in option A is finite, hence it is regular.
Option B: The DFA contains 6 states
State 1: n0(s') - n1(s') = 0
State 2: n0(s') - n1(s') = 1
State 3: n0(s') - n1(s') = 2
State 4: n0(s') - n1(s') = -1
State 5: n0(s') - n1(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: n0(s) = 5 and n1(s) = 1 then n0(s) - n1(s) = 4 and if n0(s) = 15 and n1(s) = 11 then n0(s) - n1(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?

A
L is recursively enumerable, but not recursive
B
L is recursive, but not context-free
C
L is context-free, but not regular
D
L is regular
       Theory-of-Computation       Identify-Class-Language       GATE 2006
Question 99 Explanation: 
Let L1 = {s ∈ (0+1)* | d(s) mod5 = 2}, we can construct the DFA for this which will have 5 states (remainders 0,1,2,3,4)
L2 = {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 L1 and L2 have DFAs, hence they are regular. So the resulting Language.
L = L1 ∩ L2 (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?

A
I only
B
I and III only
C
II and III only
D
I, II and III
       Theory-of-Computation       Contest-Free-Grammar       GATE 2006
Question 100 Explanation: 
Is ambiguous, as it has two parse tree for the string “abbaba”

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 L1 be a regular language, L2 be a deterministic context-free language and L3 a recursively enumerable, but not recursive, language. Which one of the following statements is false?

A
L1 ∩ L2 is a deterministic CFL
B
L3 ∩ L1 is recursive
C
L1 ∪ L2 is context free
D
L1 ∩ L2 ∩ L3 is recursively enumerable
       Theory-of-Computation       Identify-Class-Language       GATE 2006
Question 101 Explanation: 
Option A is true, as by closure property (R is a regular language and L is any language)
L ∩ R = L ( i.e. L Intersection R is same type as L )
So L1 ∩ L2 is a deterministic CFL.
Option B is false, as L3 is recursive enumerable but not recursive, so intersection with L1 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, L1 ∪ L2 is deterministic context free, hence it is also context free.
Option D is true, as L1 ∩ L2 is DCFL and DCFL ∩ L3 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:

A
3
B
5
C
8
D
9
       Theory-of-Computation       Finite-Automata       GATE 2006
Question 102 Explanation: 
L = (111 + 11111)* generates the strings {ϵ, 111, 11111, 111111, 11111111, …….}
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 = {aibj|i≠j}?

A
S→AC|CB
C→aCb|a|b
A→aA|ϵ
B→Bb|ϵ
B
S→aS|Sb|a|b
C
S→AC|CB
C→aCb|ϵ
A→aA|ϵ
B→Bb|ϵ
D
S→AC|CB
C→aCb|ϵ
A→aA|a
B→Bb|b
       Theory-of-Computation       Grammar       GATE 2006
Question 103 Explanation: 
The language have all the strings in which a’s comes before b’s and number of a’s never equal to b’s. The grammars in Option A, B and C generates string “ab” in which number of a’s are equal to b’s, hence they are wrong. But option D generates all the string which is in L.
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 albm with l≠m?

A
max(l,m)+2
B
l+m+2
C
l+m+3
D
max(l, m)+3
       Theory-of-Computation       Grammar       GATE 2006
Question 104 Explanation: 
The correct grammar for L = {aibj | i≠j} is
S → AC|CB C → aCb|ϵ A → aA|a B → Bb|b
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 P1, P2 and P3. It is known that P1 is decidable and P2 is undecidable. Which one of the following is TRUE?

A
P3 is decidable if P1 is reducible to P3
B
P3 is undecidable if P3 is reducible to P2
C
P3 is undecidable if P2 is reducible to P3
D
P3 is decidable if P3 is reducible to P2's complement
       Theory-of-Computation       Decidability-and-Undecidability       GATE 2005
Question 105 Explanation: 
Option A: If P1 is reducible to P3 then P3 is atleast as hard as P1. So there is no guarantee if P3 is decidable.
Option B: If P3 is reducible to P2, then P3 cannot be harder than P2. But P2 being undecidable, this can't say P3 is undecidable.
Option C: If P2 is reducible to P3, then P3 is atleast as hard as P2. Since, P2 is undecidable. This means P3 is also undecidable.
Question 106

Consider the machine M:

The language recognized by M is:

A
{w ∈ {a, b}* | every a in w is followed by exactly two b's}
B
{w ∈ {a, b}*| every a in w is followed by at least two b’}
C
{w ∈ {a, b}*| w contains the substring 'abb'}
D
{w ∈ {a, b}*| w does not contain 'aa' as a substring}
       Theory-of-Computation       Finite-Automata       GATE 2005
Question 106 Explanation: 
Option A: It is false. The string with more than two b's also accepting the string.
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 Nf and Np denote the classes of languages accepted by non-deterministic finite automata and non-deterministic push-down automata, respectively. Let Df and Dp denote the classes of languages accepted by deterministic finite automata and deterministic push-down automata, respectively. Which one of the following is TRUE?

A
Df ⊂ Nf and Dp ⊂ Np
B
Df ⊂ Nf and Dp = Np
C
Df = Nf and Dp = Np
D
Df = Nf and Dp ⊂ Np
       Theory-of-Computation       NFA       GATE 2005
Question 107 Explanation: 
NFA and DFA have equivalent powers.
So Df = Nf
NPDA can accept more languages than DPDA.
Dp ⊂ Np
Question 108

Consider the languages:

L1 = {anbncm |n,m > 0} and L2 = {anbmcm |n,m > 0}

Which one of the following statements is FALSE?

A
L1 ∩ L2 is a context-free language
B
L1 ∪ L2 is a context-free language
C
L1 and L2 are context-free languages
D
L1 ∩ L2 is a context sensitive language
       Theory-of-Computation       Context-Free-Language       GATE 2005
Question 108 Explanation: 
CFL is closed under Union.
CFL is not closed under Intersection.
L1 = {anbncm | n>0 & m>0}
L2 = {ambncn | n>0 & m>0}
L3 = L1 ∩ L2
={anbncn | n>0} It is not context-free.
Question 109

Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is TRUE?

A
B
C
D
       Theory-of-Computation       Recursive-Enumerable-Languages       GATE 2005
Question 109 Explanation: 
Recursive languages are closed under complementation.
But, recursive enumerable languages are not closed under complementation.
If L1 is recursive, then L1', is also recursive.
If L2 is recursive enumerable, then L2', is not recursive enumerable language.
Question 110

Consider the languages:

L1 = {wwR |w ∈ {0,1}*}
L2 = {w#wR | w ∈ {0,1}*}, where # is a special symbol
L3 = {ww | w ∈ (0, 1)*}

Which one of the following is TRUE?

A
L1 is a deterministic CFL
B
L2 is a deterministic CFL
C
L3 is a CFL, but not a deterministic CFL
D
L3 is a deterministic CFL
       Theory-of-Computation       Context-Free-Language       GATE 2005
Question 110 Explanation: 
Given: L1 = {wwR | w ∈ {0,1}*}
→ Given L1 is CFL but not DCFL.
→ Because, we can't predict where w ends and where it reverse is starts.
→ L2 = {w#wR | w ∈ (0,1)*}
→ Given L2 is CFL and also DCFL.
→ The string w and wR are separated by special symbol '#'.
→ L3 = {ww | w ∈ (0,1)*}
This is not even a CFL. This can be proved by using pumping lemma. So, L2 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?

A
It computes 1's complement of the input number
B
It computes 2's complement of the input number
C
It increments the input number
D
It decrements the input number
       Theory-of-Computation       Finite-Automata       GATE 2005
Question 111 Explanation: 
Let consider an example string:
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.

A
divisible by 3 and 2
B
odd and even
C
even and odd
D
divisible by 2 and 3
       Theory-of-Computation       Finite-Automata       GATE 2004
Question 112 Explanation: 
Option B:
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 {am bn Cm+n | m, n ≥ 1} is

A
regular
B
context-free but not regular
C
context sensitive but not context free
D
type-0 but not context sensitive
       Theory-of-Computation       Identify-Class-Language       GATE 2004
Question 113 Explanation: 
Let us construct a PDA for the language
PUSH z0 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 = {an | n ≥ 1}, Example.
CFL:
R = {anbm | n,m ≥ 1}, Example.
Question 114

L1 is a recursively enumerable language over Σ. An algorithm A effectively enumerates its words as w1, w2, w3, ... Define another language L2 over Σ Union {#} as {wi # wj : wi, wj ∈ L1, i < j}. Here # is a new symbol. Consider the following assertions.

S1: L1 is recursive implies L2 is recursive
S2: L2 is recursive implies L1 is recursive

Which of the following statements is true?

A
Both S1 and S2 are true
B
S1 is true but S2 is not necessarily true
C
S2 is true but S1 is not necessarily true
D
Neither is necessarily true
       Theory-of-Computation       Recursive-Enumerable-Languages       GATE 2004
Question 114 Explanation: 
Given that
L1 = recursively enumerable language
L2 over Σ∪{#} as {wi#wj | wi, wj ∈ L1, i < j}
S1 is True.
If L1 is recursive then L2 is also recursive. Because, to check w = wi#wj belongs to L2, and we give wi and wj to the corresponding decider L1, if both are to be accepted, then w∈L1 and not otherwise.
S2 is also True:
With the corresponding decider L2 we need to make decide L1.
Question 115

Nobody knows yet if P = NP. Consider the language L defined as follows:

Which of the following statements is true?

A
L is recursive
B
L is recursively enumerable but not recursive
C
L is not recursively enumerable
D
Whether L is recursive or not will be known after we find out if P = NP
       Theory-of-Computation       Recursive-Enumerable-Languages       GATE 2003
Question 115 Explanation: 
Here, we have two possibilities, whether
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

A
(1*0)*1*
B
0+(0+10)*
C
(0+1)*10(0+1)*
D
None of the above
       Theory-of-Computation       Regular-Expressions       GATE 2003
Question 116 Explanation: 
Both (A) and the given expression generates all strings over Σ.
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?

A
L is necessarily finite
B
L is regular but not necessarily finite
C
L is context free but not necessarily regular
D
L is recursive but not necessarily context free
       Theory-of-Computation       Identify-Class-Language       GATE 2003
Question 117 Explanation: 
The given language L is to be recursively enumerable. The TM which accepts the language which is in lexicographic order. If the language is not in lexicographic order which is not accepted by TM.
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

A
1
B
5
C
7
D
8
       Theory-of-Computation       Finite-Automata       GATE 2003
Question 118 Explanation: 

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?

A
G is not ambiguous
B
There exist x, y ∈ L(G) such that xy ∉ L(G)
C
There is a deterministic pushdown automaton that accepts L(G)
D
We can find a deterministic finite state automaton that accepts L(G)
       Theory-of-Computation       Contest-Free-Grammar       GATE 2003
Question 119 Explanation: 
a) False
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 L1 and L2 each on the alphabet ∑. Let f: ∑ → ∑ be a polynomial time computable bijection such that (∀ x)[x ∈ L1 iff f(x) ∈ L2]. Further, let f-1 be also polynomial time computable.

Which of the following CANNOT be true?

A
L1 ∈ P and L2 is finite
B
L1 ∈ NP and L2 ∈ P
C
L1 is undecidable and L2 is decidable
D
L1 is recursively enumerable and L2 is recursive
       Theory-of-Computation       Decidability-and-Undecidability       GATE 2003
Question 120 Explanation: 
L1 is polynomial time reducible to L2.
Now if L2 is decidable then L1 should also be decidable. Hence, option (c) is wrong.
Question 121

A single tape Turing Machine M has two states q0 and q1, of which q0 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 (q1, 1, R) in row q0 and column 1 signifies that if M is in state q0 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 q1.

Which of the following statements is true about M?

A
M does not halt on any string in (0+1)+
B
M does not halt on any string in (00+1)*
C
M halts on all strings ending in a 0
D
M halts on all strings ending in a 1
       Theory-of-Computation       Turing Machine       GATE 2003
Question 121 Explanation: 

Try for any string, it will not Halt for any string other than ϵ. Hence, option (A) is correct.
Question 122

Define languages L0 and L1 as follows:

L0 = {〈M, w, 0〉 | M halts on w}
L1 = {〈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 = L0∪L1. Which of the following is true?

A
B
C
D
       Theory-of-Computation       Turing Machine       GATE 2003
Question 123

Consider the NFA M shown below.

Let the language accepted by M be L. Let L1 be the language accepted by the NFA M1, obtained by changing the accepting state of M to a non-accepting state and by changing the non-accepting state of M to accepting states. Which of the following statements is true?

A
L1 = {0,1}* - L
B
L1 = {0,1}*
C
L1 ⊆ L
D
L1 = L
       Theory-of-Computation       Finite-Automata       GATE 2003
Question 123 Explanation: 
As in the question said,

As in above NFA language,
L1 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

A
Context free
B
Regular
C
Deterministic Context free
D
Recursive
       Theory-of-Computation       Identify-Class-Language       GATE 2002
Question 124 Explanation: 
Push down automata accept context free grammars but here the value of stack is limited 10 then it accepts regular languages.
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 1-bit input and y stands for 2- bit output

A
Outputs the sum of the present and the previous bits of the input.
B
Outputs 01 whenever the input sequence contains 11
C
Outputs 00 whenever the input sequence contains 10
D
None of the above
       Theory-of-Computation       Finite-Automata       GATE 2002
Question 125 Explanation: 
Let us consider a string 100111
(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 {x|length of x is divisible by 3} has

A
2 states
B
3 states
C
4 states
D
5 states
       Theory-of-Computation       Finite-Automata       GATE 2002
Question 126 Explanation: 
{x | length of x divisible by 3} for this constructing a finite Automata that implies

Minimum no. of states that we require is "3".
Question 127

Which of the following is true?

A
The complement of a recursive language is recursive.
B
The complement of a recursively enumerable language is recursively enumerable.
C
The complement of a recursive language is either recursive or recursively enumerable.
D
The complement of a context-free language is context-free.
       Theory-of-Computation       Properties-of-Languages       GATE 2002
Question 127 Explanation: 
Recursive languages are closed under complementation.
Question 128

The C language is:

A
A context free language
B
A context sensitive language
C
A regular language
D
Parsable fully only by a Turing machine
       Theory-of-Computation       Identify-Class-Language       GATE 2002
Question 128 Explanation: 
C and C++ are context sensitive languages.
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?
A
Theory Explanation is given below.
       Theory-of-Computation       Turing Machine       GATE 2002
Question 130

We require a four state automaton to recognize the regular expression (a|b)*abb.

    (a) Give an NFA for this purpose.
    (b) Give a DFA for this purpose.
A
Theory Explanation is given below.
       Theory-of-Computation       Finite-Automata       GATE 2002
Question 131

Consider the following two statements:

    S1: {02n|n≥1|} is a regular language
    S2: {0m1n0m+n|m≥1 and n≥1|} is a regular language

Which of the following statements is correct?

A
Only S1 is correct
B
Only S2 is correct
C
Both S1 and S2 are correct
D
None of S1 and S2 is correct
       Theory-of-Computation       Regular Languge       GATE 2001
Question 131 Explanation: 
For S1 we can construct DFA. S1 represents the string contains even no. of 0's. So S1 is regular.
For S2, DFA is not possible which is not regular.
Question 132

Which of the following statements is true?

A
If a language is context free it can always be accepted by a deterministic push-down automaton
B
The union of two context free languages is context free
C
The intersection of two context free languages is context free
D
The complement of a context free language is context free
       Theory-of-Computation       Properties-of-Languages       GATE 2001
Question 132 Explanation: 
Context free languages closed under Union, concatenation and kleen star. But not close under intersection and complementation.
Question 133

Given an arbitrary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least

A
N2
B
2N
C
2N
D
N!
       Theory-of-Computation       Finite-Automata       GATE 2001
Question 133 Explanation: 
If NFA contains N, then possible number of states in possible DFA is 2N.
If NFA have two states {1}{2} = 2
Then DFA may contain {ϕ}{1}{2}{1,2} = 4 = 22 = 2N
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?

A
8
B
14
C
15
D
48
       Theory-of-Computation       Finite-Automata       GATE 2001
Question 134 Explanation: 
A DFA which is no. of a's divisible by 6 consists of 6 states i.e., mod6 results 0,1,2,3,4,5.
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 = {ww|w ∈ {a,b}*}
    L2 = {wwR|w ∈ {a,b}*, wR is the reverse of w}
    L3 = {02i|i is an integer}
    L3 = {0i2|i is an integer}

Which of the languages are regular?

A
Only L1 and L2
B
Only L2, L3 and L4
C
Only L3 and L4
D
Only L3
       Theory-of-Computation       Regular-Language       GATE 2001
Question 135 Explanation: 
L1 = {ww|w∈{a,b}*}
⇒ This is not regular language. We can't be able to identify where the 'w' will ends and where the next 'w' starts.
L2 = {wwR|w∈{a,b}*, wR is the reverse of w}
⇒ This also not a regular language. We can't identify where 'w' ends.
L4 = {0i2|i is an integer}
= {0i*0i|i is an integer}
⇒ This is also not a regular language. We can't identify where 0i ends.
L3 = {02i|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?

A
X is decidable
B
X is undecidable but partially decidable
C
X is undecidable and not even partially decidable
D
X is not a decision problem
       Theory-of-Computation       Turing Mchine       GATE 2001
Question 136 Explanation: 
The given X is a Halting problem. So which is to be undecidable but partially decidable.
Question 137

Construct DFA’s for the following languages:

 (a) L = {w|w ∈ {a,b}*, w has baab as a subsring } 
 (b) L = {w|w ∈ {a,b}*, w has an odd number of a's and an odd number of b's} 
A
Theory Explanation is given below.
       Theory-of-Computation       Finite-Automata       GATE 2001
Question 138

Give a deterministic PDA for the language L = {ancb2n|n ≥ 1} over the alphabet Σ = {a,b,c}. Specify the acceptance state.

A
Theory Explanation is given below.
       Theory-of-Computation       Push-Down-Automata       GATE 2001
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.
A
Theory Explanation is given below.
       Theory-of-Computation       Turing Machine       GATE 2001
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?

A
S ⊂ T
B
T ⊂ S
C
S = T
D
S ∩ T = ɸ
       Theory-of-Computation       Regular-Expressions       GATE 2000
Question 140 Explanation: 
If we draw DFA for language S and T it will represent same.
Question 141

Let L denotes the language generated by the grammar S → 0S0/00.
Which of the following is true?

A
L = 0+
B
L is regular but not 0+
C
L is context free but not regular
D
L is not context free
       Theory-of-Computation       Identify-Class-Language       GATE 2000
Question 141 Explanation: 
The given grammar results that a string which contains even length excluding empty string i.e {00,000000,00000000,…….}. So which is regular but not 0+.
Question 142

What can be said about a regular language L over {a} whose minimal finite state automation has two states?

A
L must be {an |n is odd}
B
L must be {an |n is even}
C
L must be {an|≥0}
D
Either L must be {an |n is odd}, or L must be {an | n is even}
       Theory-of-Computation       Finite-Automata       GATE 2000
Question 142 Explanation: 
If first state is final, then it accepts even no. of a's. If second state is final then it accepts odd no. of a's.
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?

A
Both (P1) and (P2) are decidable
B
Neither (P1) nor (P2) are decidable
C
Only (P1) is decidable
D
Only (P2) is decidable
       Theory-of-Computation       Decidability-and-Undecidability       GATE 2000
Question 143 Explanation: 
For P1, we just need to give a run on the machine. Finite state machines always halts unlike TM.
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 non-terminal symbols with S being the start symbol; a,b are terminal symbols and ε is the empty string. This grammar generates strings of the form aibj for some i,j ≥ 0, where i and j satisfy some condition. What is the condition on the values of i and j?

A
Theory Explanation is given below.
       Theory-of-Computation       Descriptive       GATE 2000
Question 144 Explanation: 
(a) From the question based on possibilities:
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→bA|X 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 qo to q0 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
{x2xR|x ∈ {0,1}*, xR denotes reverse of x}, by empty stack.
(b) Describe a non-deterministic pda with three states in the above notation that accept the language {0n1m| n ≤ m ≤ 2n} by empty stack

A
Theory Explanation is given below.
       Theory-of-Computation       Descriptive       GATE 2000
Question 145 Explanation: 
(a)

(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

A
n states
B
n + 1 states
C
n + 2 states
D
None of the above
       Theory-of-Computation       Finite-Automata       GATE 1999
Question 146 Explanation: 
Let's draw both NFA and DFA and see which one requires less no. of state.
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

Context-free languages are closed under:

A
Union, intersection
B
Union, Kleene closure
C
Intersection, complement
D
Complement, Kleene closure
       Theory-of-Computation       Context-Free-Language       GATE 1999
Question 147 Explanation: 
Context free languages are not closed under Intersection and complementation.
By checking the options only option B is correct.
Question 148

Let LD be the set of all languages accepted by a PDA by final state and LE the set of all languages accepted by empty stack. Which of the following is true?

A
LD = LE
B
LD ⊃ LE
C
LE = LD
D
None of the above
       Theory-of-Computation       Push-Down-Automata       GATE 1999
Question 148 Explanation: 
For any PDA which can be accepted by final state, there is an equivalent PDA which can also be accepted by an empty stack and for any PDA which can be accepted by an empty stack, there is an equivalent PDA which can be accepted by final state.
Question 149

If L is context free language and L2 is a regular language which of the following is/are false?

A
L1 – L2 is not context free
B
L1 ∩ L2 is context free
C
~L1 is context free
D
~L2 is regular
E
Both A and C
       Theory-of-Computation       Identify-Class-Language       GATE 1999
Question 149 Explanation: 
(A) L2 is regular language and regular language is closed under complementation. Hence ~L2 is also regular.
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 non-terminal, is

A
Ambiguous
B
Unambiguous
C
Information is not sufficient to decide whether it is ambiguous or unambiguous
D
None of the above
       Theory-of-Computation       Grammar       GATE 1999
Question 150 Explanation: 
If a grammar is both left and right recursion, then grammar may or may not be ambiguous.
Question 151

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
A ⊂ B
B
B ⊂ A
C
A and B are incomparable
D
A = B
       Theory-of-Computation       Regular-Expressions       GATE 1998
Question 151 Explanation: 
Both A and B are equal, which generates strings over {0,1}, while 0 is followed by 1.
Question 152

Both A and B are equal, which generates strings over {0,1}, while 0 is followed by 1.

A
The numbers 1, 2, 4, 8, ……………., 2n, ………… written in binary
B
The numbers 1, 2, 4, ………………., 2n, …………..written in unary
C
The set of binary string in which the number of zeros is the same as the number of ones
D
The set {1, 101, 11011, 1110111, ………..}
       Theory-of-Computation       Finite-Automata       GATE 1998
Question 152 Explanation: 
The numbers are to be like
10, 100, 1000, 10000 .... = 10*
which is regular and recognized by deterministic finite automata.
Question 153

Regarding  the power of recognition of languages, which of the following statements is false?

A
The non-deterministic finite-state automata are equivalent to deterministic finite-state automata.
B
Non-deterministic Push-down automata are equivalent to deterministic Push- down automata.
C
Non-deterministic Turing machines are equivalent to deterministic Push-down automata.
D
Both B and C
       Theory-of-Computation       NFA       GATE 1998
Question 153 Explanation: 
B: No conversion possible from NPDA to DPDA.
C: Power (TM) > NPDA > DPDA.
Question 154

The string 1101 does not belong to the set represented by

A
110*(0 + 1)
B
1 ( 0 + 1)* 101
C
(10)* (01)* (00 + 11)*
D
Both C and D
       Theory-of-Computation       Regular-Expressions       GATE 1998
Question 154 Explanation: 
Options A & B are generates string 1101.
C & D are not generate string 1101.
Question 155

How many sub strings of different lengths (non-zero) can be found formed from a character string of length n?

A
n
B
n2
C
2n
D
       Theory-of-Computation       Sub-Strings       GATE 1998
Question 155 Explanation: 
Let us consider an example S = {APB}
Possible sub-strings are = {A, P, B, AP, PB, BA, APB}
Go through the options.
Option D:
n(n+1)/2 = 3(3+1)/2 = 6
Question 156

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

A
2
B
5
C
8
D
3
       Theory-of-Computation       Finite-Automata       GATE 1998
Question 156 Explanation: 
NFA:

Equivalent DFA:

Hence, 5 states.
Question 157

Which of the following statements is false?

A
Every finite subset of a non-regular set is regular
B
Every subset of a regular set is regular
C
Every finite subset of a regular set is regular
D
The intersection of two regular sets is regular
       Theory-of-Computation       Regular-Language       GATE 1998
Question 157 Explanation: 
Let regular language L = a*b* and subset of L is anbn, n ≥ 0, which is not regular. Hence option (B) is false.
Question 158

Given Σ = {a,b}, which one of the following sets is not countable?

A
Set of all strings over Σ
B
Set of all languages over Σ
C
Set of all regular languages over Σ
D
Set of all languages over Σ accepted by Turing machines
       Theory-of-Computation       Countability       GATE 1997
Question 158 Explanation: 
Uncountable: Set of all languages over Σ is uncountable.
Question 159

Which one of the following regular expressions over {0,1} denotes the set of all strings not containing 100 as a substring?

A
0*(1+0)*
B
0*1010*
C
0*1*01
D
0(10+1)*
       Theory-of-Computation       Regular-Expressions       GATE 1997
Question 159 Explanation: 
(A) generates 100.
(B) generates 100 as substring.
(C) doesn't generate 1.
(D) answer.
Question 160

Which one of the following is not decidable?

A
Given a Turing machine M, a stings s and an integer k, M accepts s within k steps
B
Equivalence of two given Turing machines
C
Language accepted by a given finite state machine is not empty
D
Language generated by a context free grammar is non empty
       Theory-of-Computation       Decidability-and-Undecidability       GATE 1997
Question 160 Explanation: 
(A) It is not halting problem. In halting problem number of steps can go upto infinity and that is the only reason why it becomes undecidable.
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 161

Which of the following languages over {a,b,c} is accepted by a deterministic pushdown automata?

 Note: wR  is the string obtained by reversing 'w'. 
A
{w⊂wR|w ∈ {a,b}*}
B
{wwR|w ∈ {a,b,c}*}
C
{anbncn|n ≥ 0}
D
{w|w is a palindrome over {a,b,c}}
       Theory-of-Computation       Push-Down-Automata       GATE 1997
Question 161 Explanation: 
(A) w⊂wR, can be realized using DPDA because we know the center of the string that is c here.
(B) wwR, is realized by NPDA because we can't find deterministically the center of palindrome string.
(C) {anbncn | 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 162

Which two of the following four regular expressions are equivalent? (ε is the empty string).

    (i) (00)*(ε+0)
    (ii) (00)*
    (iii) 0*
    (iv) 0(00)*
A
(i) and (ii)
B
(ii) and (iii)
C
(i) and (iii)
D
(iii) and (iv)
       Theory-of-Computation       Regular-Expressions       GATE 1996
Question 162 Explanation: 
(00)*(ε+0),0*
In these two, we have any no. of 0's as well as null.
Question 163

Which of the following statements is false?

A
The Halting problem of Turing machines is undecidable.
B
Determining whether a context-free grammar is ambiguous is undecidbale.
C
Given two arbitrary context-free grammars G1 and G2 it is undecidable whether L(G1) = L(G2).
D
Given two regular grammars G1 and G2 it is undecidable whether L(G1) = L(G2).
       Theory-of-Computation       Decidability-and-Undecidability       GATE 1996
Question 163 Explanation: 
Equivalence of regular languages is decidable under
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 1st for CSL and REC.
→ None for RE.
Question 164

Let L ⊆ Σ* where Σ = {a, b}. Which of the following is true?

A
L = {x|x has an equal number of a's and b's } is regular
B
L = {anbn|n≥1} is regular
C
L = {x|x has more a's and b's} is regular
D
L = {ambn|m ≥ 1, n ≥ 1} is regular
       Theory-of-Computation       Identify-Class-Language       GATE 1996
Question 164 Explanation: 
L = {ambn|m ≥ 1, n ≥ 1}
Here, m and n are independent.
So 'L' Is Regular.
Question 165

If L1 and L2 are context free languages and R a regular set, one of the languages below is not necessarily a context free language. Which one?

A
L1, L2
B
L1 ∩ L2
C
L1 ∩ R
D
L1 ∪ L2
       Theory-of-Computation       Identify-Class-Language       GATE 1996
Question 165 Explanation: 
Context free languages are not closed under intersection.
Question 166

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

A
the set of all binary strings with unequal number of 0’s and 1’s
B
the set of all binary strings including the null string
C
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
D
None of the above
       Theory-of-Computation       Context-Free-Language       GATE 1996
Question 166 Explanation: 
(B) is the answer. Because for any binary string of 0's and 1's we can append another string to make it contain equal no. of 0's and 1's, i.e., any string over {0,1} is a prefix of a string in L.
Question 167

The grammar whose productions are

  → if id then 
  → if id then   else 
  → id := id 

is ambiguous because

A
the sentence
if a then if b then c:=d
B
the left most and right most derivations of the sentence
if a then if b then c:=d
give rise top different parse trees
C
the sentence
if a then if b then c:=d else c:=f
has more than two parse trees
D
the sentence
if a then if then c:=d else c:=f
has two parse trees
       Theory-of-Computation       Context-Free-Language       GATE 1996
Question 167 Explanation: 
We have to generate
"if a then if b then c:=d else c:=f".
Parse tree 1:

Parse tree 2:
Question 168

Consider the given figure of state table for a sequential machine. The number of states in the minimized machine will be

A
4
B
3
C
2
D
1
       Theory-of-Computation       Finite-Automata       GATE 1996
Question 168 Explanation: 
3 states are required in the minimized machine states B and C can be combined as follows:
Question 169

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?

A
(L ∪ D)+
B
L(L ∪ D)*
C
(L⋅D)*
D
L⋅(L⋅D)*
       Theory-of-Computation       Regular-Expressions       GATE 1995
Question 169 Explanation: 
Which is to be letter followed by any number of letters (or) digits
L(L ∪ D)*
Question 170

Consider a grammar with the following productions

S → a∝b|b∝c| aB
S → ∝S|b
S → ∝b b|ab
S ∝ → bd b|b 

The above grammar is:

A
Context free
B
Regular
C
Context sensitive
D
LR(k)
       Theory-of-Computation       General       GATE 1995
Question 170 Explanation: 
S ∝→ [violates context free]
Because LHS must be single non-terminal 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 171

Which of the following definitions below generates the same language as L, where L = {xnyn such that n >= 1}?

 I. E → xEy|xy
 II. xy|(x+xyy+)
 III. x+y+ 
A
I only
B
I and II
C
II and III
D
II only
       Theory-of-Computation       Regular Languages       GATE 1995
Question 171 Explanation: 
(I) is the correct definition and the other two is wrong because the other two can have any no. of x and y. There is no such restriction over the number of both being equal.
Question 172

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:

A
01
B
10
C
101
D
110
       Theory-of-Computation       Finite-State-Machine       GATE 1995
Question 172 Explanation: 

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 173

Let Σ = {0,1}, L = Σ* and R = {0n1n such that n >0} then the languages L ∪ R and R are respectively

A
regular, regular
B
not regular, regular
C
regular, not regular
D
not regular, no regular
       Theory-of-Computation       regular Languages       GATE 1995
Question 173 Explanation: 
L∪R is nothing but L itself. Because R is subset of L and hence regular. R is deterministic context free but not regular as we require a stack to keep the count of 0's to make that of 1's.
Question 174

Which of the following conversions is not possible (algorithmically)?

A
Regular grammar to context free grammar
B
Non-deterministic FSA to deterministic FSA
C
Non-deterministic PDA to deterministic PDA
D
Non-deterministic Turing machine to deterministic Turing machine
       Theory-of-Computation       Grammar       GATE 1994
Question 174 Explanation: 
NPDA to DPDA conversion is not possible. They have different powers.
Question 175

Which of the following features cannot be captured by context-free grammars?

A
Syntax of if-then-else statements
B
Syntax of recursive procedures
C
Whether a variable has been declared before its use
D
Variable names of arbitrary length
       Theory-of-Computation       CFG       GATE 1994
Question 175 Explanation: 
Context free grammars are used to represent syntactic rules while designing a compiler.
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 176

The regular expression for the language recognized by the finite state automaton of figure is __________

A
L = 0*1*
       Theory-of-Computation       Finite-Automata       GATE 1994
Question 176 Explanation: 
L = 0*1*
L contains all binary strings where a 1 is not followed by a 0.
Question 177

Every subset of a countable set is countable.
State whether the above statement is true or false with reason.

A
True
B
False
       Theory-of-Computation       Undecidability       GATE 1994
Question 177 Explanation: 
Because if a set itself is countable then the subset of set is definitely countable.
Question 178

Consider the language L = {an| n≥0} ∪ {anbn| n≥0} and the following statements.

    I. L is deterministic context-free.
    II. L is context-free but not deterministic context-free.
    III. L is not LL(k) for any k.

Which of the above statements is/are TRUE?

A
II only
B
III only
C
I only
D
I and III only
       Theory-of-Computation       Languages-and-Grammars       GATE 2020
Question 178 Explanation: 
L is DCFL.
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 179

Consider the following statements.

    I. If L1 ∪ L2 is regular, then both L1 and L2 must be regular.
    II. The class of regular languages is closed under infinite union.

Which of the above statements is/are TRUE?

A
Both I and II
B
II only
C
Neither I nor II
D
I only
       Theory-of-Computation       Regular-Language       GATE 2020
Question 179 Explanation: 
Statement I is wrong.
Assume L1 = {an bn | n>0} and L2 = complement of L1
L1 and L2 both are DCFL but not regular, but L1 U L2 = (a+b)* which is regular.
Hence even though L1 U L2 is regular, L1 and L2 need not be always regular.
Statement II is wrong.
Assume the following finite (hence regular) languages.
L1 = {ab}
L2 = {aabb}
L3 = {aaabbb}
.
.
.
L100 = {a100 b100}
.
.
.
If we take infinite union of all above languages i.e,
{L1 U L2 U ……….L100 U ……}
then we will get a new language L = {an bn | n>0}, which is not regular.
Hence regular languages are not closed under infinite UNION.
Question 180

Which one of the following regular expressions represents the set of all binary strings with an odd number of 1’s?

A
10*(0*10*10*)*
B
((0 + 1)*1(0 + 1)*1)*10*
C
(0*10*10*)*10*
D
(0*10*10*)*0*1
       Theory-of-Computation       Regular-Expression       GATE 2020
Question 180 Explanation: 
The regular expression 10*(0*10*10*)* always generate string begin with 1 and thus does not generate string “01110” hence wrong option.
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 181

Which of the following languages are undecidable? Note that indicates encoding of the Turing machine M.

    L1 = | L(M) = Φ}
    L2 = {| M on input w reaches state q in exactly 100 steps}
    L3 = {| L(M) is not recursive}
    L4 = {| L(M) contains at least 21 members}
A
L2 and L3 only
B
L1 and L3 only
C
L2, L3 and L4 only
D
L1, L3 and L4 only
       Theory-of-Computation       Decidability-and-Undecidability       GATE 2020
Question 181 Explanation: 
L1 is undecidable as emptiness problem of Turing machine is undecidable. L3 is undecidable since there is no algorithm to check whether a given TM accept recursive language. L4 is undecidable as it is similar to membership problem.
Only L3 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 182

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 ______.

A
6
       Theory-of-Computation       Finite-Automata       GATE 2020
Question 182 Explanation: 
DFA 1: No. of a’s divisible by 2.

DFA 1: No. of a’s not divisible by 3

Using product automata:
Question 183

Consider the following languages.

    L1 = {wxyx | w,x,y ∈ (0 + 1)+}
    L2 = {xy | x,y ∈ (a + b)*, |x| = |y|, x ≠ y}

Which one of the following is TRUE?

A
L1 is context-free but not regular and L2 is context-free.
B
Neither L1 nor L2 is context-free.
C
L1 is regular and L2 is context-free.
D
L1 is context-free but L2 is not context-free.
       Theory-of-Computation       Languages-and-Grammars       GATE 2020
Question 183 Explanation: 
L1 is regular. y can be expanded and w can also expanded. So x can be either "a" or "b".
So it is equivalent to
(a+b)+ a (a+b)+ a + (a+b)+ b (a+b)+ b
L2 is CFL since it is equivalent to complement of L=ww.
Complement of L=ww is CFL.
Question 184

If the state machine described in figure, should have a stable state, the restriction on the inputs is given by

A
B
C
D
       Theory-of-Computation       Finite-Automata       GATE 1993
Question 185

Which of the following problems is not NP-hard?

A
Hamiltonian circuit problem
B
The 0/1 Knapsack problem
C
Finding bi-connected components of a graph
D
The graph colouring problem
       Theory-of-Computation       NP-Complete       GATE 1992
Question 185 Explanation: 
Note: Out of syllabus.
Question 186

For a context-free grammar, FOLLOW(A) is the set of terminals that can appear immediately to the right of non-terminal 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?

A
FOLLOW(A) and FOLLOW (A) may be different.
B
FOLLOW(A) and FOLLOW (A) are always the same.
C
All the three sets are identical.
D
All the three sets are different.
E
Both A and B
       Theory-of-Computation       Contest-Free-Grammar       GATE 1992
Question 186 Explanation: 
LFOLLOW may be different but RFOLLOW and FOLLOW will be same.
Question 187

Which of the following regular expression identifies are true?

A
r(*) = r*
B
(r*s*) = (r+s)*
C
(r+s)* = r* + s*
D
r*s* = r* + s*
       Theory-of-Computation       Regular-Expressions       GATE 1992
Question 187 Explanation: 
(A) Answer.
(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 188

If G is a context-free 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?

A
2l
B
2l + 1
C
2l - 1
D
l
       Theory-of-Computation       CFG       GATE 1992
Question 188 Explanation: 
For CNF, it is
2l - 1
For GNF, it is
l
Question 189

Context-free languages are

A
closed under union
B
closed under complementation
C
closed under intersection
D
closed under Kleene closure
E
Both A and D
       Theory-of-Computation       CFL       GATE 1992
Question 189 Explanation: 
CFL's are not closed under intersection and complementation.
Question 190

In which of the cases stated below is the following statement true?

 “For every non-deterministic machine M1 there exists an equivalent deterministic machine M2 recognizing the same language“.  
A
M1 is non-deterministic finite automaton
B
M1 is a non-deterministic PDA
C
M1 is a non-deterministic Turing machine
D
For no machine M1 use the above statement true
E
Both A and C
       Theory-of-Computation       General       GATE 1992
Question 190 Explanation: 
For every NFA there exists a DFA.
For every NPDA there does not exist a deterministic PDA.
Every non-deterministic TM has an equivalent deterministic TM.
Question 191

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?

A
L(s) ⊆ L(r) and L(s) ⊆ L(t)
B
L(r) ⊆ L(s) and L(s) ⊆ L(t)
C
L(s) ⊆ L(t) and L(s) ⊆ L(r)
D
L(t) ⊆ L(s) and L(s) ⊆ L(r)
E
None of the above
F
A and C
       Theory-of-Computation       Regular-Expressions       GATE 1991
Question 191 Explanation: 
L(s) ⊆ L(r), because 'r' generates all strings which 's' does but 'r' also generates '101' which 's' does not generate.
L(s) ⊆ L(t), because 't' generates all the strings which 's' generates but 't' also generates '0' which 's' do not generates.
Question 192

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 ∑?

A
It could be undecidable
B
It is Turing-machine recognizable
C
It is a context-sensitive language
D
It is a regular language
E
None of the above
F
B, C and D
       Theory-of-Computation       General       GATE 1991
Question 192 Explanation: 
(B), (C) and (D) are true. But the strongest answer would be (D), a regular language. Because every finite language is a regular language.
And, regular language ⊂ context-free ⊂ context-sensitive ⊂ Turing recognizable, would imply that regular language is the strongest answer.
Question 193

Choose the correct alternatives (More than one may be correct). Recursive languages are:

A
A proper superset of context free languages.
B
Always recognizable by pushdown automata.
C
Also called type ∅ languages.
D
Recognizable by Turing machines.
E
Both (A) and (D)
       Theory-of-Computation       Recursive-Languages       GATE 1990
Question 193 Explanation: 
A) True, since there are languages which are not CFL still recursive.
B) False.
C) False, because Type-0 language are actually recursively enumerable languages and not recursive languages.
D) True.
Question 194

Choose the correct alternatives (More than one may be correct).

It is undecidable whether:
A
An arbitrary Turing machine halts after 100 steps.
B
A Turing machine prints a specific letter.
C
A Turing machine computes the products of two numbers.
D
None of the above.
E
Both (B) and (C).
       Theory-of-Computation       Decidability-and-Undecidability       GATE 1990
Question 194 Explanation: 
A) An arbitrary TM halts after 100 steps is decidable. We can run TM for 100 steps and conclude that.
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 195

Choose the correct alternatives (More than one may be correct). Let R1 and R2 be regular sets defined over the alphabet Σ Then:

A
R1 ∩ R2 is not regular.
B
R1 ∪ R2 is regular.
C
Σ* − R1 is regular.
D
R1* is not regular.
E
Both (B) and (C).
       Theory-of-Computation       Regular-Language       GATE 1990
Question 195 Explanation: 
Regular languages are closed under,
1) Intersection
2) Union
3) Complement
4) Kleen-closure
Σ* - R1 is the complement of R1.
Hence, (B) and (C) are true.
Question 196

Context-free languages and regular languages are both closed under the operation(s) of:

A
Union
B
Intersection
C
Concatenation
D
Complementation
E
Both A and C
       Theory-of-Computation       Context-Free-and-Regular-Languages       GATE 1989
Question 196 Explanation: 
Regular languages closed under Union, Intersection, Concatenation and Complementation but CFC is only closed under Union and Concatenation.
Question 197

Which of the following problems are undecidable?

A
Membership problem in context-free languages.
B
Whether a given context-free language is regular.
C
Whether a finite state automation halts on all inputs.
D
Membership problem for type 0 languages.
E
Both (A) and (C).
       Theory-of-Computation       Undecidability       GATE 1989
Question 197 Explanation: 
→ Option A is decidable as we have various membership algorithms for CFL languages such as CYK algo, LL(K) and LC(K) parsing algorithms etc. In fact the upper bound to determine if a string belongs to CFL is given by O(n3) in worst case scenario by CYK algo and in some cases we have best case as O(n) as this is the case of S-grammar.
→ 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 198

Regularity is preserved under the operation of string reversal.

A
True
B
False
       Theory-of-Computation       Regular-Language       GATE 1987
Question 198 Explanation: 
Regular language is closed under reversal.
Question 199

All subsets of regular sets are regular.

A
True
B
False
       Theory-of-Computation       Regular-Language       GATE 1987
Question 199 Explanation: 
a*b* is regular but its subset anbn is not regular.
Question 200

A minimal DFA that is equivalent to an NDFA with n nodes has always 2n states.

A
True
B
False
       Theory-of-Computation       Finite-Automata       GATE 1987
Question 200 Explanation: 
A minimal DFA is equivalent to a NDFA with n nodes has atmost 2n states and does not have always 2n states.
Question 201

The intersection of two CFL's is also a CFL.

A
True
B
False
       Theory-of-Computation       Context-Free-Language       GATE 1987
Question 201 Explanation: 
Context free language is not closed under intersection.
Question 202

A is recursive if both A and its complement are accepted by Turing machines.

A
True
B
False
       Theory-of-Computation       Turing Machines       GATE 1987
Question 202 Explanation: 
If A is decidable, then A and A' are accepted by Turing machine.
Question 203

A context-free grammar is ambiguous if:

A
The grammar contains useless non-terminals.
B
It produces more than one parse tree for some sentence.
C
Some production has two non terminals side by side on the right-hand side.
D
None of the above.
       Theory-of-Computation       Contest-Free-Grammar       GATE 1987
Question 203 Explanation: 
An ambiguous grammar produces more than one parse tree for some string.
Question 204

FORTRAN is a:

A
Regular language.
B
Context-free language.
C
Context-sensitive language.
D
None of the above.
       Theory-of-Computation       Identify-Class-Language       GATE 1987
Question 204 Explanation: 
Due to presence of some features FORTRAN cannot be handled by PDA.
Some of the features are:
1) Variable declared before use.
2) Matching formal and actual parameters of functions.
Question 205

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?

A
m ≤ 2n
B
n ≤ m
C
M has one accept state
D
m = 2n
       Theory-of-Computation       Finite-Automata       GATE 2008-IT
Question 205 Explanation: 
Set of states of NFA = n
A state in a DFA is a proper subset of states of NFA of corresponding DFA.
→ No. of subsets with n elements = 2n
→ m ≤ 2n
Question 206

If the final states and non-final 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?

A
Set of all strings that do not end with ab
B
Set of all strings that begin with either an a or a b
C
Set of all strings that do not contain the substring ab
D
The set described by the regular expression b*aa*(ba)*b*
       Theory-of-Computation       Finite-Automata       GATE 2008-IT
Question 206 Explanation: 

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 207

Consider the following languages.

L1 = {ai bj ck | i = j, k ≥ 1}
L1 = {ai bj | j = 2i, i ≥ 0}
Which of the following is true?
A
L1 is not a CFL but L2 is
B
L1 ∩ L2 = ∅ and L1 is non-regular
C
L1 ∪ L2 is not a CFL but L2 is
D
There is a 4-state PDA that accepts L1, but there is no DPDA that accepts L2
       Theory-of-Computation       Identify-Class-Language       GATE 2008-IT
Question 207 Explanation: 
→ Both L1 and L2 are CFL. So option A is false.
→ L1 ∩ L2 = ∅, True and also L1 is non-regular. Option B is true.
→ L1 ∪ L2 is not a CFL but L2 is CFL is closed under union. So option C is false.
→ Both L1 and L2 accepted by DPDA.
Question 208

Consider a CFG with the following productions.

S → AA | B 
A → 0A | A0 | 1 
B → 0B00 | 1
S is the start symbol, A and B are non-terminals and 0 and 1 are the terminals. The language generated by this grammar is
A
{0n 102n | n ≥ 1}
B
{0i 10j 10k | i, j, k ≥ 0} ∪ {0n 102n | n ≥ l}
C
{0i 10j | i, j ≥ 0} ∪ {0n 102n | n ≥ l}
D
The set of all strings over {0, 1} containing at least two 0’s
E
None of the above
       Theory-of-Computation       Contest-Free-Grammar       GATE 2008-IT
Question 208 Explanation: 
S → AA | B
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. Non-terminal B i s generating the second part of B choice and AA is generating the first part.
{0i 10j 10k | i, j, k ≥ 0} ∪ {0n 102n | n ≥ 0}
Question 209

Which of the following languages is (are) non-regular? L1 = {0m1n | 0 ≤ m ≤ n ≤ 10000} L2 = {w | w reads the same forward and backward} L3 = {w ∊ {0, 1} * | w contains an even number of 0's and an even number of 1's}

A
L2 and L3 only
B
L1 and L2 only
C
L3 only
D
L2 only
       Theory-of-Computation       Identify-Class-Language       GATE 2008-IT
Question 209 Explanation: 
L1 and L3 are regular.
L1 is limited to fixed range and L3 contains even number of 0's which is regular. No need to use more memory to implement L3.
Question 210

Consider the following two finite automata. M1 accepts L1 and M2 accepts L2.

Which one of the following is TRUE?
A
L1 = L2
B
L1 ⊂ L2
C
L1 ∩ L2‘ = ∅
D
L1 ∪ L2 ≠ L1
E
A and C
       Theory-of-Computation       Finite-Automata       GATE 2008-IT
Question 210 Explanation: 
In this L1 = (0+10)* 11(0+1)*
L2 = (0=1)* 11(0+1)*
Both L1 and L2 are equal.
Option A is correct.
→ L1 ∩ L2‘ = L1 ∩ L1‘ = ∅ (option C also correct)
Question 211

A CFG G is given with the following productions where S is the start symbol, A is a non-terminal and a and b are terminals.

S → aS∣A
A → aAb∣bAa∣ϵ
Which of the following strings is generated by the grammar above?
A
aabbaba
B
aabaaba
C
abababb
D
aabbaab
       Theory-of-Computation       Contest-Free-Grammar       GATE 2008-IT
Question 211 Explanation: 
S→aS
S→aA
S→aaAb
S→aabAab
S→aabbAaab
S→aabbaab
Question 212

A CFG G is given with the following productions where S is the start symbol, A is a non-terminal 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?
A
6 and 1
B
6 and 2
C
7 and 2
D
4 and 2
       Theory-of-Computation       Contest-Free-Grammar       GATE 2008-IT
Question 212 Explanation: 
S→aS
S→aA
S→aaAb
S→aabAab
S→aabbAaab
S→aabbaab
⇒ 6 steps are required

Only 1 parse tree is there.
Question 213

Consider the following DFA in which s0 is the start state and s1, s3 are the final states.

What language does this DFA recognize ?

A
All strings of x and y
B
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
C
All strings of x and y which have equal number of x and y
D
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
       Theory-of-Computation       Finite-Automata       GATE 2007-IT
Question 213 Explanation: 
Just simulate the running of the DFA on all options - A, B and C are false and D is true.
Question 214

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 ?

A
(i), (ii), and (iii)
B
(ii), (v), and (vi)
C
(ii), (iii), and (iv)
D
(i), (iii), and (iv)
       Theory-of-Computation       Grammar       GATE 2007-IT
Question 214 Explanation: 
(ii) xxyyxy
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 215

Consider the following grammars. Names representing terminals have been specified in capital letters.

G1: stmnt → WHILE (expr) stmnt
    stmnt → OTHER
    expr → ID
G2: WHILE (expr) stmnt
    stmnt → OTHER
    expr → expr + expr
    expr → expr * expr
    expr → ID   

Which one of the following statements is true?

A
G1 is context-free but not regular and G2 is regular
B
G2 is context-free but not regular and G1 is regular
C
Both G1 and G2 are regular
D
Both G1 and G2 are context-free but neither of them is regular
       Theory-of-Computation       Identify-Class-Language       GATE 2007-IT
Question 215 Explanation: 
Regular grammar is either right linear or left linear. A left linear grammar is one in which there is atmost 1 non-termial on the right side of any production, and it appears at the left most position.
Similarly, in right linear grammar, non-terminal appears at the right most position.
Here we can write a right linear grammar for G1 as
S → w(E
E → id)S
S → o
(w-while, o-other)
So, L(G1) is regular.
Now for G2 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 G1 and G2 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 216

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:

A
B
C
D
       Theory-of-Computation       Finite-Automata       GATE 2007-IT
Question 216 Explanation: 
String 'aca' is accepted by both FA, P and Q. And FA in option (A) also accepts string 'aa' and none of the other option FA accepts 'aa'. Hence option (A) is the answer.
Question 217

Consider the regular expression

 R = (a + b)* (aa + bb) (a + b)* 
Which of the following non-deterministic finite automata recognizes the language defined by the regular expression R? Edges labeled λ denote transitions on the empty string.

A
B
C
D
       Theory-of-Computation       Regular-Expressions       GATE 2007-IT
Question 217 Explanation: 
Every string of given regular expression must contain the substring aa or bb.
But option (B), (C), (D) accepts aba, which do not contain aa or bb as substring.
Hence, (A) is correct.
Question 218

Consider the regular expression

 R = (a + b)* (aa + bb) (a + b)* 
Which deterministic finite automaton accepts the language represented by the regular expression R ?

A
B
C
D
       Theory-of-Computation       Regular-Expressions       GATE 2007-IT
Question 218 Explanation: 
(B) It accepts 'ab' which is not in the language.
(C) It is not accepting 'abb' which is in language.
(D) It is not accepting 'aa' and 'bb' which is in language.
Question 219

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
(a(ba)* + b(ab)*)(a + b)+
B
(a(ba)* + b(ab)*)*(a + b)*
C
(a(ba)* (a + bb) + b(ab)*(b + aa))(a + b)*
D
(a(ba)* (a + bb) + b(ab)*(b + aa))(a + b)+
       Theory-of-Computation       Regular-Expressions       GATE 2007-IT
Question 219 Explanation: 
R = (a+b)* (aa+bb) (a+b)*
Having NFA:

Equivalent DFA:
Question 220

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?

A
The automaton accepts u and v but not w
B
The automaton accepts each of u, v, and w
C
The automaton rejects each of u, v, and w
D
The automaton accepts u but rejects v and w
       Theory-of-Computation       Finite-Automata       GATE 2006-IT
Question 220 Explanation: 
(i) u = abbaba

where t is final state
(ii) v = bab

s is not final state
(iii) w = aabb

s is not final state
Question 221

In the context-free 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?

A
aaaa
B
baba
C
abba
D
babaaabab
       Theory-of-Computation       Contest-Free-Grammar       GATE 2006-IT
Question 221 Explanation: 
S → aSa | bSb | a | b | ϵ
Given string accepts all palindromes.
Option B → baba is not palindrome.
So, this is not accepted by S.
Question 222

Which regular expression best describes the language accepted by the non-deterministic automaton below?

A
(a + b)* a(a + b)b
B
(abb)*
C
(a + b)* a(a + b)* b(a + b)*
D
(a + b)*
       Theory-of-Computation       Regular-Expressions       GATE 2006-IT
Question 222 Explanation: 
Question 223

Consider the regular grammar below

S → bS | aA | ϵ
A → aS | bA 

The Myhill-Nerode equivalence classes for the language generated by the grammar are

A
{w ∈ (a + b)* | #a(w) is even) and {w ∈ (a + b)* | #a(w) is odd}
B
{w ∈ (a + b)* | #a(w) is even) and {w ∈ (a + b)* | #b(w) is odd}
C
{w ∈ (a + b)* | #a(w) = #b(w) and {w ∈ (a + b)* | #a(w) ≠ #b(w)}
D
{ϵ}, {wa | w ∈ (a + b)* and {wb | w ∈ (a + b)*}
       Theory-of-Computation       Regular-Grammar       GATE 2006-IT
Question 223 Explanation: 

⇒ This results even number, no. of a's.
Question 224

Which of the following statements about regular languages is NOT true?

A
Every language has a regular superset
B
Every language has a regular subset
C
Every subset of a regular language is regular
D
Every subset of a finite language is regular
       Theory-of-Computation       Regular Languages       GATE 2006-IT
Question 224 Explanation: 
Regular languages are not closed under subset.
Question 225

Which of the following languages is accepted by a non-deterministic pushdown automaton (PDA) but NOT by a deterministic PDA?

A
{anbncn ∣ n≥0}
B
{albmcn ∣ l≠m or m≠n}
C
{anbn ∣ n≥0}
D
{ambn∣ m,n≥0}
       Theory-of-Computation       Push-Down-Automata       GATE 2006-IT
Question 225 Explanation: 
At a time, the DPDA can compare 'a' and 'b' or 'b' and 'c' but not both.
To compare both conditions at the same time, we need a NPDA.
Question 226

Let L be a context-free language and M a regular language. Then the language L ∩ M is

A
always regular
B
never regular
C
always a deterministic context-free language
D
always a context-free language
       Theory-of-Computation       Identify-Class-Language       GATE 2006-IT
Question 226 Explanation: 
CFL is closed under regular intersection.
Question 227

Consider the pushdown automaton (PDA) below which runs over the input alphabet (a, b, c). It has the stack alphabet {Z0, X} where Z0 is the bottom-of-stack 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, XZ0) 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 Z0 and X (in that order) on the stack.

(s, a, Z0) → (s, XXZ0)
(s, ϵ, Z0) → (f, ϵ)
(s, a, X) → (s, XXX)
(s, b, X) → (t, ϵ)
(t, b, X) → (t,.ϵ)
(t, c, X) → (u, ϵ)
(u, c, X) → (u, ϵ)
(u, ϵ, Z0) → (f, ϵ) 

The language accepted by the PDA is

A
{albmcn | l = m = n}
B
{albmcn | l = m}
C
{albmcn | 2l = m+n}
D
{albmcn | m=n}
       Theory-of-Computation       Push-Down-Automata       GATE 2006-IT
Question 227 Explanation: 

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., {albmcn | 2l = m+n}
Question 228

In the context-free 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
((a + b)* b)*
B
{ambn | m ≤ n}
C
{ambn | m = n}
D
a* b*
       Theory-of-Computation       Contest-Free-Grammar       GATE 2006-IT
Question 228 Explanation: 
Option A:
((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 229

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

A
S+ = S’ . y’ + S . x
B
S+ = S. x . y’ + S’ . y . x’
C
S+ = x . y’
D
S+ = S’ . y + S . x’col
       Theory-of-Computation       Finite-Automata       GATE 2006-IT
Question 229 Explanation: 

From the table:
S' = S'y' + Sx
Question 230

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 non-regular language?

A
Both I and IV
B
Only I
C
Only IV
D
Both II and III
       Theory-of-Computation       Regular-Language       GATE 2006-IT
Question 230 Explanation: 
Repeat(L) = {ww|w ∈ L} is non-regular language.
Half (L), Suffix (L) and Prefix (L) are regular languages.
Question 231

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
(a + b)*
B
{ϵ, a, ab, bab}
C
(ab)*
D
{anbn | n ≥ 0}
       Theory-of-Computation       Regular-Language       GATE 2006-IT
Question 231 Explanation: 
A counter example which proves all the conclusions of the last question in one go should have the following properties:
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 232

Let L be a regular language and M be a context-free language, both over the alphabet Σ. Let Lc and Mc denote the complements of L and M respectively. Which of the following statements about the language if Lc ∪ Mc is TRUE?

A
It is necessarily regular but not necessarily context-free.
B
It is necessarily context-free.
C
It is necessarily non-regular.
D
None of the above.
       Theory-of-Computation       Regular Languages and finite automata       GATE 2005-IT
Question 232 Explanation: 
Context-free languages not closed under complementation. So, Lc ∪ Mc is neither regular nor context-free. It might be context sensitive language.
Question 233

Which of the following statements is TRUE about the regular expression 01*0?

A
It represents a finite set of finite strings.
B
It represents an infinite set of finite strings.
C
It represents a finite set of infinite strings.
D
It represents an infinite set of infinite strings.
       Theory-of-Computation       Regular languages and finite automata       GATE 2005-IT
Question 233 Explanation: 
The given expression 01*0 is regular. So this is a finite string. So options C and D are false and * is placed. So this is infinite set.
So, given regular expression represents an infinite set of finite strings.
Question 234

The language {0n 1n 2n | 1 ≤ n ≤ 106} is

A
regular
B
context-free but not regular
C
context-free but its complement is not context-free
D
not context-free
       Theory-of-Computation       Regular languages and finite automata       GATE 2005-IT
Question 234 Explanation: 
In this the value of n is finite then we can be able to construct a finite state automata for this language.
So, given language is regular.
Question 235

Which of the following expressions is equivalent to (A⊕B)⊕C

A
B
C
D
None of these
       Theory-of-Computation       Logical-Functions-and-Minimization       GATE 2005-IT
Question 235 Explanation: 
(A⊕B)⊕C
⇒ 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 236

Consider the non-deterministic 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.

A
L1 = L2
B
L1 ⊂ L2
C
L2 ⊂ L1
D
None of the above
       Theory-of-Computation       Regular Languages and Finite Automata       GATE 2005-IT
Question 236 Explanation: 
Based on Arden's theorem write the Y and Z in terms of incoming arrows,
Y = X0 + Y0 + Z1
Z = X0 + Y0 + Z;
⇒ X = Z;
⇒ L1 = L2
Question 237

Let P be a non-deterministic push-down 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?

A
L(P) is necessarily Σ* but N(P) is not necessarily Σ*
B
N(P) is necessarily Σ* but L(P) is not necessarily Σ*
C
Both L(P) and N(P) are necessarily Σ*
D
Neither L(P) nor N(P) are necessarily Σ*
       Theory-of-Computation       Push-Down-Automata       GATE 2005-IT
Question 237 Explanation: 
Since, it is NPDA, so we might not have any transitions over any alphabet. So option (D) is correct.
Question 238

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 non-terminals 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?

A
2
B
3
C
4
D
5
       Theory-of-Computation       DFA       GATE 2005-IT
Question 238 Explanation: 
L = {aa, aaa, aaaaa, ...}
The minimum string length is 2 [aa], so we require 3 states to construct DFA.
Question 239

A language L satisfies the Pumping Lemma for regular languages, and also the Pumping Lemma for context-free languages. Which of the following statements about L is TRUE?

A
L is necessarily a regular language
B
L is necessarily a context-free language, but not necessarily a regular language
C
L is necessarily a non-regular language
D
None of the above
       Theory-of-Computation       Pumping-lemma       GATE 2005-IT
Question 239 Explanation: 
As we know that pumping lemma is a negative test, which can be use to disprove the given language is not regular. But reverse is not True.
Question 240

Consider the context-free 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}.
Which of the following terminal strings has more than one parse tree when parsed according to the above grammar?

A
id + id + id + id
B
id + (id* (id * id))
C
(id* (id * id)) + id
D
((id * id + id) * id)
       Theory-of-Computation       Regular languages and finite automata       GATE 2005-IT
Question 240 Explanation: 
Let's draw more than one possible tree for id + id + id + id.
Question 241

Consider the context-free 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 non-terminals is {E}.
For the terminal string id + id + id + id, how many parse trees are possible?

A
5
B
4
C
3
D
2
       Theory-of-Computation       CFG       GATE 2005-IT
Question 241 Explanation: 
Total 5 parse trees possible (solved in previous question).
Question 242

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) && E1) 
       j++;
    if (j < n) E2;
} while (j < n);

flag = 1;
for (j = 0; j < n; j++)
    if ((j! = i) && E3)
        flag = 0;

if (flag)
    printf("Sink exists");
else
    printf ("Sink does not exist"); 
Choose the correct expressions for E1 and E2 

A
E1 : A[i][j] and E2 : i = j;
B
E1 : !A[i][j] and E2 : i = j + 1;
C
E1: !A[i][j] and E2 : i = j;
D
E1 : A[i][j] and E2 : i = j + 1;
       Theory-of-Computation       Graphs       GATE 2005-IT
Question 242 Explanation: 
If there is a sink in the graph, the adjacency matrix will contain all 1's (except diagonal) in one column and all 0's (except diagonal) in the corresponding row of that vertex. The given algorithm is a smart way of doing this as it finds the sink in O(n) time complexity.
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 E2, 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
E1: A[i][j]
and
E2: i = j
E1 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 E2, we must make i = j.
So, answer is (C).
Question 243

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) && E1) j++;
    if (j < n) E2;
} while (j < n);

flag = 1;
for (j = 0; j < n; j++)
    if ((j! = i) && E3)
        flag = 0;

if (flag)
    printf("Sink exists");
else
    printf("Sink does not exist"); 
Choose the correct expressions for E3

A
(A[i][j] && !A[j][i])
B
(!A[i][j] && A[j][i])
C
(!A[i][j] | | A[j][i])
D
(A[i][j] | | !A[j][i])
       Theory-of-Computation       Graphs       GATE 2005-IT
Question 243 Explanation: 
First go through the explanation of previous question.
Now, the loop breaks when we found a potential sink-that 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, E3 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 E3 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 244

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.

A
B
C
D
       Theory-of-Computation       Graphs       GATE 2005-IT
Question 244 Explanation: 



Question 245

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

A
>100 but finite
B
C
3
D
>3 and ≤100
       Theory-of-Computation       Graphs       GATE 2005-IT
Question 245 Explanation: 
We consider ABDF at t, they are:
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 246

Which one of the following regular expressions is NOT equivalent to the regular expression (a + b + c)*?

A
(a* + b* + c*)*
B
(a*b*c*)*
C
((ab)* + c*)*
D
(a*b* + c*)*
       Theory-of-Computation       Regular-Expressions       GATE 2004-IT
Question 246 Explanation: 
With the given r.e. (a+b+c)* we can generate "a".
From option 'c' we cannot be able to create a without b. So option is not equivalent.
Question 247

Which one of the following statements is FALSE?

A
There exist context-free languages such that all the context-free grammars generating them are ambiguous
B
An unambiguous context free grammar always has a unique parse tree for each string of the language generated by it
C
Both deterministic and non-deterministic pushdown automata always accept the same set of languages
D
A finite set of string from one alphabet is always a regular language
       Theory-of-Computation       General       GATE 2004-IT
Question 247 Explanation: 
Deterministic automata can be able to recognize all the deterministic context-free languages.
But non-deterministic ones can recognize all context-free languages.
So, option C is false.
Question 248

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,ε))}

A
aaa
B
aabab
C
baaba
D
bab
       Theory-of-Computation       Push-Down-Automata       GATE 2004-IT
Question 248 Explanation: 
First let's draw PDA,

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 249

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
{A→aB, A→bA, B→bA, B→aA, B→ε}
B
{A→aA, A→bB, B→bB, B→aA, B→ε}
C
{A→bB, A→aB, B→aA, B→bA, A→ε}
D
{A→aA, A→bA, B→bB, B→aA, A→ε}
       Theory-of-Computation       Finite-Automata       GATE 2004-IT
Question 250
A language with string manipulation facilities uses the following operations. concat(sl, s2)- concatenates string s1 with s2. The output of concat(head(s), head(tail(tail(s)))), where s is acbc is
A
ab
B
ba
C
ac
D
as
       Theory-of-Computation       Languages-and-Grammars       ISRO-2018
Question 250 Explanation: 
Question 251
Choose the correct statement:
A
A = {an bn | n = 1, 2, 3, …. } is a regular language
B
The set B, consisting of all strings made up of only a’s and b’s having an equal number of a’s and b’s defines a regular language
C
L(A * B) ∩ B gives the set A
D
None of the above
       Theory-of-Computation       Regular-Language       ISRO-2018
Question 251 Explanation: 
Option A: False: A = {an bn | n=1,2,3,…. } is Deterministic Context Free Language(DCFL) but not regular.
Option B: False: Equal number of a's and equal number of b's is also DCFL but not regular
Option C: False: L(A*B) ∩ B gives the set B but not set A.
L(A*B)= {AB+ AAB + …+AAAAB+B}
L(A*B)∩B=B
Question 252
CFG (Context Free Grammar) is not closed under
A
Union
B
Complementation
C
Kleene star
D
Product
       Theory-of-Computation       Context-Free-Language       ISRO-2018
Question 252 Explanation: 
CFG (Context Free Grammar) is not closed under complementation
Question 253
The FSM (Finite State Machine) machine pictured in the figure below
A
Complements a given bit pattern
B
Finds 2’s complement of a given bit pattern
C
Increments a given bit pattern by 1
D
Changes the sign bit
       Theory-of-Computation       Finite-Automata       ISRO-2018
Question 253 Explanation: 
Let consider an example string:
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 254
A CFG(Context Free Grammar) is said to be in Chomsky Normal Form (CNF), if all the productions are of the form A→ BC or A→ a. Let G be a CFG in CNF. To derive a string of terminals of length x, the number of products to be used is
A
2x – 1
B
2x
C
2x + 1
D
2x
       Theory-of-Computation       Context-Free-Language       ISRO-2018
Question 254 Explanation: 
Explanation:
→ For CNF, it is 2x - 1
→ For GNF, it is x
Question 255
Consider the grammar
S → ABCc ∣ bc
BA → AB
Bb → bb
Ab → ab
Aa → aa
Which of the following sentences can be derived by this grammar?
A
abc
B
aab
C
abcc
D
abbc
       Theory-of-Computation       Context-Free-Language       ISRO CS 2008
Question 255 Explanation: 
C is useless in S→ABCc so remove it.
S→ABc
Now see each of remaining production
Bb→bb ( i.e. B→b)
Ab→ab (i.e.A→a)
Aa→aa (i.e. A→a)
So
S→ABc→abc
Question 256
Given the following statements:
S1 : Every context-sensitive language L is recursive
S2 : There exists a recursive language that is not context-sensitive
Which statements are true?
A
Only S1 is correct
B
Only S2 is correct
C
Both S1 and S2 are not correct
D
Both S1 and S2 are correct
       Theory-of-Computation       Languages-and-Grammars       ISRO-2017 May
Question 256 Explanation: 
According to the Chomsky hierarchy, both the statements are correct.

Question 257
Which one of the following is FALSE?
A
There is a unique minimal DFA for every regular language
B
Every NFA can be converted to an equivalent PDA
C
The complement of every context-free language is recursive
D
Every non-deterministic PDA can be converted to an equivalent deterministic PDA
       Theory-of-Computation       Equivalence-of-Languages       ISRO-2017 May
Question 257 Explanation: 
→ NPDA is more powerful than DPDA because
1. DPDA accept only a proper subset of CFL's ie. LL grammars.
2. NPDA can accept any CFL, which makes them more powerful over DPDA
3. Every NPDA can not be converted to an equivalent DPDA
Question 258
In some programming languages, an identifier is permitted to be a letter followed by any number of letters or digits. If L and D denotes the set of letters and digit respectively. Which of the following expression defines an identifier?
A
(L + D)*
B
(L.D)*
C
L(L + D)*
D
L(L.D)*
       Theory-of-Computation       Regular-Expression       ISRO-2017 May
Question 258 Explanation: 
Option C is correct because it indicates L followed by (L + D)* where * means 0 or more occurences of L or D.
Question 259
If L and P are two recursively enumerable languages, then they are not closed under
A
Kleene Star L * of L
B
Intersection L ∩ P
C
Union L ∪ P
D
Set Difference
       Theory-of-Computation       Recursive-and-Recursively-Enumerable-Language       ISRO-2017 May
Question 259 Explanation: 
→ Recursively Enumerable problems are not closed under Complementation.
→ Set Difference A – B can be written as A ∩ B’ where B’ denotes complementation of B. So we can say that Recursively Enumerable problems are not closed under Set Difference
Question 260
For Σ={a,b} the regular expression r = (aa)*(bb)*b denotes
A
Set of strings with 2 a’s and 2 b’s
B
Set of strings with 2 a’s 2 b’s followed by b
C
Set of strings with 2 a’s followed by b’s which is a multiple of 3
D
Set of strings with even number of a’s followed by odd number of b’s
       Theory-of-Computation       Regular-Expression       ISRO-2017 December
Question 260 Explanation: 
→ Given expression denotes language that accepts set of all strings with even number of a’s followed by the odd number of b’s.
→ Because (aa)* implies even number of a's and (bb)*b implies even number of b's followed by one b , it implies the odd number of b's.
Question 261
Consider the grammar with productions S → aSb | SS | ϵ This grammar is
A
not context-free, not linear
B
not context-free, linear
C
context-free, not linear
D
context-free, linear
       Theory-of-Computation       Context-Free-Language       ISRO-2017 December
Question 261 Explanation: 
Linear grammar means regular grammar which is in the form of A→ Ba | b (or) A→ aB|b
and Context free grammar is in the form of A→ ɑ where ɑ = (V⋃T)^*
V → set of terminals and T → set of non-terminals
It is clearly seen that given grammar is not linear but context-free.
Question 262
Identify the language generated by the following grammar
S -> AB
A -> aAb|ϵ
B -> bB| b
A
{ambn | n>=m, m>0}
B
{ambn | n>=m, m>=0}
C
{ambn | n>m, m>0}
D
{ambn | n>m, m>=0}
       Theory-of-Computation       Languages-and-Grammars       ISRO-2017 December
Question 262 Explanation: 
The language generated by given grammar is - L={b,bb,abb,abbb,ababb}
Hence it is ambn | n>m, m>=0
Question 263
Let L1 be regular language, L2 be a deterministic context free language and L3 a recursively enumerable language, but not recursive. Which one of the following statements is false?
A
L1 ∩ L2 is context-free
B
L3 ∩ L1 is recursive
C
L1 ∪ L2 is context-free
D
L1 ∩ L2 ∩ L3 is recursively enumerable
       Theory-of-Computation       Recursive-and-Recursively-Enumerable-Language       ISRO-2017 December
Question 263 Explanation: 
→ Option A is true, as by closure property (R is a regular language and L is any language)
L ∩ R = L ( i.e. L Intersection R is same type as L )
So L1 ∩ L2 is a deterministic CFL.
→ Option B is false, as L3 is recursive enumerable but not recursive, so intersection with L1 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, L1 ∪ L2 is deterministic context free, hence it is also context free.
→ Option D is true, as L1 ∩ L2 is DCFL and DCFL ∩ L3 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 264
Let L = {ap| p is a prime}.
Then which of the following is true?
A
It is not accepted by a Turing Machine
B
It is regular but not context-free
C
It is context-free but not regular
D
It is neither regular nor context-free but accepted by a Turing Machine
       Theory-of-Computation       Context-Free-Language       ISRO-2017 December
Question 264 Explanation: 
L = {ap | p is a prime}
L can only be accepted by a Turing machine
Question 265
A FSM(finite state machine) can be considered to be a turing machine of finite tape length
A
without rewinding capability and unidirectional tape movement
B
rewinding capability and unidirectional tape movement
C
without rewinding capability and bidirectional tape movement
D
rewinding capability and bidirectional tape movement
       Theory-of-Computation       Finite-Automata       ISRO-2016
Question 265 Explanation: 
→ A FSM(finite state machine) can be considered to be a turing machine of finite tape length without rewinding capability and unidirectional tape movement.
→ The finite state machine has less computational power than some other models of computation such as the Turing machine.
→ The computational power distinction means there are computational tasks that a Turing machine can do but a FSM cannot. This is because a FSM's memory is limited by the number of states it has.
→ A finite state machine has the same computational power as a Turing machine that is restricted such that its head may only perform "read" operations, and always has to move from left to right. That is, each formal language accepted by a finite state machine is accepted by such a kind of restricted Turing machine, and vice versa.
Question 266
Let L = {w = (0+1)* | w has even number of 1’s}, i.e. L is the set of all bit strings with even number of 1’s. Which one of the regular expression below represents L ?
A
(0*10*1)*
B
0*(10*10*)*
C
0*(10*1*)*0*
D
0*1(10*1)10*
       Theory-of-Computation       Regular-Expression       ISRO-2016
Question 266 Explanation: 
→ The best way to find correct answer is option elimination method.
→ We will guess strings which has even number of 1’s and that is not generated by wrong options OR which generate strings which doesn’t have even number of 1’s.
Option A: (Regular expression: (0*10*1)* ) doesn’t generate string such as { 110, 1100,....}
Option C: (Regular expression: 0*(10*1*)*0* generate string such as {1, 111,....} which have odd number of 1’s.
Option D: (Regular expression: 0*1(10*1)*10* doesn’t generate strings such as { 11101, 1111101, ….}.
Question 267
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 an 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?
A
I only
B
I and III only
C
II and III only
D
I, II and III
       Theory-of-Computation       Context-Free-Language       ISRO-2016
Question 267 Explanation: 
Is ambiguous, as it has two parse tree for the string “abbaba”

G doesn’t produce all strings of an 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 268
If L and L’ are recursively enumerable then L is
A
Regular
B
Context-free
C
Context Sensitive
D
Recursive
       Theory-of-Computation       Recursive-and-Recursively-Enumerable-Language       ISRO-2016
Question 268 Explanation: 
→ If L is recursive enumerable, then it implies that there exist a Turing Machine (lets say M1) which always HALT for the strings which is in L.
→ If L’ 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 L’ 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 269
S → aSa ∣ bSb ∣ a ∣ b The language generated by the above grammar over the alphabet is the set of
A
all palindromes
B
all odd length palindromes
C
strings that begin and end with the same symbol
D
all even length palindromes
       Theory-of-Computation       Languages-and-Grammars       ISRO-2016
Question 269 Explanation: 
From the grammar, we can easily infer that it generates all the palindromes of odd length, for ex: strings {aba, bab, aaa, bbb, ….}
Question 270
What is the highest type number that can be assigned to the following grammar?
S → Aa
A → Ba
B → abc
A
Type 0
B
Type 1
C
Type 2
D
Type 3
       Theory-of-Computation       Languages-and-Grammars       ISRO-2016
Question 270 Explanation: 
Grammar is belongs to Type 0 ,Type 1,Type 2,Type 3 because it is regular. Option D is right answer because they are asking only highest type number.
Question 271
A problem whose language is recursive is called?
A
Unified problem
B
Boolean function
C
Recursive problem
D
Decidable
       Theory-of-Computation       Resursive       ISRO CS 2011
Question 271 Explanation: 
A formal language (a set of finite sequences of symbols taken from a fixed alphabet) is called recursive if it is a recursive subset of the set of all possible finite sequences over the alphabet of the language.
Equivalently, a formal language is recursive if there exists a total Turing machine (a Turing machine that halts for every given input) that, when given a finite sequence of symbols as input, accepts it if it belongs to the language and rejects it otherwise.
Recursive languages are also called decidable.
Question 272

Which of the following sentences can be generated by

S -> aS | bA

A -> d | cA

A
bccdd
B
abbcca
C
abcabc
D
abcd
       Theory-of-Computation       Context-free-language       ISRO CS 2011
Question 272 Explanation: 
Given language:
S -> aS | bA
A -> d | cA
From the given productions, it is not possible to derive the sentence bccdd(two consecutive d’s).So option A is not correct.
In the string “abbcca”, there are two consecutive c’s followed by the letter ‘a’, This can’t be derived from the given productions,
From the given productions, it is also not possible to derive string which consists of the letter ‘c’ followed by ‘a’ , So the option (c ) also not correct
From given productions, we can generate the string “abcd”
Question 273
What are the final states of the DFA generated from the following NFA?
A
q0, q1, q2
B
[q0, q1], [q0, q2], [ ]
C
q0, [q1, q2]
D
[q0, q1], q2
       Theory-of-Computation       DFA       ISRO CS 2013
Question 273 Explanation: 
→An epsilon transition allows an automaton to change its state spontaneously, i.e. without consuming an input symbol.
→From the diagram, initially “q2” is final state.
→As there is epsilon transitions from qo to q1 and q1 to q2 and finally we reach the end state so q0,q1 are part of final states then q0,q1 and q2 are final states.
Question 274
The number of states required by a Finite State Machine, to simulate the behavior of a computer with a memory capable of storing ‘m’ words, each of length ‘n’ bits is?
A
m x 2n
B
2m+n
C
2mn
D
m+n
       Theory-of-Computation       Finite-Automata       ISRO CS 2014
Question 274 Explanation: 
A finite-state machine (FSM) an abstract machine that can be in exactly one of a finite number of states at any given time. The FSM can change from one state to another in response to some external inputs; the change from one state to another is called a transition.
Generally FSM consists of 2x states for a given input x.
But in the question, the input is specified number of words and length of each word.
For a given, ‘m’ words, each of length ‘n’ bits, so total number of bits are m*n
So, total number of states required by a Finite State Machine are 2mn.
Question 275
What is the number of steps required to derive the string ((() ()) ()) for the following grammar?
S → SS
S → (S)
S → ε
A
10
B
15
C
12
D
16
       Theory-of-Computation       Languages-and-Grammars       ISRO CS 2014
Question 275 Explanation: 
The required string consists of only only matched parenthesis enclosed with parentheses.
To generate the string ((() ()) ()) , we need to perform the steps sequentially.
As the string starts with left parentheses, we will start with the production S → (S).
Depending upon the string we will go for either left or right tree generation.
1) S → (S) // Replacing S by (S)
2) S → (SS) // Replacing by S by SS
3) S → ((S)S) //Replacing S by(S)
4) S → ((SS)S)// Replacing S by SS
5) S → (((S)S))S)
6) S → (((S)(S))S)
7) S → (((S)(S))(S)) [S → ε]
8) S → ((()(S))S) [S → ε]
9) S → ((()())S) [S → ε]
10) S → ((()()))
Question 276
How many states are there in a minimum state deterministic finite automaton accepting the language L = {w | w {0,1} number of 0’s is divisible by 2 and number of 1’s is divisible by 5, respectively} ?
A
7
B
9
C
10
D
11
       Theory-of-Computation       Finite-Automata       ISRO CS 2014
Question 276 Explanation: 
From the given data
String which consists of 0’s and 1’s
Language is number of 0’s is divisible by 2 and number of 1’s is divisible by 5
Machine is minimum state deterministic finite automaton
The set of strings generated by {0,1} are ={ε,0,1,00,11,01,10,000,011,010 .. and so on}
The strings which are generated by language which is specified in the questions are
{ ε , 00, 11111, 0011111, 0011111 , 1111100, 1010111 , 000011111,….and so on }
So, strings accepted by the automaton have to be of length 0, 2, 4, 5, 6, 7, 8, 9, 10, 11, 14, 12….and so on, i.e. equation for length will be 2x + 5y (where x,y>=0 )
Number of 0’s divisible by 2 means , the possible remainders are 0 and 1 i.e; 2
Number of 1’s divisible by 5 means , the possible remainders are 4,3,2,1,0 i.e; 5
Total number of states are 2*5 =10
Question 277
The following Finite Automaton recognizes which of the given languages?
A
{1, 0}* {01}
B
{1, 0}* {1}
C
{1}{1, 0}* {1}
D
1*0* {0, 1}
       Theory-of-Computation       Finite-Automata       ISRO CS 2014
Question 277 Explanation: 
Given DFA accepts all string that ending with “01”, so the language should be (0+1)*01.
Question 278
Consider the following Deterministic Finite Automaton.

Let denote the set of eight bit strings whose second, third, sixth and seventh bits are 1. The number of strings in that are accepted by M is
A
0
B
1
C
2
D
3
       Theory-of-Computation       Finite-Automata       ISRO CS 2014
Question 278 Explanation: 
According to DFA transition diagram, the possible strings accepted by M is
01110110
01110111
Above two strings are are having constraint that 2nd, 3rd, 6th and 7th bits are 1. So, it satisfied above condition.
Question 279
Consider the following grammar.
S → AB
A → a
A → BaB
B → bbA
Which of the following statements is FALSE?
A
The length of every string produced by this grammar is even