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       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       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       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       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 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 5 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 6
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 6 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 7
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 7 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 8

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 8 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 9

Consider the following problems. L(G) denotes the language generated by a grammar G. L(M) denotes the language accepted by a machine M.

    (I) For an unrestricted grammar G and a string w, whether w∈L(G)
    (II) Given a Turing machine M, whether L(M) is regular
    (III) Given two grammar 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 9 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 10
 

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-01
Question 10 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 11

Consider the language L given by the regular expression (a+b)*b(a+b) over the alphabet {a,b}. The smallest number of states needed in deterministic finite-state automation (DFA) accepting L is _________.

A
4
B
5
C
6
D
7
       Theory-of-Computation       Finite-Automata       Gate 2017 set-01
Question 11 Explanation: 
The NFA for regular expression: (a+b)*b(a+b)

After converting the NFA into DFA:

After converting the NFA into DFA:
Question 12

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-01
Question 12 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 13

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-01
Question 13 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 14

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-01
Question 14 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 15

Let A and B be finite alphabets and let # be a symbol outside both A and B. Let f be a total function from A* to B*. We say f is computable if there exists a Turing machine M which given an input x in A*, always halts with f(x) on its tape. Let Ldenote 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-01
Question 15 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 16

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-02)
Question 16 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 17

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-02)
Question 17 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 18

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-02)
Question 18 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 19
 
A
B
{q0,q1,q3}
C
{q0,q1,q2}
D
{q0,q2,q3}
       Theory-of-Computation       NFA       GATE 2017(set-02)
Question 19 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 20

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-02)
Question 20 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 21

Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by a context free grammar G. Let L(M) be the language accepted by a Turing machine M.

Which of the following decision problems are undecidable?

    I. Given a regular expression R and a string w, is w ∈ L(R)?
    II. Given a 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-02)
Question 21 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 22

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       2016 set-01
Question 22 Explanation: 
From the given grammar we can draw the DFA,
Question 23

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       2016 set-01
Question 23 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 24

Which one of the following regular expressions represents the language: the set of all binary strings having two consecutive 0s and two consecutive 1s?

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       2016 set-01
Question 24 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 25

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       2016 set-01
Question 25 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 26

Consider the transition diagram of a PDA given below with input alphabet Σ = {a,b} and stack alphabet Γ = {X,Z}. Z is the initial stack symbol. Let L denote the language accepted by the PDA.

Which one of the following is TRUE?

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       2016 set-01
Question 26 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 27
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       2016 set-01
Question 27 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 28

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 28 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 29

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 29 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 30

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 30 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 31
 

Consider the following two statements:

    I. If all states of an NFA are accepting states then the language accepted by the NFA is Σ*.
    II. There exists a regular language A such that for all languages B, A∩B is regular.

Which one of the following isCORRECT?

 
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 31 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 32

Consider the following languages:

    L1 = {an bm cn+m : m,n ≥ 1}
    L2 = {an bn c2n : n ≥ 1}

Which one of the following isTRUE?

 
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 32 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 33

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 33 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 34
 

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 34 Explanation: 
Both grammars G1 and G2 generate C-array like declaration:
Question 35

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-01)
Question 35 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 36
A
1
B
2
C
3
D
4
       Theory-of-Computation       DFA       GATE 2015 (Set-01)
Question 36 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 37
A
10110
B
10010
C
01010
D
01001
       Theory-of-Computation       PDA       GATE 2015 (Set-01)
Question 37 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 38
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 38 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 39
 
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 39 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 40
 
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 40 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 41
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 41 Explanation: 

No. of states in minimal DFA is 3.
Question 42
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 42 Explanation: 
Convert the given transitions to a state diagram.

From the given diagram we can write,
X0 = 1(0+10)* 1
Question 43
   
A
4
B
5
C
6
D
8
       Theory-of-Computation       Regular-Expressions       GATE 2015(Set-03)
Question 43 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 44
A
II only
B
III only
C
I and IV only
D
I only
       Theory-of-Computation       Reducibility       GATE 2015(Set-03)
Question 44 Explanation: 
L2 ≤ pL4
L1 ≤ pL2
If L4 ∈ P then L2 ∈ P hence L1 ∈ P, hence option C.
Question 45
   
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-03)
Question 45 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 comparision 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 46
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-01)
Question 46 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 47
A
{q0,q1,q2 }
B
{q0,q1 }
C
{q0,q1,q2,q3 }
D
{q3 }
       Theory-of-Computation       Finite-Automata       GATE 2014(Set-01)
Question 47 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 48
   
A
Only (I)
B
Only (II)
C
Both (I) and (II)
D
Neither (I) nor (II)
       Theory-of-Computation       Regular Languages       Gate 2014 Set -02
Question 48 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 49
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 -02
Question 49 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 50
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 -02
Question 50 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 51
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 -02
Question 51 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 52
A
3
B
4
C
5
D
6
       Theory-of-Computation       Regular Languages and Finite Automata       Gate 2014 Set -03
Question 52 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 53
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 -03
Question 53 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 54
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 -03
Question 54 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 55
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 -03
Question 55 Explanation: 
Note: Out of Syllabus.
Question 56
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 -03
Question 56 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 57

Suppose you want to move from 0 to 100 on the number line. In each step, you either move right by a unit distance or you take a shortcut. A shortcut is simply a 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 -03
Question 57 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 58
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 58 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 59
 
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 59 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 60
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 60 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 61
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 61 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 62
     
A
B
{ε}
C
a*
D
{a ,ε}
       Theory-of-Computation       Finite-Automata       Gate 2012
Question 62 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 63
A
1, 2, 3, 4
B
1, 2
C
2, 3, 4
D
3, 4
       Theory-of-Computation       Decidability-and-Undecidability       Gate 2012
Question 63 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 64
   
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 64 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 65
   
A
B
C
D
       Theory-of-Computation       Finite-Automata       Gate 2012
Question 65 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 66
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 66 Explanation: 
Exp: Σ* - P is the complement of P so it is always regular,
since regular languages are closed under complementation
Question 67
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 67 Explanation: 
NPDA is more powerful than DPDA.
Hence answer is (B)
Question 68
A
k+1
B
n+1
C
2n+1
D
2k+1
       Theory-of-Computation       Finite-Automata       Gate 2011
Question 68 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 69
 
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 69 Explanation: 
L1: regular language
L2: context free language
L3: context sensitive language
Question 70
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       2010
Question 70 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 71
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       2010
Question 71 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 72
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       2010
Question 72 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 73
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       2010
Question 73 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 74
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       2009
Question 74 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 75
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       2009
Question 75 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 76
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       2009
Question 76 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 77
A
3
B
4
C
5
D
6
       Theory-of-Computation       Finite-Automata       2009
Question 77 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 78
 
A
Not recursive
B
Regular
C
Context free but not regular
D
Recursively enumerable but not context free
       Theory-of-Computation       Identify-Class-Language       2009
Question 78 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 79
 
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       2009
Question 79 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 80
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 80 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 81
     
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 81 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 82
A
regular
B
context-free
C
context-sensitive
D
recursive
       Theory-of-Computation       Recursive-Enumerable-Languages       Gate-2008
Question 82 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 83
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 83 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 84
 
A
B
C
D
       Theory-of-Computation       Finite-Automata       Gate-2008
Question 84 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}, wheresP 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 85

 
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 85 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 86
 
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 86 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 87
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 87 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 88
 
A
I and IV only
B
I and III only
C
I only
D
IV only
       Theory-of-Computation       Regular Languages       Gate-2008
Question 88 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 89
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 89 Explanation: 
Set of states of NFA = n
A state in a DFA is a proper suset of states of NFA of corresponding DFA.
→ No. of subsets with n elements = 2n
→ m ≤ 2n
Question 90
 
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 90 Explanation: 

Option B: abab is not accepted by given RE.
Option C: aba is accepted by given RE.
Option D: ab is not accepetd by RE and it belongs to b*aa*(ba)*b*.
Question 91
 
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 91 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 92
 
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 92 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 93
 
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 93 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 94
 
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 94 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 95
   
A
aabbaba
B
aabaaba
C
abababb
D
aabbaab
       Theory-of-Computation       Contest-Free-Grammar       Gate 2008-IT
Question 95 Explanation: 
S→aS
S→aA
S→aaAb
S→aabAab
S→aabbAaab
S→aabbaab
Question 96
 
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 96 Explanation: 
S→aS
S→aA
S→aaAb
S→aabAab
S→aabbAaab
S→aabbaab
⇒ 6 steps are required

Only 1 parse tree is there.
Question 97
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 97 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 98
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 98 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 99
 
A
15 states
B
11 states
C
10 states
D
9 states
       Theory-of-Computation       Finite-Automata       Gate-2007
Question 99 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 100
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 100 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 101
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 101 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 102
 
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 102 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 103
 
A
1
B
2
C
3
D
4
       Theory-of-Computation       Finite-Automata       Gate-2007
Question 103 Explanation: 
The minimum state automaton for problem 74 is:
Question 104
 
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 104 Explanation: 
Just simulate the running of the DFA on all options - A, B and C are false and D is true.
Question 105
 
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 105 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 106
 
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 106 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 107
   
A
B
C
D
       Theory-of-Computation       Finite-Automata       Gate 2007-IT
Question 107 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 108
 
A
B
C
D
       Theory-of-Computation       Regular-Expressions       Gate 2007-IT
Question 108 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 109
 
A
B
C
D
       Theory-of-Computation       Regular-Expressions       Gate 2007-IT
Question 109 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 110
   
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 110 Explanation: 
R = (a+b)* (aa+bb) (a+b)*
Having NFA:

Equivalent DFA:
Question 111
 
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 111 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 112
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 112 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
State1: n0(s') - n1(s') = 0
State2: n0(s') - n1(s') = 1
State3: n0(s') - n1(s') = 2
State4: n0(s') - n1(s') = -1
State5: n0(s') - n1(s') = -2
State6: Dead state (trap state)
Hence it is regular.
Option D: Product automata concept is used to construct the DFA.
mod 7 has remainders {0,1,2,3,4,5,6} and mod 5 remainders {0,1,2,3,4}
So product automata will have 35 states.
But option C has infinite comparisons between number of 0’s and 1’s.
For ex: 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 113
   
A
L1 only
B
L3 only
C
L1 and L2
D
L2 and L3
       Theory-of-Computation       Context-Free-Language       Gate-2006
Question 113 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 114
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 114 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 115
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 115 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 116
Consider the regular language L = (111 + 11111)*. The minimum number of states in any DFA accepting this language is:
A
3
B
5
C
8
D
9
       Theory-of-Computation       Finite-Automata       Gate-2006
Question 116 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 117
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 117 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 118
 
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 118 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 119
 
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 119 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 120
 
A
aaaa
B
baba
C
abba
D
babaaabab
       Theory-of-Computation       Contest-Free-Grammar       Gate 2006-IT
Question 120 Explanation: 
S → aSa | bSb | a | b | ϵ
Given string accepts all palindromes.
Option B → baba is not palindrome.
So, this is not accpeted by S.
Question 121
 
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 121 Explanation: 
Question 122
 
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 122 Explanation: 

⇒ This results even number, no. of a's.
Question 123
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 123 Explanation: 
Regular languages are not closed under subset.
Question 124
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 124 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 125
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 125 Explanation: 
CFL is closed under regular intersection.
Question 126
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 126 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 127
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 127 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 128
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 128 Explanation: 

From the table:
S' = S'y' + Sx
Question 129
   
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 129 Explanation: 
Repeat(L) = {ww|w ∈ L} is non-regular language.
Half (L), Suffix (L) and Prefix (L) are regular languages.
Question 130
 
A
(a + b)*
B
{ϵ, a, ab, bab}
C
(ab)*
D
{anbn | n ≥ 0}
       Theory-of-Computation       Regular-Language       Gate 2006-IT
Question 130 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 131
 
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 131 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 132
 
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 132 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 133
   
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 133 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 134
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 134 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 135

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 135 Explanation: 
NFA and DFA have equivalent powers.
So Df = Nf
NPDA can accept more languages than DPDA.
Dp ⊂ Np
Question 136
 
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 136 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 137
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 137 Explanation: 
Option A: If P1 is reducible tido 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 138
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 138 Explanation: 
Context-free languages not closed under complementation. So, Lc ∪ Mc is neither regular nor context-free. It might be context sensitive language.
Question 139
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 139 Explanation: 
The given expression01*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 140
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 140 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 141
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 141 Explanation: 
Question 142

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 142 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 143

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 143 Explanation: 
Since, it is NPDA, so we might not have any transitions over any alphabet. So option (D) is correct.
Question 144

A
2
B
3
C
4
D
5
       Theory-of-Computation       DFA       Gate 2005-IT
Question 144 Explanation: 
L = {aa, aaa, aaaaa, ...}
The minimum string length is 2 [aa], so we require 3 states to construct DFA.
Question 145
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 145 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 146
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 146 Explanation: 
Let's draw more than one possible tree for id + id + id + id.
Question 147
   
A
5
B
4
C
3
D
2
       Theory-of-Computation       CFG       Gate 2005-IT
Question 147 Explanation: 
Total 5 parse trees possible (solved in previous question).
Question 148
 
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 148 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 149
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 149 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 150
 
A
B
C
D
       Theory-of-Computation       Graphs       Gate 2005-IT
Question 150 Explanation: 



Question 151
A
>100 but finite
B
C
3
D
>3 and ≤100
       Theory-of-Computation       Graphs       Gate 2005-IT
Question 151 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 152
 
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 152 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 153
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 153 Explanation: 
Let us construct a PDA for the language
PUSH z0 into stack
PUSH K to stack of occurance of a
PUSH L to stack of occurance of b
POP K and L for the occurance of c
→ After POPno elements in the stack. So, this is context free language.
Note:
Regular:
R = {an | n ≥ 1}, Example.
CFL:
R = {anbm | n,m ≥ 1}, Example.
Question 154
     
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 154 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 155
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 155 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 156
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 156 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 157
   
A
aaa
B
aabab
C
baaba
D
bab
       Theory-of-Computation       Push-Down-Automata       Gate 2004-IT
Question 157 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 accpeted.
Thus in our question, option (B) is aabab having 'b' in the middle and thus can't be accepted.
Question 158
   
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 159
   
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 159 Explanation: 
Here, we have two possibilities, whether
P = NP (or) P != NP
→ If P=NP then L=(0+1)* which is recular, then it is recursive.
→ If P!=NP then L becomes ɸ which is also regular, then it is recursive.
So, finally L is recursive.
Question 160
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 160 Explanation: 
Both (A) and the given expression generates all strings over Σ.
Option (B) and (C) doesn't generate 11.
Question 161
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 161 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 lexicograhic order which is not accepted by TM.
The give 'L' is recursive but not necessarily context free.
Question 162
   
A
1
B
5
C
7
D
8
       Theory-of-Computation       Finite-Automata       Gate-2003
Question 162 Explanation: 

There are possible: 7 strings
Question 163
   
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 163 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 164
 
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 164 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 165
 
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 165 Explanation: 

Try for any string, it will not Halt for any string other than ϵ. Hence, option (A) is correct.
Question 166
   
A
B
C
D
       Theory-of-Computation       Turing Machine       Gate-2003
Question 167
 
A
L1 = {0,1}* - L
B
L1 = {0,1}*
C
L1 ⊆ L
D
L1 = L
       Theory-of-Computation       Finite-Automata       Gate-2003
Question 167 Explanation: 
As in the question said,

As in above NFA language,
L1 is {0,1}*.
Question 168
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 168 Explanation: 
Push down automata accept context free grammars but here the value of stack is limited 10 then it accepts regular languages.
Question 169
 
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 169 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 170
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 170 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 171
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 171 Explanation: 
Recursive languages are closed under complementation.
Question 172
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 172 Explanation: 
C and C++ are context sensitive languages.
Question 173
A
Theory Explanation is given below.
       Theory-of-Computation       Turing Machine       Gate-2002
Question 174
A
Theory Explanation is given below.
       Theory-of-Computation       Finite-Automata       Gate-2002
Question 175
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 175 Explanation: 
If we draw DFA for language S and T it will represent same.
Question 176
 
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 176 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 177
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 177 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 178
 
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 178 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 179
 
A
Theory Explanation is given below.
       Theory-of-Computation       Descriptive       Gate-2000
Question 179 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 180
 
A
Theory Explanation is given below.
       Theory-of-Computation       Descriptive       Gate-2000
Question 180 Explanation: 
(a)

(b)
Question 181
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 181 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 182
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 182 Explanation: 
Context free languages are not closed under Intersection and complementation.
By checking the options only option B is correct.
Question 183
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 183 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 184
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 184 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 185
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 185 Explanation: 
If a grammar is both left and right recursion, then grammar may or may not be ambiguous.
Question 186
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 186 Explanation: 
Both A and B are equal, which generates strings over {0,1}, while 0 is followed by 1.
Question 187
Which of the following set can be recognized by a Deterministic Finite state Automaton?  
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 187 Explanation: 
The numbers are to be like
10, 100, 1000, 10000 .... = 10*
which is reguar and recognized by deterministic finite automata.
Question 188
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 188 Explanation: 
B: No conversion possible from NPDA to DPDA.
C: Power (TM) > NPDA > DPDA.
Question 189
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 189 Explanation: 
Options A & B are generates string 1101.
C & D are not generate string 1101.
Question 190
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 190 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 191

Let L be the set of all binary strings whose last two symbols are the same. The number of states in the minimum state deterministic finite 0 state automaton accepting L is

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

Equivalent DFA:

Hence, 5 states.
Question 192
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 192 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 193
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 193 Explanation: 
Uncountable: Set of all languages over Σ is uncountable.
Question 194
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 194 Explanation: 
(A) generates 100.
(B) generates 100 as substring.
(C) doesn't generate 1.
(D) answer.
Question 195
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 195 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 196
 
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 196 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 197
 
A
(i) and (ii)
B
(ii) and (iii)
C
(i) and (iii)
D
(iii) and (iv)
       Theory-of-Computation       Regular-Expressions       Gate-1996
Question 197 Explanation: 
(00)*(ε+0),0*
In these two, we have any no. of 0's as well as null.
Question 198
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 198 Explanation: 
Equivalenceof 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 199
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 199 Explanation: 
L = {ambn|m ≥ 1, n ≥ 1}
Here, m and n are independent.
So 'L' Is Regular.
Question 200
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 200 Explanation: 
Context free languages are not closed under intersection.
Question 201
 
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 201 Explanation: 
(B) is the answer. Because for any binarystring 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 202
   
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 202 Explanation: 
We have to generate
"if a then if b then c:=d else c:=f".
Parse tree 1:

Parse tree 2:
Question 203
 
A
4
B
3
C
2
D
1
       Theory-of-Computation       Finite-Automata       Gate-1996
Question 203 Explanation: 
3 states are required in the minimized machine states B and C can be combined as follows:
Question 204
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 204 Explanation: 
Which is to be letter followed by any number of letters (or) digits
L(L⋅D)*
Question 205
     
A
Context free
B
Regular
C
Context sensitive
D
LR(k)
       Theory-of-Computation       General       Gate-1995
Question 205 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 206
 
A
I only
B
I and II
C
II and III
D
II only
       Theory-of-Computation       Regular Languages       Gate-1995
Question 206 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 207
   
A
01
B
10
C
101
D
110
       Theory-of-Computation       Finite-State-Machine       Gate-1995
Question 207 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 208
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 208 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 209
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 209 Explanation: 
NPDA to DPDA conversion is not possible. They have different powers.
Question 210
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 210 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 211
 
A
L=0*1*
       Theory-of-Computation       Finite-Automata       Gate-1994
Question 211 Explanation: 
L = 0*1*
L contains all binary strings where a 1 is not followed by a 0.
Question 212
 
A
True
B
False
       Theory-of-Computation       Undecidability       Gate-1994
Question 212 Explanation: 
Because if a set itself is countable then the subset of set is definitely countable.
Question 213
 
A
B
C
D
E
       Theory-of-Computation       Finite-Automata       Gate-1993
Question 214
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 214 Explanation: 
Note: Out of syllabus.
Question 215
 
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 215 Explanation: 
LFOLLOW may be different but RFOLLOW and FOLLOW will be same.
Question 216
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 216 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 217
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 217 Explanation: 
For CNF, it is
2l - 1
For GNF, it is
l
Question 218
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 218 Explanation: 
CFL's are not closed under intersection and complementation.
Question 219

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 219 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 220
 
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 220 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 221
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 221 Explanation: 
Context free languages closed under Union, concatenation and kleen star. But not close under intersection and complementation.
Question 222
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 222 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 223
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 223 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 224
   
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 224 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 225
 
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 225 Explanation: 
The given X is a Halting problem. So which is to be undecidable but partially decidable.
Question 226
 
A
Theory Explanation is given below.
       Theory-of-Computation       Finite-Automata       Gate-2001
Question 227
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 228
 
A
Theory Explanation is given below.
       Theory-of-Computation       Turing Machine       Gate-2001
Question 229
   
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 229 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 230
 
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 230 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 231
 
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 231 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 232
 
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 232 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 behaviour of TM unknown hence, undecidable.
Question 233
 
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 233 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 234
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 234 Explanation: 
Regular languages closed under Union, Intersection, Concatenation and Complementation but CFC is only closed under Union and Concatenation.
Question 235
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 235 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 236
Regularity is preserved under the operation of string reversal.
A
True
B
False
       Theory-of-Computation       Regular-Language       GATE-1987
Question 236 Explanation: 
Regular language is closed under reversal.
Question 237
All subsets of regular sets are regular.
A
True
B
False
       Theory-of-Computation       Regular-Language       GATE-1987
Question 237 Explanation: 
a*b* is regular but its subset anbn is not regular.
Question 238
A minimal DFA that is equiavlent to an NDFA with n nodes has always 2n states.
A
True
B
False
       Theory-of-Computation       Finite-Automata       GATE-1987
Question 238 Explanation: 
A minimal DFA is equivalent to a NDFA with n nodes has atmost 2n states and does not have always 2n states.
Question 239
The intersection of two CFL's is also a CFL.
A
True
B
False
       Theory-of-Computation       Context-Free-Language       GATE-1987
Question 239 Explanation: 
Context free language is not closed under intersection.
Question 240
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 240 Explanation: 
If A is decidable, then A and A' are accepted by Turing machine.
Question 241
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 241 Explanation: 
An ambiguous grammar produces more than one parse tree for some string.
Question 242
FORTRAN is a:
A
Regular language.
B
Context-free language.
C
Context-senstive language.
D
None of the above.
       Theory-of-Computation       Identify-Class-Language       GATE-1987
Question 242 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.
There are 242 questions to complete.