www.LearnEngineering.

in

No part of this publication may be reproduced or distributed in any form or any means, electronic, mechanical,
photocopying, or otherwise without the prior permission of the author.

.in
ng
eri
GATE SOLVED PAPER
Computer Science Engineering
Theory of Computation e
gin
Copyright © By NODIA & COMPANY
En
arn

Information contained in this book has been obtained by authors, from sources believes to be reliable. However,
neither Nodia nor its authors guarantee the accuracy or completeness of any information herein, and Nodia nor its
authors shall be responsible for any error, omissions, or damages arising out of use of this information. This book
is published with the understanding that Nodia and its authors are supplying information but are not attempting
to render engineering or other professional services.
Le
w.
ww

NODIA AND COMPANY

B-8, Dhanshree Tower Ist, Central Spine, Vidyadhar Nagar, Jaipur 302039
Ph : +91 - 141 - 2101150
www.nodia.co.in
email : [email protected]

www.LearnEngineering.in
 www.LearnEngineering.in

GATE SOLVED PAPER - CS

THEORY OF COMPUTATION

YEAR 2001

Q. 1 Consider the following two statements :

.in
S1 : {02n n $ 1 } is a regular language
S2 : {0m 1n 0m n+ m $ 1 and n $ 1 } is a regular language
Which of the following statements is incorrect ?

ng
(A) Only S1 is correct (B) Only S2 is correct
(C) BothS1 and S2 are correct (D) None of S1 and S2 is correct.

eri
Q. 2 Which of the following statements true ?
(A) If a language is context free it can be always be accepted by a deterministic
push-down automaton.

e
(B) The union of two context free language is context free.
(C) The intersection of two context free language is context free
gin
(D) The complement of a context free language is context free

Q. 3 Given an arbitary non-deterministic finite automaton (NFA) with N states, the

maximum number of states in an equivalent minimized DFA is at least.
En

(A) N2 (B) 2N
(C) 2N (D) N!

Q. 4 Consider a DFA over S {a, b=} accepting all strings which have number of a's
arn

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
Le

(C) 15 (D) 48

Q. 5 Consider the following languages :

L1 =
{ww w ! {a, b} )}
w.

L2 {wwR w ! {a, b})wR is the reverse of w}

=
L3 {02i i is an integer}
=
2
L4 {0i i is an integer}
=
ww

Which of the languages are regular ?

(A) Only L1 and L2 (B) Only L2, L3 and L4
(C) Only L3 and L4 (D) Only L3

Q. 6 Consider the following problem x .

Given a Turing machine M over the input alphabet ,Sany state q of M .
And a word w ! )Sdoes the computation of M on w visit the state q ?
Which of the following statements about x is correct ?
(A) x is decidable
(B) x is undecidable but partially decidable

www.LearnEngineering.in
 www.LearnEngineering.in
GATE SOLVED PAPER - CS THEORY OF COMPUTATION

(C) x is undecidable and not even partially decidable

(D) x is not a decision problem

YEAR 2002

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

.in
Q. 8 Which of the following is true ?
(A) The complement of a recursive language is recursive.

ng
(B) The complement of a recursively enumerable language is recursively
enumerable.
(C) The complement of a recursive language is either recursive or recursively

eri
enumerable.
(D) The complement of a context-free language is context-free.

Q. 9 The C language is :
(A) A context free language
e (B) A context sensitive language
gin
(C) A regular language (D) Parsable fully only by a Turing
machine

Q. 10 The language accepted by a Pushdown Automaton in which the stack is limited

to 10 items is best described as
En

(A) Context free (B) Regular

(C) Deterministic Context free (D) Recursive
arn

YEAR 2003 ONE MARK

Q. 11 Ram and Shyam have been asked to show that a certain problem Pis NP-
complete. Ram shows a polynomial time reduction from the 3-SAT problem to P
Le

, and Shyam shows a polynomial time reduction from P to 3-SAT. Which of the
following can be inferred from these reduction?
(A) P is NP-hard but not NP-complete
w.

(b) P
is in NP, but is not NP-complete
(C) P is NP-complete
(D) P is neither Np-hard, nor in NP
ww

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

(0 + 1)* if P = NP
L = *
f
othervise
Which of the following statements is true?
(A) L is recursive
(B) L is recursively enumerable but not recu
(C) L is not recursively enumerable
(D) Whether L is recursive or not will be known after we find out if P =
NP

www.LearnEngineering.in
 www.LearnEngineering.in
GATE SOLVED PAPER - CS THEORY OF COMPUTATION

Q. 13 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

Q. 14 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

.in
(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

ng
YEAR 2003 TWO MARKS

eri
Q. 15 Consider the following deterministic finite state automaton M .

e
gin
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
En

(C) 7 (D) 8

Q. 16 Let G =
({S},{ a, b} R, S be a context free grammar where the rule set R is
arn

S " a S b|S S| e

Which of the following statements is true?

(A) G is not ambiguous
Le

(B) There exist x, y, ! L (G) such that xy z 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)
w.

Q. 17 Consider two languages L1 and L2 each on the alphabet / . Let f: / " / be a

polynomial time computable bijection such that (6x [x ! L1 iff f (x) ! L2]. Further,
let f1 be also polynomial time commutable.
ww

Which of the following CANNOT be true?

(A) L1 ! P and L2 finite
(B) L1 ! NP and L2 ! P
(C) L1 is undecidable and L2 is decidable
(D) L1 is recursively enumerable and L2 is recursive

Q. 18 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

www.LearnEngineering.in
 www.LearnEngineering.in
GATE SOLVED PAPER - CS THEORY OF COMPUTATION

0 1 B
0 1, 1,R 1, 1,R
q q Q Halt
q1 q1, 1,R q0, 1,L qH0, 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 ?

.in
(A) M does not halt on any string in (0 1+) +
(B) M dies not halt on any string in (00 1+)*
(C) M halts on all string ending in a 0

ng
(D) M halts on all string ending in a 1

Q. 19 Define languages L0 and L1 as follows

eri
L0 = { M, w, 0 <| M halts on w} >
L0 = { 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, t , is a bit.
Let L =
e
L0 , L1 . Which of the following is true?
gin
(A) L is recursively enumerable, but L is not
(B) L is recursively enumerable, but L is not
(C) Both L and L are recursive
(D) Neither L nor L is recursively enumerable
En

Q. 20 Consider the NFAM shown below.

arn
Le

Let the language accepted by M be L. Let L1 be the language accepted by the

w.

NFAM1 , 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}*
ww

(C) L1 3 L (D) L1 = L

YEAR 2004 ONE MARK

Q. 21 The problems 3-SAT and 2-SAT are

(A) both in P
(B) both NP-complete
(C) NP-complete and in P respectively
(D) undecidable and NP-complete respectively

www.LearnEngineering.in
 www.LearnEngineering.in
GATE SOLVED PAPER - CS THEORY OF COMPUTATION

YEAR 2004 TWO MARKS

Q. 22 The following finite state machine accepts all those binary strings in which the
number of 1’s and 0’s are respectively

.in
ng
(A) divisible by 3 and 2 (B) odd and even
(C) even and odd (D) divisible by 2 and 3
n+
Q. 23 The language {am bm | m, n # 1} is

eri
(A) regular (B) context-free but not regular
(C) context sensitive but not context free (D) type-0 but not context sensitive

Q. 24 Consider the flowing grammar C

S " bS | aA | b e
gin
A " bA | aB
B " bB | aS | a

Let Na (W) and Nb (W) denote the number of a’s and b’s in a string W respectively.
En

The language L (G) 3 {a, b} +generated by G is

(A) {W | Na (W) > 3Nb (W)} (B) {W | Nb (W) > 3Na (W)}
(C) {W | Na (W) = 3k, k ! {0,1,2,...}} (D) {W | Nb (W) = 3k, k ! {0,1,2,...}}
arn

Q. 25 L1 is a recursively enumerable language over / . An algorithm A effectively

enumerates its words as w1, w2, w3,.... Define another language L2 over / j {#} as
{wi #wj : wi, wj ! L1, i <
j}. Here # is a new symbol. Consider the following assertion.
Le

S1: L1 is recursive implies L2 is recursive

S2: L2 is recursive implies L1 is recursive
Which of the following statements is true?
(A) Both S1 and S2 are true
w.

(B) S1 is true but S2 is not necessarily true

(C) S2 is true but S1 ins necessarily true
ww

(D) Neither is necessarily true

YEAR 2005 TWO MARKS

Q. 26 Consider three decision problem 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) PL3 is undecidable if P2 is reducible to P3
(D) P3 is decidable if P3 is reducible to P2 ’s complement

www.LearnEngineering.in
 www.LearnEngineering.in
GATE SOLVED PAPER - CS THEORY OF COMPUTATION

Q. 27 Consider the machine M

.in
The language recognized by M is
(A) {W ! {a, b}*/ every a in w is followed by exactly two b's}

ng
(B) {W ! {a, b}*/ every a in w is followed by at least two b's}
(C) {W ! {a, b}*/ w contains the substring ‘abb’

eri
(D) {W ! {a, b}*/ w does not contain ‘aa’ as a substring}

Q. 28 Let Nf and Np denote the classes of languages accepted by non-deterministic

finite automata and non-deterministic push-down automata, respectively. let Df

e
and DP denote the classes of languages accepted by deterministic finite automata
gin
and deterministic push-down automata, respectively. Which one of the following
is TRUE?
(A) Df 1 Nf and DP 1 NP (B) Df 1 Nf and DP = NP
(C) Df = Nf and DP = NP (D) Df = Nf and DP 1 NP
En

Q. 29 Consider the languages

L1 {+an bn cm | n, m >0} and L2 = {an bm cm | n, m >0}
(A) L1 + L2 is a context-free language (B) L1 , L2 is a context-free language
arn

(C) L1 and L2 are context-free language (D) L1 + L2 is a context sensitive

language

Q. 30 Let L1 be a recursive language, and let L2 be a recursively enumerable but not a

Le

recursive language. Which one of the following is TRUE?

(A) L1 is recursive and L2 is recursively enumerable
(B) L1 is recursive and L2 is not recursively enumerable
w.

(C) L1 and L2 are recursively enumerable

(D) L1 is recursively enumerable and L2 is recursive

Q. 31 Consider the languages

ww

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

www.LearnEngineering.in
 www.LearnEngineering.in
GATE SOLVED PAPER - CS THEORY OF COMPUTATION

Q. 32 Consider the following two problems on undirected graphs

: aGiven G (V, E), does G have an independent set of size | V | 4-?

: bGiven G (V, E), does G have an independent set of size 5?

Which one of the following is TRUE?

(A) a is in the P and b is NP-complete
(B) a is NP-complete and bis P
(C) Both a and b are NP-complete

.in
(D) Both a
and b
are in P

YEAR 2006 ONE MARK

ng
Q. 33 Let S be an NP -complete problem Q and R be two other problems not known to
be in NP . Q is polynomial-time reducible to S and S is polynomial-time reducible

eri
to R. Which one of the following statements is true?
(A) R is NP -complete (B) R is NP -hard
(C) Q is NP -complete (D) Q is NP -hard

Q. 34 Let
e
L1 {0n m 1n 0m | n, m # 0}, L2 = {0n +m 1n m 0m | n, m # 0}, and =
gin
n m n +m n m
L3 = {0 1 0 | n,+m # 0}. Which
+
of these languages are NOT context free?
(A) L1 only (B) L3 only
(C) L1 and L2 (D) L2 and L3
En

YEAR 2006 TWO MARKS

Q. 35 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?
arn

(A) L {s ! (0 =1)*| n0 (s) is a 3-digit+ prime}

(B) L {s ! (0 =1)*| for every prefixes’+ -1 (s')| # 2}
of s,| n0 (s') n
(C) L {s ! (0 =1)*|| n0 (s) n1 (s) + #4 -
Le

(D) L {s ! (0 =1)*| n0 (s) mod 7=+

n1 (s) mod5 =}
0

Q. 36 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) mod 5=2+and d (s) mod 7 ! 4}
w.

Which one of the following statements is true?

(A) L is recursively enumerable, but not recursive
(B) L is recursive, but not context-free
ww

(C) L is context_free, but not regular

(D) Lis regular

Q. 37 Let SHAM, be the problem of finding a Hamiltonian cycle in a graph G (+V, E)

with [V] divisible by 3 and DHAM’ be the problem of determining if a Hamltonian
cycle exists in such graphs. Which one of the following is true?
(A) Both DHAM, and SHAM, are NP-hard
(B) SHAM, is NP-hard, but DHAM, is not
(C) DHAM, is NP-hard, but SHAM, is not
(D) Neither DHAM,nor SHAM, is NP-hard

www.LearnEngineering.in
 www.LearnEngineering.in
GATE SOLVED PAPER - CS THEORY OF COMPUTATION

Q. 38 Consider the following statements about the context-free grammar,

G = {S " SS, S " ab, S " ba, S "!}
1. G is ambiguous.
2. G produces all strings with equal number of a’s and b’s .
3. G can be accepted by a deterministic PDA.
Which combination below expresses all the true statements about G ?
(A) 1 only (B) 1 and 3 only
(C) 2 and 3 only (D) 1, 2 and 3

.in
Q. 39 Let L1 be 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?

ng
(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

eri
Q. 40 Consider the regular language L (111 =111111)* . The
+ minimum number of
states in any DFA accepting this languages is
(A) 3 (B) 5
(C) 8
e (D) 9
gin
YEAR 2007 ONE MARK

Q. 41 Which of the following problems is undecidable?

En

(A) Membership problem for CFGs

(B) Ambiguity problem for CFGs
(C) Finiteness problem for FSAs
arn

(D) Equivalence problem for FSAs

Q. 42 Which of the following is TRUE?

(A) Every subset of a regular set is regular
Le

(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
w.

YEAR 2007 TWO MARKS

ww

Q. 43 A minimum state deterministic finite automation accepting the language

L = {w | w ! (0, 1}* , number of 0s &1s in w are divisible by 3 and 5, respectively}
has
(A) 15 states (B) 11 states
(C) 10 states (D) 9 states

Q. 44 The language L = {0T 21i | i # 0} over the alphabet {0,1,2) is

(A) not recursive
(B) is recursive and is a deterministic CFL
(C) us a regular language
(D) is not a deterministic CFI but a CFL

www.LearnEngineering.in
 www.LearnEngineering.in
GATE SOLVED PAPER - CS THEORY OF COMPUTATION

Q. 45 Which of the following languages is regular?

(A) {WWR | W ! {0,1} +}

(B) {WWR X | X, W ! {0,1} +}

(C) {WXWR X | X, W ! {0,1} +}

(D) {XWWR X | X, W ! {0,1} +}

Common Data For Q. 46 & 47

.in
Solve the problems and choose the correct answers.
Consider the following Finite State Automation

ng
e eri
gin
Q. 46 The language accepted by this automaton is given by the regular expression
(A) b * ab * ab * ab * (B) (a b+)*
(C) b * a (a b+)* (D) b * ab * ab *
En

Q. 47 The minimum state automaton equivalent to the above FSA has the following
number of states
(A) 1 (B) 2
(C) 3 (D) 4
arn

YEAR 2008 ONE MARK

Q. 48 Which of the following in true for the language{aP | P is a prime}?

Le

(A) It is not accepted by a Turning Machine

(B) It is regular but not context-free
(C) It is context-free but not regular
w.

(D) It is neither regular nor context-free, but accepted by a Turing machine

Q. 49 Which of the following are decidable?

ww

1. Whether the intersection of two regular languages is infinite

2. Whether a given context-free language is regular
3. Whether two push-down automata accept the same language
4. Whether a given grammar is context-free
(A) 1 and 2 (B) 1 and 4
(C) 2 and 3 (D) 2 and 4

Q. 50 If L and L are recursively enumerable then L is

(A) regular (B) context-free
(C) context-sensitive (D) recursive

www.LearnEngineering.in
 www.LearnEngineering.in
GATE SOLVED PAPER - CS THEORY OF COMPUTATION

YEAR 2008 TWO MARKS

Q. 51 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

Q. 52 Given below are two finite state automata("indicates the start and F indicates

.in
a final state)
Y: Z:
a b a b

ng
" 1 2 " 2 2
2F 2 1 2F 1 1

eri
(A) (B)
a b
e a b
gin
-P S R -P S Q
Q R S Q R S
R(F) Q P R(F) Q P
S Q P S Q P
En

(C) (D)
a b a b
-P Q S -P S Q
arn

Q R S Q S R
R(F) Q P R(F) Q P
S Q P S Q P
Le

Q. 53 Which of the following statements are true ?

1. Every left-recursive grammar can be converted to a right-recursive grammar
w.

and vice-versa
e
2. All -productions can be removed from any context-free grammar by
suitable transformations
ww

3. The language generated by a context-free grammar all of whose production

are of the form X " w or X " wY (where, w is a staring of terminals and Y
is a non-terminal), is always regular
4. The derivation trees of strings generated by a context-free grammar in
Chomsky Normal Form are always binary trees.
(A) 1, 2, 3 and 4
(B) 2, 3 and 4 only
(C) 1, 3 and 4 only
(D) 1, 2 and 4 only

www.LearnEngineering.in
 www.LearnEngineering.in
GATE SOLVED PAPER - CS THEORY OF COMPUTATION

Q. 54 Match List-I with List-II and select the correct answer using the codes given
below the lists:
List-I List-II
P. Checking that identifiers are declared before 1. L = {a"b"c"d"| n # 1, m # 1}
their use
Q. Number of formal parameters in the declara- 2. X " XbX | XcX | dXf | g
tion to a function agress with the number of
actual parameters in a use of that function
R. Arithmetic expressions with matched pairs 3. L =
{wcw | w ! (a | b)*}

.in
of parentheses
S. Palindromes 4. X " bXb | cXc | e
Codes:

ng
P Q R S
(A) 1 3 2 4
(B) 3 1 4 2

eri
(C) 3 1 2 4
(D) 1 3 4 2
Match List I with List II and select the correct answer using the codes given
Q. 55

below the lists: e

gin
En
arn
Le
w.
ww

www.LearnEngineering.in
 www.LearnEngineering.in
GATE SOLVED PAPER - CS THEORY OF COMPUTATION

.in
Code:
a b c d
(A) 2 1 3 4

ng
(B) 1 3 3 4
(C) 1 2 3 4
(D) 3 2 1 4

eri
Q. 56 Which of the following are regular sets?
1. {an b2m | n # 0, m # 0}
2. {an bm | n = 2m}
n m
3. {a b | n ! m}
e
gin
4. {xcy | x, y ! {a, b}*}
(A) 1 and 4 only (B) 1 and 3 only
(C) 1 only (D) 4 only
En

YEAR 2009 ONE MARK

Q. 57 S " aSa bSb a b

arn

The language generated by the above grammar over the alphabet {a, b} is the set
of
(A) all palindromes
(B) all odd length palindromes
Le

(C) strings that begin and end with the same symbol
(D) all even length palindromes
w.

Q. 58 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)) ? + +
ww

(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 being and end with either 0 or 1

Q. 59 Which one of the following is FALSE ?

(A) There is a unique minimal DFA for every regular language
(B) Every NFA can be converted to an equivalent PDA
(C) Complement of every context-free language is recursive
(D) Every nondeterministic PDAcan be converted to an equivalent deterministic
PDA

www.LearnEngineering.in
 www.LearnEngineering.in
GATE SOLVED PAPER - CS THEORY OF COMPUTATION

Q. 60 Match all items in Group I with correct options from those given in Group 2
Group 1 Group 2
P. Regular expression 1. Syntax analysis
Q. Pushdown automata 2. Code generation
R. Data flow analysis 3. Lexical analysis
S. Register allocation 4. Code Optimization

(A) P-4, Q-1, R-2, S-3 (B) P-3, Q-1, R-4, S-2

.in
(C) P-3, Q-4, R-1, S-2 (D) P-2, Q-1, R-4, S-3

YEAR 2009 TWO MARKS

ng
Q. 61 Given the following state table of an FSM with two states A and B , one input
and one output :

eri
Present Present Input Next Next Output
State A State B State A State B
0 0 0 0 0 1
0 1 0e 1 0 0
gin
1 0 0 0 1 0
1 1 0 1 0 0
0 0 1 0 1 0
En

0 1 1 0 0 1
1 0 1 0 1 1
1 1 1 0 0 1
arn

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
Le

(C) 5 (D) 6

Q. 62 Let L = L1 + L2 where L1 and L2 are language as defined below :

L1 = {am bm can bn m, n $ 0}
w.

L2 = {ai b j ck i, j, k $ 0}
Then L is
(A) Not recursive (B) Regular
ww

(C) Context-free but not regular

(D) Recursively enumerable nut not context-free

Q. 63 The following DFA accept the set of all string over {0, 1} that

(A) Begin either with 0 or 1 (B) End with 0

(C) End with 00 (D) Contain the substring 00

www.LearnEngineering.in
 www.LearnEngineering.in
GATE SOLVED PAPER - CS THEORY OF COMPUTATION

YEAR 2010 ONE MARK

Q. 64 Let L1 be a recursive language. Let L2 and L3 be language that are recursively

enumerable but not recursive. What of the following statements is not necessarily
true ?
(A) L1 L -1 is recursively enumerable
(B) L1 L -3 is recursively enumerable
(C) L2 + L3 is recursively enumerable
(D) L2 + L3 is recursively enumerable

.in
YEAR 2010 TWO MARKS

Q. 65 Let L { ! (0 =1)) w has even number + of 1s}, i.e.,

w L is the set of all bit

ng
strings with even number of 1s. Which one of the regular expressions below
represents L ?
(A) (0)10)1)) (B) 0)(10)10)))

eri
(C) 0)(10)1))0) (D) 0)1 (10)1))10)

Q. 66 Consider the language L1 {0i 1 j i Y= j}, L2 {0i 1 j i ==j}, L3 {0i 1 j i ==2j 1} =

L4 {0i 1 j i Y= 2j}.Which one of =
the following statements is true ?
(A) Only L2 is context free e
gin
(B) Only L2 and L3 are context free
(C) Only L1 and L2 are context free
(D) All are context free
En

Q. 67 Let w by any string of length n in{0, 1}). Let L be the set of all substring so . w
What is the minimum number of states in a non-deterministic finite automation
that accepts L ?
arn

(A) n 1- (B) n
(C) n 1+ (D) 2n 1+

YEAR 2011 ONE MARK

Le

Q. 68 Which of the following pairs have DIFFERENT expressive power?

(A) Deterministic finite automata (DFA) and Non-deterministic finite automata
(NFA)
w.

(B) Deterministic push down automata (DPDA) and Non-deterministic push

down automata (NPDA)
ww

(C) Deterministic single-tape Turing machine and Non-deterministic single-tape

Turing machine
(D) Single-tape Turing machine and multi-tape Turing machine

Q. 69 The lexical analysis for a modern computer language such as Java needs the
power of which one of the following machine models in a necessary and sufficient
sense?
(A) Finite state automata
(B) Deterministic pushdown automata
(C) Non-deterministic pushdown automata
(D) Turing machine

www.LearnEngineering.in
 www.LearnEngineering.in
GATE SOLVED PAPER - CS THEORY OF COMPUTATION

Q. 70 Let P be a regular language and Q be a context-free language such that Q 3 P .

(For example, let P be the language represented by the regular expression p * q *
and Q be $ pn qn n ! N . . Then which of the following is ALWAYS regular?
(A) P + Q (B) P Q -
(C) *S P - (D) *S Q -

YEAR 2011 TWO MARKS

Q. 71 Consider the languages L1, L2 and L3 are given below:

.in
L1 $0 p 1q p, q d N . , L2 $0 p 1q p, q d N and p q . and
=
L3 $0 p 1q 0r p, q, r d N and p q = r . =
Which of the following statements is NOT TRUE?

ng
(A) Push Down Automata (PDA) can be used to recognize L1 and L2
(B) L1 is a regular language
(C) All the three languages are context free

eri
(D) Turing machines can be used to recognize all the languages

Q. 72 Definition of a language L with alphabet "a , is given as follows:

L = $a k >
nk

e
0. , and n is a positive integer constant}
What is the minimum number of states needed in a dfa to recognize L?
gin
(A) k 1+ (B) n 1+
n 1+
(C) 2 (D) 2k 1+

Q. 73 A deterministic finite automaton (DFA) D with alphabet "a, b , is given

S=
En

below:
arn
Le

Which of the following finite state machines is a valid minimal DFA which accepts
the same language as D?
w.
ww

www.LearnEngineering.in
 www.LearnEngineering.in
GATE SOLVED PAPER - CS THEORY OF COMPUTATION

YEAR 2012 ONE MARK

Q. 74 assuming P Y =
NP , which of the following is TRUE?
(A) NP -complete = NP
(B) NP-complete + P = Q
(C) NP -hard = NP
(D) P = NP -complete

Q. 75 What is the complement of the language accepted by the NFA shown below?
Assume S = "a , and ise the empty string.

.in
ng
(A) Q (B) " ,e

eri
(C) a * (D) "a, , e

Q. 76 Which of the following problems are decidable?

e
1. Does a given program ever produce an output?
2. If L is a context-free language, then, is L also context-free?
gin
3. If L is a regular language, then, is L also regular
4. If L is a recursive language, then, is L also recursive?
(A) 1, 2, 3, 4
En

(B) 1, 2
(C) 2, 3, 4
(D) 3, 4
arn

Q. 77 Given the language L "ab, aa, baa , , which of the following strings are in L *?
=
1. abaabaaabaa
2. aaaabaaaa
Le

3. baaaaabaaaab
4. baaaaabaa
(A) 1, 2 and 3
w.

(B) 2, 3 and 4
(C) 1, 2 and 4
(D) 1, 3 and 4
ww

YEAR 2012 TWO MARKS

Q. 78 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
complete DFA that accepts this language is shown below.
The missing arcs in the DFA are

www.LearnEngineering.in
 www.LearnEngineering.in
GATE SOLVED PAPER - CS THEORY OF COMPUTATION

.in
ng
eri
(A) (B)
00 01 10 11 q 00 01 10 11 q
00 1 0
e 00 0 1
gin
01 1 01 1
10 0 10 0
11 0 11 0
(C) (D)
En

00 01 10 11 q 00 01 10 11 q
00 1 0 00 1 0
arn

01 1 01 1
10 0 10 0
11 0 11 0
Le

**********
w.
ww

www.LearnEngineering.in
 www.LearnEngineering.in
GATE SOLVED PAPER - CS THEORY OF COMPUTATION

ANSWER KEY
Theory of Computation
1 2 3 4 5 6 7 8 9 10
(A) (B) (C) (C) (C) (A) (B) (A) (A) (B)
11 12 13 14 15 16 17 18 19 20
(C) (A) (?) (D) (C) (C) (C) (A) (B) (C)
21 22 23 24 25 26 27 28 29 30
(C) (A) (B) (C) (B) (C) (B) (D) (A) (B)

.in
31 32 33 34 35 36 37 38 39 40
(B) (?) (B) (D) (C) (D) (?) (B) (B) (D)

ng
41 42 43 44 45 46 47 48 49 50
(B) (B) (A) (B) (C) (C) (B) (D) (B) (D)
51 52 53 54 55 56 57 58 59 60

eri
(D) (A) (C) (C) (C) (A) (B) (C) (D) (B)
61 62 63 64 65 66 67 68 69 70
(A) (C) (A) (B) (B) (D) (C) (B) (A) (C)
71 72 73 74 75 e 76 77 78
gin
(C) (B) (A) (B) (B) (D) (C) (D)
En
arn
Le
w.
ww

www.LearnEngineering.in