## 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
Consider the language and the following statements.
1. L is deterministic context-free.
2. L is context-free but not deterministic context-free.
3. L is not LL(k) for any k.
Which of the above statements is/are TRUE?
 A 2 only B 3 only C 1 only D 1 and 3 only
Theory-of-Computation       Languages-and-Grammars       GATE 2020
Question 5 Explanation:
L is DCFL.
We can make DPDA for this.

L is not LL(k) for any “k” look aheads. The reason is the language is a union of two languages which have common prefixes. For example strings {aa, aabb, aaa, aaabbb,….} present in language. Hence the LL(k) parser cannot parse it by using any lookahead “k” symbols.
 Question 6
Consider the following statements.
I.If L1 U L2is regular, then both L1 and L2 must be regular.
II.The class of regular languages is closed under infinite union.
Which of the above statements is/are TRUE?
 A Both I and II B II only C Neither I nor II D I only
Theory-of-Computation       Regular-Language       GATE 2020
Question 6 Explanation:
Statement I is wrong. Assume L1= {an bn | n>0} and L2= complement of L1
L1 and L2 both are DCFL but not regular, but L1 U L2 = (a+b)* which is regular.
Hence even though L1 U L2 is regular , L1 and L2 need not be always regular.
Statement II is wrong.
Assume the following finite (hence regular) languages.
L1= {ab}
L2={aabb}
L3={aaabbb}
.
.
.
.
L100={a^100 b^100}
.
If we take infinite union of all above languages i.e,
{L1 U L2 U ……….L100 U ……} then we will get a new language L={a^n b^n | n>0}, which is not regular. Hence regular languages are not closed under infinite UNION.
 Question 7
Which one of the following regular expressions represents the set of all binary strings with an odd number of 1’s?
 A 10*(0*10*10*)* B ((0 + 1)*1(0 + 1)*1)*10* C (0*10*10*)*10* D (0*10*10*)*0*1
Theory-of-Computation       Regular-Expression       GATE 2020
Question 7 Explanation:
The regular expression 10*(0*10*10*)* always generate string begin with 1 and thus  does not generate string “01110” hence wrong option.
The regular expression ((0+1)*1(0+1)*1)*10*  generate string “11110” which is not having odd number of 1’s , hence wrong option.
The regular expression (0*10*10*)10* is not a generating string “01”. Hence this is also wrong . It seems none of them is correct.
NOTE: Option 3 is most appropriate option as it generate the max number of strings with odd 1’s.
But option 3 is not generating odd strings. So, still it is not completely correct.
The regular expression (0*10*10*)*0*1  always generates all string ends with “1” and thus does not generate string “01110” hence wrong option.
 Question 8
Which of the following languages are undecidable? Note that indicates encoding of the Turing machine M.

 A L2 and L3 only B L1 and L3 only C L2, L3 and L4 only D L1, L3 and L4 only
Theory-of-Computation       Decidability-and-Undecidability       GATE 2020
Question 8 Explanation:
L1 is undecidable as emptiness problem of Turing machine is undecidable. L3 is undecidable since there is no algorithm to check whether a given TM accept recursive language. L4 is undecidable as it is similar to membership problem.
Only L3 is decidable. We can check whether a given TM reach state q in exactly 100 steps or not. Here we have to check only upto 100 steps, so here is not any case of going to infinite loop.
 Question 9
Consider the following language.
L = {x ∈ {a,b}* | number of a’s in x is divisible by 2 but not divisible by 3}
The minimum number of states in a DFA that accepts L is ______.
 A 6
Theory-of-Computation       Finite-Automata       GATE 2020
Question 9 Explanation:

 Question 10
Consider the following languages.
L1 = {wxyx | w,x,y ∈ (0 + 1)+}
L2 = {xy | x,y ∈ (a + b)*, |x| = |y|, x ≠ y}
Which one of the following is TRUE?
 A L1 is context-free but not regular and L2 is context-free. B Neither L1 nor L2 is context-free. C L1 is regular and L2 is context-free. D L1 is context-free but L2 is not context-free.
Theory-of-Computation       Languages-and-Grammars       GATE 2020
Question 10 Explanation:
L1 is regular. y can be expanded and w can also expanded. So x can be either "a" or "b"
So it is equivalent to
(a+b)+ a (a+b)+ a  + (a+b)+ b (a+b)+ b
L2 is CFL since it is equivalent to complement of L=ww. Complement of
L=ww is CFL.
 Question 11

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 11 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 12
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 12 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 13
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 13 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 14

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

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 15 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 16

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 16 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 17

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 17 Explanation:
The NFA for regular expression: (a+b)*b(a+b)

After converting the NFA into DFA:

After converting the NFA into DFA:
 Question 18

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 18 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 19

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 19 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 20

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 20 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 21

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 21 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 22

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 22 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 23

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 23 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 24

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 24 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 25

 A ∅ B {q0,q1,q3} C {q0,q1,q2} D {q0,q2,q3}
Theory-of-Computation       NFA       GATE 2017(set-02)
Question 25 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 q3 but from q3, 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 26

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 26 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 27

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

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 28 Explanation:
From the given grammar we can draw the DFA,
 Question 29

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

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

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

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 ﬁnite 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 32 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 33
 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 33 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 34

The number of states in the minimum sized DFA that accepts the language deﬁned 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 34 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 35

Language L1 is deﬁned by the grammar: S1 → aS1b|ε
Language L2 is deﬁned 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 35 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 36

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 36 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.
 Question 37

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 37 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 38

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 38 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 39

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 speciﬁc 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 39 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 40

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

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 41 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 42
Consider the DFAs M and N given above. The number of states in a minimal DFA that accepts the language L(M) ∩ L(N) is __________.
 A 1 B 2 C 3 D 4
Theory-of-Computation       DFA       GATE 2015 (Set-01)
Question 42 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 43
Consider the NPDA 〈Q = {q0, q1, q2}, Σ = {0, 1}, Γ = {0, 1, ⊥}, δ, q0, ⊥, F = {q2}〉, where (as per usual convention) Q is the set of states, Σ is the input alphabet, Γ is stack alphabet, δ is the state transition function, q0 is the initial state, ⊥ is the initial stack symbol, and F is the set of accepting states, The state transition is as follows: Which one of the following sequences must follow the string 101100 so that the overall string is accepted by the automaton?
 A 10110 B 10010 C 01010 D 01001
Theory-of-Computation       PDA       GATE 2015 (Set-01)
Question 43 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 44
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 44 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 45
Consider the follwoing statements.
 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 45 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 46
Which of the following language is/are regular ?
 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 46 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 47
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 47 Explanation:

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

From the given diagram we can write,
X0 = 1(0+10)* 1
 Question 49

 A 4 B 5 C 6 D 8
Theory-of-Computation       Regular-Expressions       GATE 2015(Set-03)
Question 49 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 50
Language L1 is polynomial time reducible to language L2. Language L3 is polynomial time reducible to L2, which in turn is polynomial time reducible to language L4. Which of the following is/are True?
```I. If L4 ∈ P, L2 ∈ P
II. If L1 ∈ P or L3 ∈ P, then L2 ∈ P
III. L1 ∈ P, if and only if L3 ∈ P
IV. If L4 ∈ P, then L1 ∈ P and L3 ∈ P```
 A II only B III only C I and IV only D I only
Theory-of-Computation       Reducibility       GATE 2015(Set-03)
Question 50 Explanation:
L2 ≤ pL4
L1 ≤ pL2
If L4 ∈ P then L2 ∈ P hence L1 ∈ P, hence option C.
 Question 51
Which of the following languages are context-free?
```L1 = {ambnanbm ⎪ m, n ≥ 1}
L2 = {ambnambn ⎪ m, n ≥ 1}
L3 = {ambn ⎪ m = 2n + 1}```

 A L1 and L2 only B L1 and L3 only C L2 and L3 only D L3 only
Theory-of-Computation       Context-Free-Language       GATE 2015(Set-03)
Question 51 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 52
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 52 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 53
Consider the finite automaton in the following figure. What is the set of reachable states fot the input string 0011?
 A {q0,q1,q2 } B {q0,q1 } C {q0,q1,q2,q3 } D {q3 }
Theory-of-Computation       Finite-Automata       GATE 2014(Set-01)
Question 53 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 54

 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 54 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 complementation, so there concatenation (i.e. L1. L2) must also be a regular language.
But,
L1.L2 ≠ { anbn | n ≥ 0}
L1= {ϵ, a ,aa, aaa, aaaa,.............}
L2={ϵ, b, bb, bbb, bbbb, …………}
So L1.L2 = {ϵ, a ,aa, aaa, aaaa,.............}.{ϵ, b, bb, bbb, bbbb, …………}
L1.L2= {ϵ, a, aa, aaa, …………., b, bb, bbb, ……., ab, abb, abbb, …….., aab, aaab, …………..}
Hence L1.L2= { ambn | m, n ≥ 0}
 Question 55
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 55 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 56
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 56 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 57
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 57 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 58
The length of the shortest string NOT in the language (over Σ = {a b,} of the following regular is expression is ______________. a*b*(ba)*a*
 A 3 B 4 C 5 D 6
Theory-of-Computation       Regular Languages and Finite Automata       Gate 2014 Set -03
Question 58 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 59
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 59 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 60
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 60 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 61
Consider the decision problem 2CNFSAT defined as follows: The decision problem 2CNFSAT is
 A NP-Complete. B solvable in polynomial time by reduction to directed graph reachability. C solvable in constant time since any input instance is satisfiable. D NP-hard, but not NP-complete.
Theory-of-Computation       NP-Complete       Gate 2014 Set -03
Question 61 Explanation:
Note: Out of Syllabus.
 Question 62
Consider the following languages over the alphabet Σ = {0,1, c}: Here, wris the reverse of the string . Which of these languages are deterministic Context-free languages?
 A None of the languages B Only L1 C Only L1 and L2 D All the three languages
Theory-of-Computation       Context-Free-and-pushdown-Automata       Gate 2014 Set -03
Question 62 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 63

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 63 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 64
Which of the following statements is/are FALSE?
```1. For every non-deterministic Turing machine,
there exists an equivalent deterministic Turing machine.
2. Turing recognizable languages are closed under union
and complementation.
3. Turing decidable languages are closed under intersection
and complementation.
4. Turing recognizable languages are closed under union
and intersection.```
 A 1 and 4 only B 1 and 3 only C 2 only D 3 only
Theory-of-Computation       REL&Turing-Machines       Gate 2013
Question 64 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 65
Which of the following statements are TRUE?
```1. The problem of determining whether there exists
a cycle in an undirected graph is in P.
2. The problem of determining whether there exists
a cycle in an undirected graph is in NP.
3. If a problem A is NP-Complete, there exists a
non-deterministic polynomial time algorithm to solve A.```
 A 1, 2 and 3 B 1 and 2 only C 2 and 3 only D 1 and 3 only
Theory-of-Computation       NP-Complete       Gate 2013
Question 65 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 66
Consider the DFA given. Which of the following are FALSE?
```1. Complement of L(A) is context-free.
2. L(A) = L((11*0+0)(0 + 1)*0*1*)
3. For the language accepted by A, A is the minimal DFA.
4. A accepts all strings over {0, 1} of length at least 2.```
 A 1 and 3 only B 2 and 4 only C 2 and 3 only D 3 and 4 only
Theory-of-Computation       Regular Languages and Finite Automata       Gate 2013
Question 66 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 67
Which of the following is/are undecidable?
 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 67 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 68
What is the complement of the language accepted by the NFA shown below?
 A ∅ B {ε} C a* D {a ,ε}
Theory-of-Computation       Finite-Automata       Gate 2012
Question 68 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 69
`Which of the following problems are decidable?`
 A 1, 2, 3, 4 B 1, 2 C 2, 3, 4 D 3, 4
Theory-of-Computation       Decidability-and-Undecidability       Gate 2012
Question 69 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 70
Given the language L ={ab,aa,baa}, which of the following strings are in L *? 1)abaabaaabaa 2)aaaabaaaa 3)baaaaabaaaab 4)baaaaabaa
 A 1, 2 and 3 B 2, 3 and 4 C 1, 2 and 4 D 1, 3 and 4
Theory-of-Computation       Regular Languages       Gate 2012
Question 70 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 71
Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two zeros. For example, 001110 and 011001 are in the language, but 100010 is not. All strings of length less than 3 are also in the language. A partially completed DFA that accepts this language is shown below. The missing arcs in the DFA are
 A B C D
Theory-of-Computation       Finite-Automata       Gate 2012
Question 71 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 72
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 72 Explanation:
Exp: Σ* - P is the complement of P so it is always regular,
since regular languages are closed under complementation
 Question 73
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 73 Explanation:
NPDA is more powerful than DPDA.
 Question 74
Definition of a language L with alphabet {a} is given as foloowing. What is the minimum number of states needed in a DFA to recognize L?
 A k+1 B n+1 C 2n+1 D 2k+1
Theory-of-Computation       Finite-Automata       Gate 2011
Question 74 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 75
Consider the languages L1,L2 and L3 as given below. Which of the following statements is NOT TRUE?
 A Push Down Automate (PDA) can be used to recognize L1 and L2 B L1 is a regular language C All the three languages are context free D Turing machines can be used to recognize all the languages
Theory-of-Computation       Identify-Class-Language       Gate 2011
Question 75 Explanation:
L1: regular language
L2: context free language
L3: context sensitive language
 Question 76
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 76 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 77
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 77 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 78
Consider the languages L1 = {0i1j | i != j}. L2 = {0i1j | i = j}. L3 = {0i1j | i = 2j+1}. L4 = {0i1j | i != 2j}. Which one of the following statements is true?
 A Only L2 is context free B Only L2 and L3 are context free C Only L1 and L2 are context free D All are context free
Theory-of-Computation       Context-Free-Language       2010
Question 78 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 79
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 79 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 80
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 80 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 81
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 81 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 82
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 82 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 83
Given the following state table of an FSM with two states A and B, one input and one output: If the initial state is A = 0, B=0, what is the minimum length of an input string which will take the machine to the state A=0, B=1 with Output=1?
 A 3 B 4 C 5 D 6
Theory-of-Computation       Finite-Automata       2009
Question 83 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 84

 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 84 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 85
The above DFA accepts the set of all strings over {0,1} that
 A begin either with 0 or 1 B end with 0 C end with 00 D contain the substring 00
Theory-of-Computation       Finite-Automata       2009
Question 85 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 86
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 86 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 87
Which of the following are decidable? I.Whether the intersection of two regular languages is infinite II.Whether a given context-free language is regular III.Whether two push-down automata accept the same language IV.Whether a given grammar is context-free
 A I and II B I and IV C II and III D II and IV
Theory-of-Computation       Decidability-and-Undecidability       Gate-2008
Question 87 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 88
 A regular B context-free C context-sensitive D recursive
Theory-of-Computation       Recursive-Enumerable-Languages       Gate-2008
Question 88 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 89
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 89 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 90
Given below are two finite state automata (® indicates the start state and F indicates a final state) Which of the following represents the product automaton Z×Y?
 A B C D
Theory-of-Computation       Finite-Automata       Gate-2008
Question 90 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 91

Which of the following statements are true? I.Every left-recursive grammar can be converted to a right-recursive grammar and vice-versa II.All e-productions can be removed from any context-free grammar by suitable transformations III.The language generated by a context-free grammar all of whose productions are of the form X ® w or X ® wY a non-terminal), is always regular (where, w is a string of  erminals and Y is IV.The derivation trees of strings generated by a context-free grammar in Chomsky Normal Form are always binary trees
 A I, II, III and IV B II, III and IV only C I, III and IV only D I, II and IV only
Theory-of-Computation       Contest-Free-Grammar       Gate-2008
Question 91 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 92
Match the following:
 A E - P, F - R, G - Q, H - S B E - R, F - P, G - S, H - Q C E - R, F - P, G - Q, H - S D E - P, F - R, G - S, H - Q
Theory-of-Computation       Match-the-Following       Gate-2008
Question 92 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 93
Match the following NFAs with the regular expressions they correspond to .      1.e + 0 (01 * 1 + 00) * 01 *
1. e+ 0 (10 * 1 + 00) * 0
2. e+ 0 (10 * 1 + 10) * 1
3. e+ 0 (10 * 1 + 10) * 10 *
 A P-2, Q-1, R-3, S-4 B P-1, Q-3, R-2, S-4 C P-1, Q-2, R-3, S-4 D P-3, Q-2, R-1, S-4
Theory-of-Computation       Finite-Automata       Gate-2008
Question 93 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 94
Which of the following are regular sets?

 A I and IV only B I and III only C I only D IV only
Theory-of-Computation       Regular Languages       Gate-2008
Question 94 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 95
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 95 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 96
If the final states and non-final states in the DFA below are interchanged, then which of the following languages over the alphabet {a,b} will be accepted by the new DFA?
 A Set of all strings that do not end with ab B Set of all strings that begin with either an a or a b C Set of all strings that do not contain the substring ab D The set described by the regular expression b*aa*(ba)*b*
Theory-of-Computation       Finite-Automata       Gate 2008-IT
Question 96 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 97
Consider the following languages. L1 = {ai bj ck | i = j, k ≥ 1} L1 = {ai bj | j = 2i, i ≥ 0} Which of the following is true?
 A L1 is not a CFL but L2 is B L1 ∩ L2 = ∅ and L1 is non-regular C L1 ∪ L2 is not a CFL but L2 is D There is a 4-state PDA that accepts L1, but there is no DPDA that accepts L2
Theory-of-Computation       Identify-Class-Language       Gate 2008-IT
Question 97 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 98
Consider a CFG with the following productions. S → AA | B A → 0A | A0 | 1 B → 0B00 | 1 S is the start symbol, A and B are non-terminals and 0 and 1 are the terminals. The language generated by this grammar is
 A {0n 102n | n ≥ 1} B {0i 10j 10k | i, j, k ≥ 0} ∪ {0n 102n | n ≥ l} C {0i 10j | i, j ≥ 0} ∪ {0n 102n | n ≥ l} D The set of all strings over {0, 1} containing at least two 0’s E None of the above
Theory-of-Computation       Contest-Free-Grammar       Gate 2008-IT
Question 98 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 99
Which of the following languages is (are) non-regular? L1 = {0m1n | 0 ≤ m ≤ n ≤ 10000} L2 = {w | w reads the same forward and backward} L3 = {w ∊ {0, 1} * | w contains an even number of 0's and an even number of 1's}
 A L2 and L3 only B L1 and L2 only C L3 only D L2 only
Theory-of-Computation       Identify-Class-Language       Gate 2008-IT
Question 99 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 100
Consider the following two finite automata. M1 accepts L1 and M2 accepts L2. Which one of the following is TRUE?
 A L1 = L2 B L1 ⊂ L2 C L1 ∩ L2‘ = ∅ D L1 ∪ L2 ≠ L1 E A and C
Theory-of-Computation       Finite-Automata       Gate 2008-IT
Question 100 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 101
A CFG G is given with the following productions where S is the start symbol, A is a non-terminal and a and b are terminals. S→aS∣A A→aAb∣bAa∣ϵ Which of the following strings is generated by the grammar above?
 A aabbaba B aabaaba C abababb D aabbaab
Theory-of-Computation       Contest-Free-Grammar       Gate 2008-IT
Question 101 Explanation:
S→aS
S→aA
S→aaAb
S→aabAab
S→aabbAaab
S→aabbaab
 Question 102
A CFG G is given with the following productions where S is the start symbol, A is a non-terminal and a and b are terminals. S→aS∣A A→aAb∣bAa∣ϵ For the correct answer in Q75, how many steps are required to derive the string and how many parse trees are there?
 A 6 and 1 B 6 and 2 C 7 and 2 D 4 and 2
Theory-of-Computation       Contest-Free-Grammar       Gate 2008-IT
Question 102 Explanation:
S→aS
S→aA
S→aaAb
S→aabAab
S→aabbAaab
S→aabbaab
⇒ 6 steps are required

Only 1 parse tree is there.
 Question 103
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 103 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 104
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 104 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 105
A minimum state deterministic finite automaton accepting the language L={w | w ε {0,1} *, number of 0s and 1s in w are divisible by 3 and 5, respectively} has
 A 15 states B 11 states C 10 states D 9 states
Theory-of-Computation       Finite-Automata       Gate-2007
Question 105 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 106
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 106 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 107
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 107 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 108

 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 108 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 109
Consider the following Finite State Automaton.

The language accepted by this automaton is given by the regular expression
 A 1 B 2 C 3 D 4
Theory-of-Computation       Finite-Automata       Gate-2007
Question 109 Explanation:
The minimum state automaton for problem 74 is:
 Question 110
Consider the following DFA in which s0 is the start state and s1, s3 are the final states. What language does this DFA recognize ?
 A All strings of x and y B All strings of x and y which have either even number of x and even number of y or odd number or x and odd number of y C All strings of x and y which have equal number of x and y D All strings of x and y with either even number of x and odd number of y or odd number of x and even number of y
Theory-of-Computation       Finite-Automata       Gate 2007-IT
Question 110 Explanation:
Just simulate the running of the DFA on all options - A, B and C are false and D is true.
 Question 111
Consider the grammar given below S → x B | y A A → x | x S | y A A B → y | y S | y B B Consider the following strings. (i) xxyyx (ii) xxyyxy (iii) xyxy (iv) yxxy (v) yxx (vi) xyx Which of the above strings are generated by the grammar ?
 A (i), (ii), and (iii) B (ii), (v), and (vi) C (ii), (iii), and (iv) D (i), (iii), and (iv)
Theory-of-Computation       Grammar       Gate 2007-IT
Question 111 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 112
Consider the following grammars. Names representing terminals have been specified in capital letters. Which one of the following statements is true?
 A G1 is context-free but not regular and G2 is regular B G2 is context-free but not regular and G1 is regular C Both G1 and G2 are regular D Both G1 and G2 are context-free but neither of them is regular
Theory-of-Computation       Identify-Class-Language       Gate 2007-IT
Question 112 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 113
Consider the following finite automata P and Q over the alphabet {a, b, c}. The start states are indicated by a double arrow and final states are indicated by a double circle. Let the languages recognized by them be denoted by L(P) and L(Q) respectively. The automation which recognizes the language L(P) ∩ L(Q) is :
 A B C D
Theory-of-Computation       Finite-Automata       Gate 2007-IT
Question 113 Explanation:
String 'aa' 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 114
Consider the regular expression R = (a + b)* (aa + bb) (a + b)* Which deterministic finite automaton accepts the language represented by the regular expression R ?
 A B C D
Theory-of-Computation       Regular-Expressions       Gate 2007-IT
Question 114 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 115
Consider the regular expression R = (a + b)* (aa + bb) (a + b)*
Which one of the regular expressions given below defines the same language as defined by the regular expression R?
 A B C D
Theory-of-Computation       Regular-Expressions       Gate 2007-IT
Question 115 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 116
For S ∈ (0 + 1) * let d(s) denote the decimal value of s (e.g. d(101) = 5). Let L = {s ∈ (0 + 1)* d(s)mod5 = 2 and d(s)mod7 != 4}. Which one of the following statements is true?
 A L is recursively enumerable, but not recursive B L is recursive, but not context-free C L is context-free, but not regular D L is regular
Theory-of-Computation       Identify-Class-Language       Gate-2006
Question 116 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 117
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 117 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
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 118

 A L1 only B L3 only C L1 and L2 D L2 and L3
Theory-of-Computation       Context-Free-Language       Gate-2006
Question 118 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 119
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 119 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 120
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 120 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 121
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 121 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 122
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 122 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 123
Consider the following statements about the context free grammar
```G = {S → SS, S → ab, S → ba, S → Ε}
I. G is ambiguous
II. G produces all strings with equal number of a’s and b’s
III. G can be accepted by a deterministic PDA.```
Which combination below expresses all the true statements about G?
 A I only B I and III only C II and III only D I, II and III
Theory-of-Computation       Contest-Free-Grammar       Gate-2006
Question 123 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 124
In the automaton below, s is the start state and t is the only final state. Consider the strings u = abbaba, v = bab, and w = aabb. Which of the following statements is true?
 A The automaton accepts u and v but not w B The automaton accepts each of u, v, and w C The automaton rejects each of u, v, and w D The automaton accepts u but rejects v and w
Theory-of-Computation       Finite-Automata       Gate 2006-IT
Question 124 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 125
In the context-free grammar below, S is the start symbol, a and b are terminals, and ϵ denotes the empty string S → aSa | bSb | a | b | ϵ Which of the following strings is NOT generated by the grammar?
 A aaaa B baba C abba D babaaabab
Theory-of-Computation       Contest-Free-Grammar       Gate 2006-IT
Question 125 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 126
Which regular expression best describes the language accepted by the non-deterministic automaton below?
 A (a + b)* a(a + b)b B (abb)* C (a + b)* a(a + b)* b(a + b)* D (a + b)*
Theory-of-Computation       Regular-Expressions       Gate 2006-IT
Question 126 Explanation:
 Question 127
Consider the regular grammar below S → bS | aA | ϵ A → aS | bA The Myhill-Nerode equivalence classes for the language generated by the grammar are
 A {w ∈ (a + b)* | #a(w) is even) and {w ∈ (a + b)* | #a(w) is odd} B {w ∈ (a + b)* | #a(w) is even) and {w ∈ (a + b)* | #b(w) is odd} C {w ∈ (a + b)* | #a(w) = #b(w) and {w ∈ (a + b)* | #a(w) ≠ #b(w)} D {ϵ}, {wa | w ∈ (a + b)* and {wb | w ∈ (a + b)*}
Theory-of-Computation       Regular-Grammar       Gate 2006-IT
Question 127 Explanation:

⇒ This results even number, no. of a's.
 Question 128
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 128 Explanation:
Regular languages are not closed under subset.
 Question 129
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 129 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 130
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 130 Explanation:
CFL is closed under regular intersection.
 Question 131
Consider the pushdown automaton (PDA) below which runs over the input alphabet (a, b, c). It has the stack alphabet {Z0, X} where Z0 is the bottom-of-stack marker. The set of states of the PDA is (s, t, u, f} where s is the start state and f is the final state. The PDA accepts by final state. The transitions of the PDA given below are depicted in a standard manner. For example, the transition (s, b, X) → (t, XZ0) means that if the PDA is in state s and the symbol on the top of the stack is X, then it can read b from the input and move to state t after popping the top of stack and pushing the symbols Z0 and X (in that order) on the stack. (s, a, Z0) → (s, XXZ0) (s, ϵ, Z0) → (f, ϵ) (s, a, X) → (s, XXX) (s, b, X) → (t, ϵ) (t, b, X) → (t,.ϵ) (t, c, X) → (u, ϵ) (u, c, X) → (u, ϵ) (u, ϵ, Z0) → (f, ϵ) The language accepted by the PDA is
 A {albmcn | l = m = n} B {albmcn | l = m} C {albmcn | 2l = m+n} D {albmcn | m=n}
Theory-of-Computation       Push-Down-Automata       Gate 2006-IT
Question 131 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 132
In the context-free grammar below, S is the start symbol, a and b are terminals, and ϵ denotes the empty string. S → aSAb | ϵ A → bA | ϵ The grammar generates the language
 A ((a + b)* b)* B {ambn | m ≤ n} C {ambn | m = n} D a* b*
Theory-of-Computation       Contest-Free-Grammar       Gate 2006-IT
Question 132 Explanation:
Option A generates string {aab, aaab, ........} which are not present in language hence this is wrong option.
Option C&D:
→ abb accepted by given grammar but option C & D are not accepting.
 Question 133
For a state machine with the following state diagram the expression for the next state S+ in terms of the current state S and the input variables x and y is
 A S+ = S’ . y’ + S . x B S+ =S. x . y’ + S’ . y . x’ C S+ =x . y’ D S+ =S’ . y + S . x’col
Theory-of-Computation       Finite-Automata       Gate 2006-IT
Question 133 Explanation:

From the table:
S' = S'y' + Sx
 Question 134
Let L be a regular language. Consider the constructions on L below: I. repeat (L) = {ww | w ∊ L} II. prefix (L) = {u | ∃v : uv ∊ L} III. suffix (L) = {v | ∃u : uv ∊ L} IV. half (L) = {u | ∃v : | v | = | u | and uv ∊ L} Which of the constructions could lead to a non-regular language?
 A Both I and IV B Only I C Only IV D Both II and III
Theory-of-Computation       Regular-Language       Gate 2006-IT
Question 134 Explanation:
Repeat(L) = {ww|w ∈ L} is non-regular language.
Half (L), Suffix (L) and Prefix (L) are regular languages.
 Question 135
Let L be a regular language. Consider the constructions on L below: repeat (L) = {ww | w ∊ L} prefix (L) = {u | ∃v : uv ∊ L} suffix (L) = {v | ∃u uv ∊ L} half (L) = {u | ∃v : | v | = | u | and uv ∊ L} Which of the constructions could lead to a non-regular language?
 A (a + b)* B {ϵ, a, ab, bab} C (ab)* D {anbn | n ≥ 0}
Theory-of-Computation       Regular-Language       Gate 2006-IT
Question 135 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 136
The following diagram represents a finite state machine which takes as input a binary number from the least significant bit. Which one of the following is TRUE?
 A It computes 1's complement of the input number B It computes 2's complement of the input number C It increments the input number D It decrements the input number
Theory-of-Computation       Finite-Automata       Gate-2005
Question 136 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 137
Consider the languages:
```L1 = {wwR |w ∈ {0, 1}*}
L2 = {w#wR | w ∈ {0, 1}*}, where # is a special symbol
L3 = {ww |  w ∈  (0, 1}*)```
Which one of the following is TRUE?
 A L1 is a deterministic CFL B L2 is a deterministic CFL C L3 is a CFL, but not a deterministic CFL D L3 is a deterministic CFL
Theory-of-Computation       Context-Free-Language       Gate-2005
Question 137 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 138
Consider the languages:
```L1 = {anbncm | n, m > 0}
L2 = {anbmcm | n, m > 0}```
Which one of the following statements is FALSE?
 A L1 ∩ L2 is a context-free language B L1 ∪ L2 is a context-free language C L1 and L2 are context-free languages D L1 ∩ L2 is a context sensitive language
Theory-of-Computation       Context-Free-Language       Gate-2005
Question 138 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 139
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 139 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 140

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 140 Explanation:
NFA and DFA have equivalent powers.
So Df = Nf
NPDA can accept more languages than DPDA.
Dp ⊂ Np
 Question 141
Consider the machine M: The language recognized by M is :
 A {w ∈ {a, b}* | every a in w is followed by exactly two b's} B {w ∈ {a, b}*| every a in w is followed by at least two b’} C {w ∈ {a, b}*| w contains the substring 'abb'} D {w ∈ {a, b}*| w does not contain 'aa' as a substring}
Theory-of-Computation       Finite-Automata       Gate-2005
Question 141 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 142
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 142 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 143
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 143 Explanation:
Context-free languages not closed under complementation. So, Lc ∪ Mc is neither regular nor context-free. It might be context sensitive language.
 Question 144
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 144 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 145
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 145 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 146
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 146 Explanation:
 Question 147

Consider the non-deterministic finite automaton (NFA) shown in the figure.

State X is the starting state of the automaton. Let the language accepted by the NFA with Y as the only accepting state be L1. Similarly, let the language accepted by the NFA with Z as the only accepting state be L2. Which of the following statements about L1 and L2 is TRUE? Correction in Question: There is an edge from Z->Y labeled 0 and another edge from Y->Z labeled 1 - in place of double arrowed and no arrowed edges.

 A L1 = L2 B L1 ⊂ L2 C L2 ⊂ L1 D None of the above
Theory-of-Computation       Regular Languages and Finite Automata       Gate 2005-IT
Question 147 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 148

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 148 Explanation:
Since, it is NPDA, so we might not have any transitions over any alphabet. So option (D) is correct.
 Question 149
Consider the regular grammar: S → Xa | Ya X → Za Z → Sa | ϵ Y → Wa W → Sa where S is the starting symbol, the set of terminals is {a} and the set of non-terminals is {S, W, X, Y, Z}. We wish to construct a deterministic finite automaton (DFA) to recognize the same language. What is the minimum number of states required for the DFA?
 A 2 B 3 C 4 D 5
Theory-of-Computation       DFA       Gate 2005-IT
Question 149 Explanation:
L = {aa, aaa, aaaaa, ...}
The minimum string length is 2 [aa], so we require 3 states to construct DFA.
 Question 150
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 150 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 151
Consider the context-free grammar E → E + E E → (E * E) E → id
where E is the starting symbol, the set of terminals is {id, (,+,),*}, and the set of nonterminals is {E}.
Which of the following terminal strings has more than one parse tree when parsed according to the above grammar?
 A id + id + id + id B id + (id* (id * id)) C (id* (id * id)) + id D ((id * id + id) * id)
Theory-of-Computation       Regular languages and finite automata       Gate 2005-IT
Question 151 Explanation:
Let's draw more than one possible tree for id + id + id + id.
 Question 152
Consider the context-free grammar E → E + E E → (E * E) E → id
where E is the starting symbol, the set of terminals is {id, (,+,),*}, and the set of non-terminals is {E}.
For the terminal string id + id + id + id, how many parse trees are possible?

 A 5 B 4 C 3 D 2
Theory-of-Computation       CFG       Gate 2005-IT
Question 152 Explanation:
Total 5 parse trees possible (solved in previous question).
 Question 153
A sink in a directed graph is a vertex i such that there is an edge from every vertex j ≠ i to i and there is no edge from i to any other vertex. A directed graph G with n vertices is represented by its adjacency matrix A, where A[i] [j] = 1 if there is an edge directed from vertex i to j and 0 otherwise. The following algorithm determines whether there is a sink in the graph G.
```i = 0
do {
j = i + 1;
while ((j < n) && E1)
j++;
if (j < n) E2;
} while (j < n);

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

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

 A E1 : A[i][j] and E2 : i = j; B E1 : !A[i][j] and E2 : i = j + 1; C E1: !A[i][j] and E2 : i = j; D E1 : A[i][j] and E2 : i = j + 1;
Theory-of-Computation       Graphs       Gate 2005-IT
Question 153 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.
 Question 154
A sink in a directed graph is a vertex i such that there is an edge from every vertex j ≠ i to i and there is no edge from i to any other vertex. A directed graph G with n vertices is represented by its adjacency matrix A, where A[i] [j] = 1 if there is an edge directed from vertex i to j and 0 otherwise. The following algorithm determines whether there is a sink in the graph G.
```i = 0
do {
j = i + 1;
while ((j < n) && E1) j++;
if (j < n) E2;
} while (j < n);

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

if (flag)
printf("Sink exists");
else
printf("Sink does not exist");
```
Choose the correct expressions for E3
 A (A[i][j] && !A[j][i]) B (!A[i][j] && A[j][i]) C (!A[i][j] | | A[j][i]) D (A[i][j] | | !A[j][i])
Theory-of-Computation       Graphs       Gate 2005-IT
Question 154 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 155
Consider a simple graph with unit edge costs. Each node in the graph represents a router. Each node maintains a routing table indicating the next hop router to be used to relay a packet to its destination and the cost of the path to the destination through that router. Initially, the routing table is empty. The routing table is synchronously updated as follows. In each updation interval, three tasks are performed.
1. A node determines whether its neighbours in the graph are accessible. If so, it sets the tentative cost to each accessible neighbour as 1. Otherwise, the cost is set to ∞.
2. From each accessible neighbour, it gets the costs to relay to other nodes via that neighbour (as the next hop).
3. Each node updates its routing table based on the information received in the previous two steps by choosing the minimum cost.
For the graph given above, possible routing tables for various nodes after they have stabilized, are shown in the following options. Identify the correct table.
 A B C D
Theory-of-Computation       Graphs       Gate 2005-IT
Question 155 Explanation:

 Question 156
Consider a simple graph with unit edge costs. Each node in the graph represents a router. Each node maintains a routing table indicating the next hop router to be used to relay a packet to its destination and the cost of the path to the destination through that router. Initially, the routing table is empty. The routing table is synchronously updated as follows. In each updation interval, three tasks are performed.
1. A node determines whether its neighbours in the graph are accessible. If so, it sets the tentative cost to each accessible neighbour as 1. Otherwise, the cost is set to ∞.
2. From each accessible neighbour, it gets the costs to relay to other nodes via that neighbour (as the next hop).
3. Each node updates its routing table based on the information received in the previous two steps by choosing the minimum cost.
For the graph given above, possible routing tables for various nodes after they have stabilized, are shown in the following options. Identify the correct table.
 A >100 but finite B ∞ C 3 D >3 and ≤100
Theory-of-Computation       Graphs       Gate 2005-IT
Question 156 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 157

 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 157 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 158
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 158 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 159

 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 159 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 160
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 160 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 161
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 161 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 162
Which one of the following strings is not a member of L (M)?
 A aaa B aabab C baaba D bab
Theory-of-Computation       Push-Down-Automata       Gate 2004-IT
Question 162 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 163
Nobody knows yet if P = NP. Consider the language L defined as follows : Which of the following statements is true ?
 A L is recursive B L is recursively enumerable but not recursive C L is not recursively enumerable D Whether L is recursive or not will be known after we find out if P = NP
Theory-of-Computation       Recursive-Enumerable-Languages       Gate-2003
Question 163 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 164
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 164 Explanation:
Both (A) and the given expression generates all strings over Σ.
Option (B) and (C) doesn't generate 11.
 Question 165
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 165 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 166
Consider the following deterministic finite state automaton M. Let S denote the set of seven bit binary strings in which the first, the fourth, and the last bits are 1. The number of strings in S that are accepted by M is
 A 1 B 5 C 7 D 8
Theory-of-Computation       Finite-Automata       Gate-2003
Question 166 Explanation:

There are possible: 7 strings
 Question 167
Let G = ({S}, {a, b} R, S) be a context free grammar where the rule set R is S → a S b | SS | ε Which of the following statements is true?
 A G is not ambiguous B There exist x, y ∈ L(G) such that xy ∉ L(G) C There is a deterministic pushdown automaton that accepts L(G) D We can find a deterministic finite state automaton that accepts L(G)
Theory-of-Computation       Contest-Free-Grammar       Gate-2003
Question 167 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 168
Consider two languages L1 and L2 each on the alphabet ∑. Let f : ∑ → ∑ be a polynomial time computable bijection such that (∀ x) [x ∈ L1 iff f(x) ∈ L2]. Further, let f-1 be also polynomial time computable. Which of the following CANNOT be true?
 A L1 ∈ P and L2 is finite B L1 ∈ NP and L2 ∈ P C L1 is undecidable and L2 is decidable D L1 is recursively enumerable and L2 is recursive
Theory-of-Computation       Decidability-and-Undecidability       Gate-2003
Question 168 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 169
A single tape Turing Machine M has two states q0 and q1, of which q0 is the starting state. The tape alphabet of M is {0, 1, B} and its input alphabet is {0, 1}. The symbol B is the blank symbol used to indicate end of an input string. The transition function of M is described in the following table
 0 1 B q0 q1, 1, R q1, 1, R Halt q1 q1, 1, R q0, 1, L q0, B, L
The table is interpreted as illustrated below. The entry (q1, 1, R) in row q0 and column 1 signifies that if M is in state q0 and reads 1 on the current tape square, then it writes 1 on the same tape square, moves its tape head one position to the right and transitions to state q1. Which of the following statements is true about M ?
 A M does not halt on any string in (0+1)+ B M does not halt on any string in (00+1)* C M halts on all strings ending in a 0 D M halts on all strings ending in a 1
Theory-of-Computation       Turing Machine       Gate-2003
Question 169 Explanation:

Try for any string, it will not Halt for any string other than ϵ. Hence, option (A) is correct.
 Question 170
Define languages L0 and L1 as follows :
```L0 = {< M, w, 0 > | M halts on w}
L1 = {< M, w, 1 > | M does not halts on w}```
Here < M, w, i > is a triplet, whose first component. M is an encoding of a Turing Machine, second component, w, is a string, and third component, i, is a bit. Let L = L0 ∪ L1. Which of the following is true ?
 A B C D
Theory-of-Computation       Turing Machine       Gate-2003
Question 170 Explanation:
A language L is recursive when we have a TM for L which give guarantee of halting in both cases, i.e., for string acceptance and for string rejection.
A language L is recursively enumerable when we have a TM for L which give guarantee of halting only in case of string acceptance and for string rejection the TM may or may not halt.
A language is not recursively enumerable if we don't have TM which give guarantee for halting even in case of string present in language. In other words if we don't have Turing machine for a language.
Now the language L=L0 UNION L1 is recursive or recursively enumerable is decided based on the type of Turing machine it have.
Assume we have a Turing machine M1 for language L. Now we need to analyse the type of this Turing machine.
Suppose M1 is given a string and suppose that this M doesnot halt on "w" . So this string is present in L1 hence it is present in L.
Now M1 will run encoding of "M" on string "w". Since M doesn't halt on "w". So M1 will also not halt (as M1 is running M on w).
Since string is present in language and even though our assumed TM M1 doesn't give guarantee for halting, Hence the language L is not recursively enumerable.
The same logic is for L' also.
As L'= { | M doesn't halt on w} Union { | M halt on w} . So this is also not recursively enumerable as M1 will not halt for string which is present in language.
 Question 171
Consider the NFA M shown below. Let the language accepted by M be L. Let L1 be the language accepted by the NFA M1, obtained by changing the accepting state of M to a non-accepting state and by changing the non-accepting state of M to accepting states. Which of the following statements is true ?
 A L1 = {0,1}* - L B L1 = {0,1}* C L1 ⊆ L D L1 = L
Theory-of-Computation       Finite-Automata       Gate-2003
Question 171 Explanation:
As in the question said,

As in above NFA language,
L1 is {0,1}*.
 Question 172
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 172 Explanation:
Push down automata accept context free grammars but here the value of stack is limited 10 then it accepts regular languages.
 Question 173

 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 173 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 174
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 174 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 175
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 175 Explanation:
Recursive languages are closed under complementation.
 Question 176
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 176 Explanation:
C and C++ are context sensitive languages.
 Question 177
 A Theory Explanation is given below.
Theory-of-Computation       Turing Machine       Gate-2002
 Question 178
 A Theory Explanation is given below.
Theory-of-Computation       Finite-Automata       Gate-2002
 Question 179
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 179 Explanation:
If we draw DFA for language S and T it will represent same.
 Question 180

 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 180 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 181
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 181 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 182

 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 182 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 183

 A Theory Explanation is given below.
Theory-of-Computation       Descriptive       Gate-2000
Question 183 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 184

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

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

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 automaton accepting L is

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

Equivalent DFA:

Hence, 5 states.
 Question 196
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 196 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 197
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 197 Explanation:
Uncountable: Set of all languages over Σ is uncountable.
 Question 198
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 198 Explanation:
(A) generates 100.
(B) generates 100 as substring.
(C) doesn't generate 1.
 Question 199
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 199 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 200

 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 200 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 201

 A (i) and (ii) B (ii) and (iii) C (i) and (iii) D (iii) and (iv)
Theory-of-Computation       Regular-Expressions       Gate-1996
Question 201 Explanation:
(00)*(ε+0),0*
In these two, we have any no. of 0's as well as null.
 Question 202
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 202 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 203
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 203 Explanation:
L = {ambn|m ≥ 1, n ≥ 1}
Here, m and n are independent.
So 'L' Is Regular.
 Question 204
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 204 Explanation:
Context free languages are not closed under intersection.
 Question 205

 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 205 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 206

 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 206 Explanation:
We have to generate
"if a then if b then c:=d else c:=f".
Parse tree 1:

Parse tree 2:
 Question 207

 A 4 B 3 C 2 D 1
Theory-of-Computation       Finite-Automata       Gate-1996
Question 207 Explanation:
3 states are required in the minimized machine states B and C can be combined as follows:
 Question 208
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 208 Explanation:
Which is to be letter followed by any number of letters (or) digits
L(L ∪ D)*
 Question 209

 A Context free B Regular C Context sensitive D LR(k)
Theory-of-Computation       General       Gate-1995
Question 209 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 210

 A I only B I and II C II and III D II only
Theory-of-Computation       Regular Languages       Gate-1995
Question 210 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 211

 A 01 B 10 C 101 D 110
Theory-of-Computation       Finite-State-Machine       Gate-1995
Question 211 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 212
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 212 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 213
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 213 Explanation:
NPDA to DPDA conversion is not possible. They have different powers.
 Question 214
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 214 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 215

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

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

 A B C D E
Theory-of-Computation       Finite-Automata       Gate-1993
 Question 218
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 218 Explanation:
Note: Out of syllabus.
 Question 219

 A FOLLOW(A) and LFOLLOW (A) may be different. B FOLLOW(A) and RFOLLOW (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 219 Explanation:
 Question 220
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 220 Explanation:
(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 221
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 221 Explanation:
For CNF, it is
2l - 1
For GNF, it is
l
 Question 222
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 222 Explanation:
CFL's are not closed under intersection and complementation.
 Question 223

 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 223 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 224

 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 224 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 225
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 225 Explanation:
Context free languages closed under Union, concatenation and kleen star. But not close under intersection and complementation.
 Question 226
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 226 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 227
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 227 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 228

 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 228 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 229

 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 229 Explanation:
The given X is a Halting problem. So which is to be undecidable but partially decidable.
 Question 230

 A Theory Explanation is given below.
Theory-of-Computation       Finite-Automata       Gate-2001
 Question 231
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 232

 A Theory Explanation is given below.
Theory-of-Computation       Turing Machine       Gate-2001
 Question 233

 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 233 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 234

 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 234 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 235

 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 235 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 236

 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 236 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 237

 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 237 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 238
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 238 Explanation:
Regular languages closed under Union, Intersection, Concatenation and Complementation but CFC is only closed under Union and Concatenation.
 Question 239
Which of the following problems are decidable?
 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 239 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 240
Regularity is preserved under the operation of string reversal.
 A True B False
Theory-of-Computation       Regular-Language       GATE-1987
Question 240 Explanation:
Regular language is closed under reversal.
 Question 241
All subsets of regular sets are regular.
 A True B False
Theory-of-Computation       Regular-Language       GATE-1987
Question 241 Explanation:
a*b* is regular but its subset anbn is not regular.
 Question 242
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 242 Explanation:
A minimal DFA is equivalent to a NDFA with n nodes has atmost 2n states and does not have always 2n states.
 Question 243
The intersection of two CFL's is also a CFL.
 A True B False
Theory-of-Computation       Context-Free-Language       GATE-1987
Question 243 Explanation:
Context free language is not closed under intersection.
 Question 244
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 244 Explanation:
If A is decidable, then A and A' are accepted by Turing machine.
 Question 245
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 245 Explanation:
An ambiguous grammar produces more than one parse tree for some string.
 Question 246
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 246 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 246 questions to complete.