Theory of Computation

Let M be a nondeterministic finite automaton (NFA)
with 6 states over a finite alphabet. Which of the
following options CANNOT be the number of states in
the minimal deterministic finite automaton (DFA) that is
equivalent to M?

• (a). 32
• (b). 65
• (c). 1
• (d).128

Let L1 and L2 be two languages over a finite alphabet,
such that L1∩L2 and L2 are regular languages. Which of
the following statements is/are always true?

• (a). L1 is regular
• (b). L1∪L2 is regular
• (c). L2 is context-free
• (d). L1 is context-free

Consider the following two finite automata D1  and
D2  (as shown in the figure).

Which of the following statements is/are true?

• (a). L(D1)=L(D2)
• (b). L(D1) is a proper subset of L(D2)
• (c). L(D1)∩L(D2)={ε}
• (d). (L(D1)∪L(D2))* consists of all strings in {0,1}* whose length is divisible by 3

A regular language L is accepted by a non-deterministic
finite automaton (NFA) with n states. Which of the
following statement(s) is/are FALSE?

• (a). L may have an accepting NFA with < n states.
• (b). L may have an accepting DFA with < n states.
• (c). There exists a DFA with ≤ 2n states that accepts L.
• (d). Every DFA that accepts L has > 2n states.

Let S be the set of all ternary strings defined over the
alphabet {a, b, c}. Consider all strings in S that contain at
least one occurrence of two consecutive symbols, that is,
"aa", "bb" or "cc". The number of such strings of length 5
that are possible is _______. (Answer in integer)

Consider the following two languages over the alphabet {a,
b}:
L1 = { αβα | α ∈ {a, b}+ AND β ∈ {a, b}+ }
L2 = { αβα | α ∈ {a}+ AND β ∈ {a, b}+ }
Which ONE of the following statements is CORRECT?

• (a). Both L1 and L2 are regular languages.
• (b). L1 is a regular language but L2 is not a regular language.
• (c). L1 is not a regular language but L2 is a regular language.
• (d). Neither L1 nor L2 is a regular language.

Consider the following deterministic finite automaton
(DFA) defined over the alphabet, Σ = {a, b}. Identify which
of the following language(s) is/are accepted by the given
DFA.

THEORY OF COMPUTATION

• (a)The set of all strings containing an even number of b's.
• (b)The set of all strings containing the pattern bab.
• (c)The set of all strings ending with the pattern bab.
• (d)The set of all strings not containing the pattern aba.

Consider a finite state machine (FSM) with one input X
and one output f, represented by the given state transition
table. The minimum number of states required to realize
this FSM is ________. (Answer in integer)

Consider the two lists List I and List II given below:

List 1
List 2
(i) Context free languages

• (a)Closed under union (ii) Recursive languages
• (b)Not closed under complementation (iii) Regular languages
• (c)Closed under intersection For matching of items in List I with those in List II, which of the following option(s) is/are CORRECT?
• (a)(i) – (a), (ii) – (b), and (iii) – (c)
• (b)(i) – (b), (ii) – (a), and (iii) – (c)
• (c)(i) – (b), (ii) – (c), and (iii) – (a)
• (d)(i) – (a), (ii) – (c), and (iii) – (b)

Let Σ = {a, b, c}. For x ∈ Σ* , and α ∈ Σ, let #α(x) denote
the number of occurrences of α in x. Which one or more of
the following option(s) define(s) regular language(s)?

• (a){ambn | m, n ≥ 0}
• (b){a, b}* ∩ {ambn cm - n | m ≥ n ≥ 0}
• (c){w | w ∈ {a, b}* , #a (w) ≡ 2 (mod 7), and #b (w) ≡ 3 (mod 9)}
• (d){w | w ∈ {a, b}* , #a (w) ≡ 2 (mod 7), and #a (w) ≡ #b(w)}

Let Σ = {1,2,3,4}. For x ∈ Σ* , let prod(x) be the product of
symbols in x modulo 7. We take prod(ε) =1,where ε is the
null string .
For example, prod(124) = (1 × 2 × 4) mod 7 = 1.
Define L = {x ∈ Σ* | prod(x) = 2}.
The number of states in a minimum state DFA for L is
___________. (Answer in integer)

Consider the 5-state DFA M accepting the language L(M) ⊂
(0 + 1) * shown below. For any string w ∈ (0 + 1) * let n0(w)
be the number of 0 ' s in w and n1(w) be the number of 1's
in w.

Which of the following statements is/are FALSE?

• (a)States 2 and 4 are distinguishable in M
• (b)States 3 and 4 are distinguishable in M
• (c)States 2 and 5 are distinguishable in M
• (d)Any string w with n0 (w) = n1(w) is in L(M).

Let L1, L2 be two regular languages and L3 a language
which is not regular. Which of the following statements
is/are always TRUE?

• (a). L1 = L2 if and only if L1 ∩L2 = φ
• (b). L1 ∪L3 is not regular
• (c). L3 is not regular
• (d). L1 ∪L2 is regular THEORY OF COMPUTATION

Consider the following two regular expressions over the
alphabet {0,1}:
r = 0* + 1*
s = 01* + 10*
The total number of strings of length less than or equal to
5, which are neither in r nor in s, is _________

Which one of the following regular expressions is
equivalent to the language accepted by the DFA given
below?

• (a). 0*1(0 + 10*1)*
• (b). 0* (10*11) * 0 *
• (c). 0 *1(010*1)* 0*
• (d). 0(1 + 0*10*1)*0 *

Let M be the 5-state NFA with ε-transitions shown in the
diagram below

Which one of the following regular expressions
represents the language accepted by M ?

• (a). (00)* + 1(11)*
• (b). 0* + (1 + 0(00)* )(11)*
• (c). (00)* + (1 + (00)* )(11)*
• (d). 0+ + 1(11)* + 0(11)*

Let L1 be the language represented by the regular expression
b *ab * (ab *ab * ) * and L2 = { w ∈ (a + b) * | |w| ≤ 4}, where
|w| denotes the length of string w. The number of strings in
L2 which are also in L1 is ___________

Consider the following definition of a lexical token id for an
identifier in a programming language, using extended
regular expressions:
letter→[A-Za-z]
digit→[0-9]
id→letter(letter|digit)*
Which one of the following Non-deterministic
Finite-state Automata with - transitions accepts the
set of valid identifiers? (A double-circle denotes a
final state)

• (a).
• (b).
• (c).
• (d).

Consider the language L over the alphabet {0, 1}, given
below: L = {w ∈ {0, 1}* | w does not contain three or more
consecutive 1's}. The minimum number of states in a
Deterministic Finite-State Automaton (DFA) for L is _____.

THEORY OF COMPUTATION

Consider the Deterministic Finite-state Automaton (DFA)
A shown below. The DFA runs on the alphabet {0, 1},
and has the set of states {s, p, q, r}, with s being the start
state and p being the only final state.

Which one of the following regular expressions
correctly describes the language accepted by A?

• (a)1(0*11)*
• (b)0(0 + 1)*
• (c)1(0 + 11)*
• (d)1(110*)*

Which one of the following regular expression correctly
represents the language of the finite automata given
below?

• (a)ab*bab*+ba*aba*
• (b)(ab*b)*ab* + (ba*a)* ba*
• (c)(ab*b+ba*a)(a*+b*)
• (d)(ba*a+ab*b)*(ab*+ba*)

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

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

Consider the following statements.
I. If L1 U L2 is regular, then both L1 and L2 must be
regular.
II. The class of regular languages is closed under infinite
union.
Which of the above statements is/are TRUE?

• (a)Both I and II
• (b)II only
• (c)Neither I nor II
• (d)I only

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.L R = {xy | x ε L, yR ε L}

For Σ = {a,b}, let us consider the regular language L = {x|x
= a 2+3k or x = b 10+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

Let    Σ      be
the
set
of
all
bijections
from {1, ... ,5} to {1, ... ,5}, where id denotes the identity
function, i.e. id(j) = j, ∀j. Let ∘ denote composition on
functions.
For
a
string x= x1x2 ... xn∈Σn, n≥0,
let π(x) = x1 ∘x2 ∘⋯∘xn. Consider the language L=
{x∈Σ*|π(x) = id}. The minimum number of states in
any DFA accepting L is _______

THEORY OF COMPUTATION

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

The order of L1 is_______.

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

The minimum possible number of states of a deterministic
finite automaton that accepts the regular language
L = {w1aw2 | w1, w2 ∈ {a,b}*, |w1| = 2,|w2| ≥ 3} is
_________

• (a)8
• (b)9
• (c)10
• (d)11

Let
δ
denote
the
transition
function
and
δ̂ denote the extended transition function of the
ε-NFA whose transition table is given below:

δ
ε
a
b
→ q0 {q2} {q1} {q0}
q1
{q2} {q2} {q3}
q2
{q0} ∅
∅
q3
∅
∅
{q2}

Then δ̂ (q2 , aba) is:

• (a)∅
• (b){q0,q1,q3}
• (c){q0,q1,q2}
• (d){q0,q2,q3}

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

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 automaton (DFA) accepting L is _________

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} U {bn | n >= 0} U {anbn | n >= 0}
• (d){a,b}*

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

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

Consider
the
following
two
statements:
I. If all states of an NFA are accepting states then the
language
accepted
by
the
NFA
is
Σ*.
II. There exists a regular language A such that for all
languages B, A ∩B is regular.
Which one of the following is CORRECT?

• (a)Only I is true
• (b)Only II is true
• (c)Both I and II are true
• (d)Both I and II are false

The number of states in the minimum sized DFA that
accepts the language defined by the regular expression
(0+1)*(0+1)(0+1)*is_________.

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

Which of the following language is/are regular
languages?

L1 : {wxwR|w,x ε {a, b}* and |w|, |x| > 0}, wR is the
reverse of string w
L2 : {anbm | m != n and m, n >= 0}
L3 : {apbqcr | p, q, r >= 0}

• (a)L1 and L3 only
• (b)L2 only
• (c)L2 and L3 only
• (d)L3 only

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

Consider the alphabet Σ = {0, 1}, the null/empty string λ
and the sets of strings X0, X1 and X2 generated by the
corresponding grammar. X0, X1 and X2 are related as
follows :
X0 = 1X1
X1 = 0X1 + 1X2
X2 = 0X1 + {λ}
Which of the following choices precisely represents the
strings in X0?

• (a)10(0* + (10)* 1
• (b)10(0* + (10)*)* 1
• (c)1(0* + 10)* 1
• (d)10(0 + 10)* 1 + 110(0 + 10)* 1

The length of the shortest string NOT in the language (over
Σ = {a,b}) of the following regular expression is
a*b*(ba)*a* is ______________.

• (a)3
• (b)4
• (c)5
• (d)6

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 L1 nor L2 are regular THEORY OF COMPUTATION

Consider the finite automaton in the following figure.
What is the set of reachable states for the input string
0011?

• (a){q0,q1,q2}
• (b){q0,q1}
• (c){q0,q1,q2, q3}
• (d){ q3}

Which one of the following is TRUE?

• (a)The language L = {anbn | 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.

If L1 = {an | n > 0} and L2 = {bn | n >= 0}, consider
(I) L1.L2 is a regular language
(II) L1.L2 = {anbn | n >= 0}
Which one of the following is CORRECT?

• (a)Only (I)
• (b)Only (II)
• (c)Both (I) and (II)
• (d)Neither (I) nor (II)

Which of the regular expressions given below represent
the following DFA?

I)0*1(1+00*1)*
II)0*1*1+11*0*1
III) (0+1)*1

• (a)I and II only
• (b)I and III only
• (c)II and III only
• (d)I, II, and III

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

What is the complement of the language accepted by the
NFA shown below?
Assume Σ = {a} and ε is the empty string.

• (a)∅
• (b){ε}
• (c)a*
• (d){a ,ε}

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.

THEORY OF COMPUTATION

The missing arcs in the DFA are:

• (a).
• (b).
• (c).
• (d).

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

A deterministic finite automation (DFA) D with alphabet
Σ = {a, b} is given below.

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

• (a). THEORY OF COMPUTATION
• (b).
• (c).
• (d).

Definition of a language L with alphabet {a} is given as
following. L = {ank | k > 0, and n is a positive integer
constant} What is the minimum number of states needed
in a DFA to recognize L?

• (a)k+1
• (b)n+1
• (c)2 n+1
• (d)2 k+1

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 (NPDA)
• (c). Deterministic single-tape Turning machine and Non-deterministic single tape Turning machine
• (d). Single-tape Turning machine and multi-tape Turning machine

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

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

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*

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

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

Given below are two finite state automata (-> indicates
the start state and F indicates a final state)
Automaton Y

a
b
→1
1
2
2(F)
2
1

Automaton Z

a
b
→1
2
2
2(F)
1
1
Which of the following represents the product
automaton Z × Y?

• (a). a b →p S R Q R S R(F) Q P S Q P
• (b)a b →p S Q Q R S R(F) Q P S P Q
• (c)a b →p Q S Q R S R(F) Q P S Q P
• (d)a b →p S Q Q S R R(F) Q P S Q P THEORY OF COMPUTATION

Match the following NFAs with the regular expressions
they correspond to:

1. ε + 0(01*1 + 00)*01*
2. ε + 0(10*1 + 00)*0
3. ε + 0(10*1 + 10)*1
4. ε + 0(10*1 + 10)*10*

• (a)P – 2, Q – 1, R – 3, S – 4
• (b)P – 1, Q – 3, R – 2, S – 4
• (c)P – 1, Q – 2, R – 3, S – 4
• (d)P – 3, Q – 2, R – 1, S – 4

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*

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 ∩ L2c = ∅
• (d). L1 ∪ L2 ≠ L1

Which of the following are regular sets?
I. { anb2m | n ≥ 0, m ≥ 0 }
II. { anbm | n = 2m }
III. { anbm | n ≠ m }
IV. { xcy | x, y ∈ {a, b}* }

• (a)I and IV only
• (b)I and III only
• (c)I only
• (d)IV only M1 THEORY OF COMPUTATION

Consider the following Finite State Automaton:

The language accepted by this automaton is given by the
regular expression

• (a)b*ab*ab*ab*
• (b)(a+b)*
• (c)b* a(a+b)*
• (d)b*ab*ab*

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 of 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

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 automata which recognizes the language L(P) ∩
L(Q) is:

• (a).
• (b).
• (c).
• (d). THEORY OF COMPUTATION

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

• (a).
• (b)
• (c).
• (d).

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). THEORY OF COMPUTATION
• (d).

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}+ }

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

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

For a state machine with the following state diagram the
expression for the next state S+ in terms of the current
state 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'

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 }

Consider the machine M:

THEORY OF COMPUTATION
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's }
• (c){ w ∈ {a, b}* | w contains the substring 'abb' }
• (d){ w ∈ {a, b}* | w does not contain 'aa' as a substring }

The following diagram represents a finite state
machine which takes as input a binary number from
the least significant bit.

Which 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

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?

• (a)L1 = L2
• (b)L1 ⊂ L2
• (c)L2 ⊂ L1
• (d)None of the above

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

Consider the following grammar where S is the start
symbol, and a and b are
terminal symbols.
S→aSbS | bS | ε
Which of the following statements is/are true?

• (a)The grammar is ambiguous
• (b)The string abb has two distinct derivations in this grammar
• (c)The string abab has only one rightmost derivation
• (d)The language generated by the grammar is undecidable

Which of the following grammars is/are ambiguous?

• (a). S → aSb | ε
• (b). E → E + E | E * E | id
• (c). S → aS | Sa | ε
• (d). S → aS | ε

Let Σ = {a, b, c, d} and let L = { aibjckdl | i, j, k, l ≥ 0
}.
Which of the following constraints ensure(s) that the
language L is context-free?

• (a)i + k = j + l
• (b)i = k and j = l
• (c)i = l and j = k
• (d)i + j = k + l

Let G1, G2 be Context Free Grammars (CFGs) and R be a
regular expression. For a grammar G, let L(G) denote the
language generated by G.

Which ONE among the following questions is decidable?

• (a)Is L(G1 ) = L(G2 )?
• (b)Is L(G1 ) ∩ L(G2 ) = ∅?
• (c)Is L(G1 ) = L(R )?
• (d)Is L(G1 ) = ∅?

Which ONE of the following languages is accepted by a
deterministic pushdown automaton?

• (a)Any regular language.
• (b)Any context-free language.
• (c)Any language accepted by a non-deterministic pushdown automaton.
• (d)Any decidable language.

Consider the following context-free grammar G, where S,
A, and B are the variables (non-terminals), a and b are the
terminal symbols, S is the start variable, and the rules of
G are described as:
S → aaB | Abb
A → a | aA
B → b | bB
Which ONE of the languages L(G) is accepted by G?

• (a)L(G) = {a2bn | n ≥ 1} ∪ {anb2 | n ≥ 1}
• (b)L(G) = {anb2n | n ≥ 1} ∪ {a2nbn | n ≥ 1}
• (c)L(G) = {anbn | n ≥ 1}
• (d)L(G) = {a2nb2n | n ≥ 1}

Consider the following two languages over the alphabet
{a, b, c}, where m and n are natural numbers.
L1 = {ambmcm+n | m, n ≥ 1}
L2 = {ambncm+n | m, n ≥ 1}
Which ONE of the following statements is CORRECT?

THEORY OF COMPUTATION

• (a)A Both L1 and L2 are context-free languages.
• (b)L1 is a context-free language but L2 is not a context-free language.
• (c)L1 is not a context-free language but L2 is a context- free language..
• (d)Neither L1 nor L2 are context-free languages.

Consider a context-free grammar G with the following
3 rules.
S → aS, S → aSbS, S → c
Let w ∈ L(G). Let na (w), nb (w), nc (w) denote the
number of times a, b, c occur in w, respectively.
Which of the following statements is/are TRUE?

• (a)na(w) > nb(w)
• (b)na(w) > nc (w) - 2
• (c)nc(w) = nb(w) + 1
• (d)nc(w) = nb(w) * 2

Let G = (V, Σ, S, P) be a context-free grammar in
Chomsky Normal Form with Σ = {a, b, c} and V
containing 10 variable symbols including the start
symbol S. The string w = a30b30c 30 is derivable from S.
The number of steps (application of rules) in the
derivation S →* w is _________

Consider the pushdown automaton (PDA) P below,
which runs on the input alphabet {a, b}, has stack
alphabet {⊥, A}, and has three states {s, p, q}, with s
being the start state. A transition from state u to state v,
labelled c/X/γ, where c is an input symbol or , X is a
stack symbol, and γ is a string of stack symbols,
represents the fact that in state u, the PDA can read c
from the input, with X on the top of its stack, pop X from
the stack, push in the string γ on the stack, and go to state
v. In the initial configuration, the stack has only the
symbol ⊥ in it. The PDA accepts by empty stack.

Which one of the following options correctly describes the
language accepted by P?

• (a){ambn | 1<=m and n<m}
• (b){ambn | 0<=n<=m}
• (c){ambn | 0<=n and 0<=m}
• (d){am| 0<=m} U {bn | 0<=n}

Which of the following statements is/are CORRECT?

• (a)The intersection of two regular languages is regular.
• (b)The intersection of two context-free languages is context-free.
• (c)The intersection of two recursive languages is recursive.
• (d). The intersection of two recursively enumerable languages is recursively enumerable.

Consider the context-free grammar G below
S → aSb | X
X → aX | Xb | a | b ,
where S and X are non-terminals, and a and b are
terminal symbols. The starting non-terminal is S.
Which one of the following statements is CORRECT?

• (a)The language generated by G is (a + b)*
• (b)The language generated by G is a*(a + b)b*
• (c)The language generated by G is a*b*(a + b)
• (d)The language generated by G is not a regular language THEORY OF COMPUTATION

Consider the following languages:
L1 = {ww | w ∈ {a, b}* }
L2 = {anbncm | m, n≥ 0}
L3 = {ambncn | m, n≥ 0}
Which of the following statements is/are FALSE?

• (a)L1 is not context-free but L2 and L3 are deterministic context-free
• (b)Neither L1 nor L2 is context-free.
• (c)L2, L3, and L2 ∩ L3 all are context-free.
• (d)Neither L1 nor its complement is context-free.

Consider the following languages:
L1 = { anwan | w ∈ {a, b}* }
L2 = { wxwr | w, x ∈ {a, b}*, |w|, |x| > 0 }
Note that wr is the reversal of the string w. Which of
the following is/are TRUE?

• (a)L1 and L2 are regular.
• (b)L1 and L2 are context-free.
• (c)L1 is regular and L2 is context-free.
• (d)L1 and L2 are context-free but not regular.

For a string w, we define wR to be the reverse of w. For
example, if w= 01101 then wR= 10110. Which of the
following languages is/are context-free?

• (a){wxxRwR | w,x ∈ {0,1}*}
• (b){wxwR | w,x ∈ {0,1}*}
• (c){wxwRxR | w,x ∈ {0,1}*}
• (d){wwRxxR | w,x ∈ {0,1}*}

In a pushdown automaton P=(Q,Σ,Γ,δ,q0,F), a
transition of the form,

 where p, q∈Q, a ∈ Σ ∪ {ε}, X , Y ∈ Γ∪ {ε},
represents:(q,Y) ∈ δ(p,a,X)
Consider the following p ushdown automaton over the
input alphabet Σ={a,b} and stack alphabet Γ={#,A}.

 The number of strings of length 100 accepted by the above
pushdown automaton is ___________

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.

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}

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

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

Let L1, L2 be any two context-free languages and R be
any regular language.
Then which of the following is/are CORRECT?
I. L1 U L2is context free.
II. L̅1 is context-free
III. L1 – R is context – free.
IV. L1 ∩ L2 is context – free

• (a)I, II and IV only
• (b)I and III only
• (c)II and IV only
• (d)I only

Identify the language generated by the following
grammar, where S is the start variable.
S → XY
X → aX|a
Y → aYb|ε

• (a){ambn | m >= n, n > 0}
• (b){ambn | m >= n, n > =0}
• (c){ ambn | m > n, n > =0 }
• (d){ ambn | m > n, n > 0 }

Consider the following languages over the alphabet Σ =
{a, b, c}. Let L1 = {anbncm | m, n > 0} and L2 =
{ambncn | 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

Consider the following languages:
L1 = {ap│p is a prime number}
L2 = {anbmc2m | n ≥ 0, m ≥ 0}
L3 = {anbnc2n │ n ≥ 0}
L4 = {anbn │ n ≥ 1}
Which of the following are CORRECT?
I. L1 is context-free but not regular.
II. L2 is not context-free.
III. L3 is not context-free but recursive.
IV. L4 is deterministic context-free.

• (a)I, II and IV only
• (b)II and III only
• (c)I and IV only
• (d)III and IV only

Language L1 is defined by the grammar:
S1 → aS1b|ε
Language L2 is defined by the grammar:
S2 → abS2|ε
Consider the following statements:
P: L1 is regular
Q: L2 is regular
Which one of the following is TRUE?

• (a)Both P and Q are true
• (b)P is true and Q is false
• (c)P is false and Q is true
• (d)Both P and Q are false

Consider the following languages:
L1 = {anbmcn+m: m, n > 1}
L2 = {anbnc2n: n > 1}
Which one of the following is TRUE?

• (a)Both L1 and L2 are context-free.
• (b)L1 is context-free while L2 is not context-free.
• (c)L2 is context-free while L1 is not context-free.
• (d)Neither L1 nor L2 is context-free.

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 = {anbn | n>= 0} and is not accepted by any finite automata
• (b)L = {an| n >= 0} {anbn ∪ | n > =0} and is not accepted by any deterministic PDA.
• (c)L is not accepted by any Turning machine that halts on every input.
• (d)L = {an| n >= 0} {anbn ∪ | n > =0} and is deterministic context-free. THEORY OF COMPUTATION

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){ambn | m > 0 or n > 0} and {ambn | m > 0 and n > 0}
• (b){ambn | m > 0 and n > 0} and {ambn | m > 0 or n >= 0}
• (c){ambn | m >= 0 or n > 0} and {ambn| m > 0 and n > 0}
• (d){ambn | m >= 0 and n > 0} and {ambn | m > 0 or n > 0}

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

Consider the languages L1,L2 and L3 as given below:
L1 = { 0p 1q | p, q ∈ N },
L2 = { 0p 1q | p, q ∈ N and p = q } and
L3 = { 0p 1q 0r | p, q, r ∈ N and p = q = r }.
Which of the following statements is NOT TRUE?

• (a)Push Down Automate (PDA) can be used to recognize L1 and L2
• (b)L1 is a regular language
• (c)All the three languages are context free
• (d)Turing machines can be used to recognize all the languages

Consider the languages
L1 = {0 i1 j | i != j}.
L2 = {0 i1 j | i = j}.
L3 = {0 i1 j | i = 2j+1}.
L4 = {0 i1 j | 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.

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 PDA can be converted to an equivalent deterministic PDA.

S → aSa | bSb | a | b
The language generated by the above grammar over the
alphabet is the set of:

• (a)all palindromes
• (b)all odd length palindromes
• (c)strings that begin and end with the same symbol
• (d)all even length palindromes

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

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){ 0n102n|n≥1}
• (b){0i10j10k |i,j,k≥0}∪{ 0n102n|n≥0}
• (c){0i10j |i,j≥0}∪{ 0n102n|n≥0}
• (d)The set of all strings over {0,1} containing at least two 0's

Match the following:

E. Checking that
identifiers are
declared before
their use
P. L={ anbmcndm |n≥1,m≥1}
F. Number of formal
parameters in the
declaration of a
function agrees with
the number of actual
parameters in a use of
that function
Q. X→XbX | XcX | dXf | g
G. Arithmetic
expressions with
matched pairs of
parentheses
R. L={wcw|w∈ (a+b)* }
H. Palindromes
S. X→bXb | cXc | ε

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

Consider the following languages.
L1={ai b j ck | i =j, k>=1}
L2={ai b j | 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 U 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.

Consider the grammar given below:
S → x B | yA
A → x | xS | y A A
B → y | yS | x 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

The two grammars given below generate a language over
the alphabet {x,y,z}
G1: S → x | z | xS | zS | yB
B → y | z | yB |zB
G2: S →y | z | yS | zS | xB
B →y | yS
Which one of the following choices describes the
properties satisfied by the strings in these languages?

• (a)G1 : No y appears before any x G2 : Every x is followed by at least one y.
• (b)G1 : No y appears before any x G2 : No x appears before any y
• (c)G1 : No y appears after any x G2 : Every x is followed by at least one y
• (d)G1 : No y appears after any x G2 : Every y is followed by atleast one x

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

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

• (a)L1 only
• (b)L3 only
• (c)L1 and L2
• (d)L2 and L3

In the context-free grammar below, is the start symbol,
and 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*

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

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}
Which one of the following statements is true?

• (a)is recursively enumerable, but not recursive
• (b)is recursive, but not context-free
• (c)is context-free, but not regular
• (d)is regular

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

• (a){ anbncn | n≥0}
• (b){albmcn | l ≠ m or m≠n }
• (c){anbn | n>=0}
• (d){ambn m,n >=0}

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 accepeted by the PDA is

• (a). {albmcn | l=m=n }
• (b). {albmcn | l=m}
• (c). {albmcn | 2l=m+n}
• (d). {albmcn | m=n}

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

Consider the languages:
L1 = {anbncm | n, m > 0} and L2 = {anbmcm | n, m > 0},
Which one of the following statements is FALSE?

• (a)L1 ∩ L2 is a context-free language
• (b)L1 U 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

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
Lc U 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

The language {0n1n2n | 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

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 Σ*

Which one of the following statements is equivalent to the
following assertion?
Turing machine M decides the language L ⊆ {0,1}*.

• (a). Turing machine M halts on all input strings in {0,1}*
• (b). Turing machine M accepts all input strings in L
• (c). Turing machine M rejects all input strings in {0,1}* - L
• (d).Turing machine M accepts all input strings in L and rejects all input strings in {0,1}*-L

Which of the following is/are undecidable?

• (a)Given two Turing machines M1, and M2, decide if L(M1) = L(M2).
• (b)Given a Turing machine M, decide if L(M) is regular.
• (c)Given a Turing machine M, decide if M accepts all strings.
• (d)Given a Turing machine M, decide if M takes more than 1073 steps on every string.

Which of the following statements is/are TRUE?

• (a)Every subset of a recursively enumerable language is recursive.
• (b)If a language L and its complement I are both recursively enumerable, then L must be recursive.
• (c)Complement of a context-free language must be recursive.
• (d)If L1 and L2 are regular, then L1∩L2 must be deterministic context-free.

Let <M> denote an encoding of an automaton M. Suppose
that Σ = {0, 1}. Which of the following languages is/are
NOT recursive?

• (a)L= {<M>| M is a DFA such that L(M) = ∅}
• (b)L = {<M>| M is a DFA such that L(M) = Σ*}
• (c)L= {<M>| M is a PDA such that L(M) = ∅}
• (d)L = {<M>| M is a PDA such that L(M) = Σ*

Which of the following languages are undecidable? Note
that <M> indicates encoding of the Turing machine M.
L1 = <M> | L(M) = φ}
L2 = {<M, w, q>| M on input w reaches state q in exactly
100 steps}
L3 = {<M>|L(M) is not recursive}
L4 = {<M>|L(M) contains at least 21 members}?

• (a)L2 and L3 only
• (b)L1 and L3 only
• (c)L2, L3 and L4 only
• (d)L1, L3 and L4 only

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

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

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.

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

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  ∈  A*, always halts
with f(x) on its tape. Let Lf denote the language {x #
f(x)│x ∈ A* }. Which of the following statements is
true:

• (a)f is computable if and only if Lf is recursive.
• (b)f is computable if and only if Lf is recursively enumerable.
• (c)If f is computable then Lf is recursive, but not conversely.
• (d)If f is computable then Lf is recursively enumerable, but not conversely.

Consider the following types of languages:
L1: Regular
L2: Context-free
L3: Recursive
L4: Recursively enumerable.
Which of the following is/are TRUE?
I. L3' ∪ L4 is recursively enumerable .
II. L2' ∪ L3 is recursive .
III. L1* ∪ L2 is context-free .
IV. L1 ∪ L2' is context-free.

• (a)I only
• (b)I and III only
• (c)I and IV only
• (d)I, II and III only

Consider the following languages.
L1 = { ⟨M⟩ | M takes at least 2016 steps on some input },
L2 = { ⟨M⟩ | M takes at least 2016 steps on all inputs },
and
L3 = { ⟨M⟩ | M accepts ε },
Where for each Turing machine M, ⟨M⟩ denotes a specific
encoding of M.
Which one of the following is TRUE?

• (a)L1 is recursive and L2, L3 are not recursive
• (b)L2 is recursive and L1, L3 are not recursive
• (c)L1, L2 are recursive and L3 is not recursive
• (d)L1, L2, L3 are recursive

Consider the following statements.
I. The complement of every Turing decidable language is
Turing decidable
II. There exists some language which is in NP but is not
turing decidable
III. If L is a language in NP, L is turing decidable
Which of the above statements is/are true?

• (a)Only II
• (b)Only III
• (c)Only I and II
• (d)Only I and III THEORY OF COMPUTATION

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?
1. L1' (complement of L1) is recursive.

2. L2' (complement of L2) is recursive.
3. L1' is context-free.
4. L1' ∪ L2 is recursively enumerable.

• (a)I only
• (b)III only
• (c)III and IV only
• (d)I and IV only

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

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≤mB and B is recursive then A is recursive.
• (b)If A≤mB and A is undecidable then B is undecidable.
• (c)If A≤mB and B is recursively enumerable then A is recursively enumerable
• (d)If A≤mB and B is not recursively enumerable then A is not recursively enumerable

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

Which of the following is/are undecidable?
1. G is a CFG. Is L(G) = φ?
2. G is a CFG. Is L(G) = Σ*?
3. M is a Turing machine. Is L(M) regular?
4. A is a DFA and N is an NFA. Is L(A) = L(N)?

• (a)3 only
• (b)3 and 4 only
• (c)1, 2 and 3 only
• (d)2 and 3 only

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

Let L= L1 ∩ L2 , where L1 and L2 are languages as
defined below:
L1={ambmcnbn | m,n >=0}
L2={aibjck | i,j,k >=0}
Then is L

• (a)Not recursive
• (b)Regular
• (c)Context free but not regular
• (d)Recursively enumerable but not context free

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

Which of the following is true for the language
{ ap| p is 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

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

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

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

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 U L2 is context free
• (d)L1 ∩ L2 ∩ L3 is recursively enumerable

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)L1' is recursive and L2' is recursively enumerable
• (b)L1' is recursive and L2' is not recursively enumerable
• (c)L1' and L2' is recursively enumerable
• (d)L1' is recursively enumerable and L2' is recursive

Consider three decision problems P1, P2 and P3. It is
known that P1 is decidable and P2 is undecidable.

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