SETHU INSTITUTE OF TECHNOLOGY

(An Autonomous Institution | Accredited by NAAC with ‘A’ Grade)

PULLOOR, KARIAPATTI – 626 115.
DEPATMENT OF COMPUTER SCIENCE & ENGINEERING

QUESTION BANK FOR CEAT EXAMINATIONS

Theory of Computation
Multiple choice questions (MCQ) – 1 Mark
1. 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) ScT (S is a subset of T) (b) TcS (T is a subset of S)
(c) S=T (d) SnT=Ø
2. Let L denotes the language generated by the grammar S – OSO/00. Which of the following is
true?
(a) L = O (b) L is regular but not O
(c) L is context free but not regular (d) L is not context free
3. 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) N^2 (b) 2^N (c) 2N (d) N!

4. The lexical analysis for a modern 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

5. Let P be a regular language and Q be context-free language such that Q ⊆ P. (For example, let P
be the language represented by the regular expression p*q* and Q be {p nqn|n ∈ N}). Then which
of the following is ALWAYS regular?
(A) P ∩ Q (B) P – Q (C) ∑* – P (D) ∑* – Q

6. Definition of a language L with alphabet {a} is given as following. L= { a nk | k > 0, and n is a

positive integer constant} What is the minimum number of states needed in a DFA to recognize
L?
(A) k+1 (B) n+1 (C) 2n+1 (D) 2k+1

7. 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*
8. 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.
9. Let L = L1 ∩ L2, where L1 and L2 are languages as defined below:
L1 = {ambmcanbn | m, n >= 0 }
L2 = {aibjck | i, j, k >= 0 }
Then L is
(A) Not recursive
(B) Regular
(C) Context free but not regular
(D) Recursively enumerable but not context free.

10. Which one of the following regular expression describes the language over {a, b} which consists
of no pair of consecutive b’s?
(A) (a*baa*)(b + epsilon)
(B) (a + ba)*(b + epsilon)
(C) (a*baa*)*(b + epsilon) + a*
(D) (a*ba*)*(b + epsilon) + a*(b + epsilon)
11. 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 pushdown automata
(C) Deterministic single-tape Turing machine and Non-deterministic single-tape Turing Machine
(D) Single-tape Turing machine and multi-tape Turing machine

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

13. Consider L= {(ap)* | P is a prime number} over the alphabet {a}, then what is the minimum
number of states in NFA that accepts the language L?
(A) three (B) five (C) two (D) four

14. Consider the Context free grammars over the alphabet {a, b} given below, where ‘S’ is non-
terminal
X:S= aSa |aSb |epsilon
Y:S= aaS |bbS |epsilon
What is the length of the shortest string which does not belongs to L(X) but belongs to L(Y)?

(A) three (B) four (C) one (D) six

(A) {wxwR | w,x ∈ (a+b)+}

15. Which one of the following language is Regular?

(B) {wxwR | w ∈ (a+b)*, x ∈ {a,b}}

(C) {wwRx | w,x ∈ (a+b)+}
(D) {wwR | w ∈ (a+b)*}
16. Let w be any string of length n in {a, b}*. Consider ‘L’ be the set of all strings ending with at
least n a’s. What is the minimum number of states in non deterministic finite automata that
accept ‘L’?
(A) (n+3) (B) (n+1) (C) n (D) 2n
17. Consider three decision problems X, Y, and Z. It is known that X is decidable and Y is
undecidable then which is the following is true?
(A) Z is decidable if X is reducible to Z
(B) Z is undecidable if Z is reducible to Y
 (C) Z is undecidable if Y is reducible to Z
(D) Z is decidable if Z i reducible to Y’s complement.
18. What is the length of the shortest string not in the language over alphabet {0, 1} for regular
expression given below:
1*(0 + 1)*1*
(A) three (B) five (C) six (D) four
19. Let ‘X’ be set of all languages accepted by deterministic push down automata (DPDA) by final
state and ‘Y’ be set of all languages accepted by DPDA by empty stack then, which of the
following is true?
(A) X is proper subset of Y
(B) X = Y
(C) X is proper super set of Y
(D) none of the above
20. Which two of the following four regular expressions are equivalent?\
(i) (00)∗(ε+0)(00)∗(ε+0)
(ii) (00)∗(00)∗
(iii) 0∗0∗
(iv) 0(00)∗
A. (i) and (ii) B. (ii) and (iii) C. (i) and (iii) D. (iii) and (iv)

I. If L1 ∪∪ L2 is regular, then both L1 and L2 must be regular.

21. Consider the following statements.

II. The class of regular languages is closed under infinite union.

Which of the above statements is/are TRUE?
A. I Only B. II Only C. Both I and II D. Neither I nor II

22. 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 ’s
C. The set of all string containing at least two ’s
D. The set of all strings that begin and end with either 0 or 1

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

24. 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 Σ * is uncountable
C. 2Σ* is uncountable and Σ * is countable
D. Both 2Σ* and Σ * are uncountable

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

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

27. Consider the following languages over the alphabet Σ = {0,1,c}

Here wr is the reverse of the string w. Which of these languages are deterministic Contextfree
languages?
A. None of the languages
B. Only L1
C. Only L1 and L2
D. All the three languages
28. 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*10*10*)*10*
C. ((0 + 1)*1(0 + 1)*1)*10*
D. (0*10*10*)*0*1

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

A. Suffix (L) = {y ∈ Σ* such that xy ∈ L}

30. If L is a regular language over Σ = {a,b}, which one of the following languages is NOT regular?

B. {wwR │w ∈ L}
C. Prefix (L) = {x ∈ Σ*│∃y ∈ Σ* such that xy ∈ L}
D. L ∙ LR = {xy │ x ∈ L, yR ∈ L}

A. {wwR |w ∈ {a,b}*}
31. Which one of the following languages over Σ = {a,b} is NOT context-free?

B. {wanwRbn |w ∈ {a,b}*, n ≥ 0}
C. {anbi | i ∈ {n, 3n, 5n}, n ≥ 0}
D. {wanbnwR |w ∈ {a,b}*, n ≥ 0}

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

34. What is the complement of the language accepted by the NFA shown below

A. ∅ B. {ε} C. a* D. {a ,ε}

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

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

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

38. 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*
39. 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?

(B) There exist x, y, ∈ L (G) such that xy ∉ L(G)

(A) G is not ambiguous

(C) There is a deterministic pushdown automaton that accepts L(G)

(D) We can find a deterministic finite state automaton that accepts L(G)

40. Let A ≤m B 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 B and A is undecidable then B is undecidable.
(C) If A ≤m B and 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.

41. Shift Reduce Parsers are ________________

A. Top down parser
B. Bottom up parser
C. May be top down or bottom up
D. None of the mentioned.

42. What is the similarity between LR,LALR and SLR?

A. Use same algorithm , but different parsing table.
B. Same parsing table, but different algorithm.
C. Their parsing table and algorithm are similar but uses top down approach
D. Both parsing tables and algorithm are different

43. Which one of the following is a top down parser?

A. Recursive Decent parser
B. Operator Precedence Parser
C. An LR(K) Parser
D. An LALR(K) Parser

44. In which parsing , the parser constructs the parse tree from the start symbol and transforms it in to
the input symbol.
A. Bottonm-up-Parsing
B. Top-Down parsing
C. None of the above
D. Both A and B

45. Which parser is most powerful in the following parsers?

A. Operator Precedence B. SLR C. Canonical LR D. LALR

46. Language L1 is defined by the grammar: S1→aS1b|εS1→aS1b|ε

Language L2 is defined by the grammar: S2→abS2|εS2→abS2|ε
Consider the following statements:
P: L1L1 is regular
Q: L2L2 is regular
Which one of the following is TRUE?
 A. P is false and Q is True
B. Both P and Q are True
C. P is True and Q is false.
D. Both P and Q are false.

47. Which one of the following regular expressions represents the language: the set of all binary
strings having two consecutive 0s0s and two consecutive 1s?
A. (0+1)*0011(0+1)*+(0+1)*1100()+1)*
B. (0+1)*())(0+1)*11+11()+1)*00)(0+1)*
C. (0+1)*00()+1)*+(0+1)*11(0+1)*
D. 00(0+1)*11+11(0+1)*00

48. The Lexical analysis for a modern computer language such as the java needs the power of Which
one of the following machine model in a necessary and sufficient sense?
A. Finite state automata
B. Deterministic push down automata
C. Non deterministic push down automata
D. Turing Machine
49. S→aSa|bSb|a|b
The language generated by the above grammar over the alphabet {a,b}{a,b} is the set of
A. All Palindromes
B. All odd Length Palindromes
C. Strings that begin and with same symbol
D. All even length palindromes

50. The language accepted by a pushdown Automation in which the stack is limited to 1010 items is best
described as
A. Context free
B. Regular
C. Deterministic Context free
D. Recursive

51. Which of the following statement is true?

A. The Union of two context free language is context free
B. If a language is context free it can be always accepted by push down automation
C. The intersection of two context free language is context free
D. The complement of a context free language is context free.

52. Context free language are closed under

A. Union,Kleen closure B. Union,Intersection
C. Intersection, complement D. Complement, Kleen closure

53. Consider the grammar with the following productions.

S→aαb|bαc|aBS→aαb|bαc|aB
S→αS|bS→αS|b
S→αbb|abS→αbb|ab
Sα→bdb|bSα→bdb|b
the above grammar is
A. Context free grammar B. Rgular Grammar
C. Context sensitive grammar D. LR(K)

54. State whether the following statement is TRUE / FALSE. The problem is to whether a Turing Machine
M accepts input ww is un-decidable.
A. True B. False
55. State whether the following statement is TRUE / FALSE.
The intersection of two CFL′s is also CFL.
A. True B. False

L = {x ∈∈ {a, b}* | number of a’s in x is divisible by 2 but not divisible by 3}

56. Consider the following language.

The minimum number of states in a DFA that accepts L is ______.

A. 6 B. 7 C. 3 D.4

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

58. Which of the following problems are decidable?

….1) Does a given program ever produce an output?
….2) If L is a context-free language, then is L’ (complement of L) also context-free?
….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 B. 1, 2, C. 2, 3, 4 D. 3, 4

59. Which of the following are decidable?

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
60. What can be said about a regular language L over {a} whose minimal finite state automaton has two
states?
A. L must be {an| n is odd}
B. L must be {an| n is even}
C. L must be {an| ³ O}
D. Either L must be {an | n is odd}, or L must be {a n | n is even}

Multiple choice questions (MCQ) – 2 Marks

1. Consider the following deterministic finite state automaton M.

Let S denote the set of seven bit binary strings the first, the fourth and the last bits are 1. Find the
number of strings in S that are accepted by M.
(A) 1 (B) 5 (C) 7 (D) 8
2. Consider the following finite automata PP and QQ over the alphabet {a,b,c}{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)L(P) and L(Q)L(Q) respectively.
 A. B.

C D.

3. Match all items in Group 1 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. Dataflow 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
(C) P-3, Q-4, R-1, S-2
(D) P-2, Q-1, R-4, S-3

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

Answer (D)

5. 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?

Answer (A)

6. Which of the following languages is/are regular?

A. L1 and L3 only
B. L1 only
C. L2 and L3only
D. L3 only
7. What is the minimum number of states in deterministic finite automata (DFA) for string starting
with ba2 and ending with ‘a’ over alphabet {a, b}?
A. Ten B. Nine C. Eight D. Six

8. What is the number of states in minimal NFA (non deterministic finite automata), which accepts set
of all strings in which the third last symbol is ‘a’ over alphabet {a, b}?
A. three B. four C. six D. five

9. 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 G1G1 and G2G2, 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 }

10. Which of the following languages is generated by the given grammar? S → aS|bS|ε

B. {w ∈ {a,b}* | w has equal number of a 's and b's}

A. {an bm | n,m ≥ 0}

C. {an | n ≥ 0} ∪ {bn | n ≥ 0} ∪ {an bn | n ≥ 0}

D. {a, b}∗

11. Define Languages L0L0 and L1L1 as follows

L0={<M,w,0>|ML0={<M,w,0>|M halts on w}w}
L1={<M,w,1>|ML1={<M,w,1>|M does not halts on w}w}
Here <M,w,i><M,w,i> is a triplet, whose first component, MM is an encoding of a Turing Machine,
second component, ww, is a string, and third component, t,t, is a bit.
Let L=L0∪L1. Which of the following is true?
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 recursive enumerable

12. For s∈(0+1)∗,s∈(0+1)∗, let d(s)d(s) denote the decimal value of s(e.g.d(101)=5)s(e.g.d(101)=5)
Let L={s∈(0+1)∗|d(s)L={s∈(0+1)∗|d(s) mod 5=25=2 and d(s)d(s) mod 7≠4}7≠4}Which of the
following statement is true?
A. L is recursively enumerable, but not recursive
B. B. L is recursive, but not context free
C. L is context free, but not regular
D. L is regular

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

 L = {an |n ≥ 0} ∪ {an bn|n ≥ 0} and is not accepted by any deterministic PDA
A. L = {an bn|n ≥ 0} and is not accepted by any finite automata
B.

L = {an |n ≥ 0} ∪ {an bn|n ≥ 0} and is deterministic context-free

C. L is not accepted by any Turing machine that halts on every input
D.

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

15. 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}

16. Consider the NPDA 〈Q = {q0, q1, q2}, Σ = {0, 1}, Γ = {0, 1, ⊥}, δ, q0, ⊥, F = {q2}〉, where (as per

transition function, q0 is the initial state, ⊥ is the initial stack symbol, and F is the set of accepting
usual convention) Q is the set of states, Σ is the input alphabet, Γ is stack alphabet, δ is the state

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

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

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.

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 (0+1)+ B. M does not halt on any string in (00+1) +
C. M halts on all string ending in a 0 D. M halts on all string ending in a

19. 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 grammars 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 statements 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

20. Consider the following problem X.X. Given a Turing machine MM over the input alphabet ∑,∑, any
state qq of MM And a word wε∑∗,wε∑∗, does the computation of MM on ww visit the state q′′q″
Which of the following statements about XX is correct?
A. X is decidable
B. X is undecidable but partially decidable
C. X is undecidable and not even partially decidable
D. X is not a decision problem

21. Which of the following languages are undecidable? Note that ⟨M⟩ indicates encoding of the Turing
machine M.
L1 = {⟨M⟩|L(M)=ϕ}{⟨M⟩|L(M)=ϕ}

L3 = { ⟨M⟩|⟨M⟩| L(M) is not recursive }

L2 = {⟨M,w,q⟩|{⟨M,w,q⟩| M on input w reaches state q in exactly 100 steps }

L4 = { ⟨M⟩|⟨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

L1 = {wxyx | w, x, y ∈ (0 + 1)+}
22. Consider the following languages.

L2 = {xy | x, y ∈ (a + b)*, |x| = |y|, x ≠ y}

Which one of the following is TRUE?
A. L1 is Regular and L2 is context- free
B. L1 is context free but not regular and L2 is context- free
C. Neither L1 nor L2 is Context free
D. L1 is context free but L2 is not context free

23. Consider the following statements.

I. The complement of every Turing decidable language is Turing decidable
II. There exists some language which is in NPNP but is not Turing decidable
III. If LL is a language in NP,NP, LL is Turing decidable
Which of the above statements is/are true?
A. Only I and II B. Only I and III C. Only II D. Only III

24. Let N be an NFA with nn states. Let k be the number of states of a minimal DFAwhich is equivalent
to N. Which one of the following is necessarily true?
A. K<2^n B. k<n^2 C. K>2^n D. K>2^n

25. Given a Turing Machine

M = ({q0,q1,q2,q3}, {a,b}, {a,b,B}, δ, B, {q3})
Where δ is a transition function defined as
δ(q0,a) = (q1,a,R)
δ(q1,b) = (q2,b,R)
δ(q2,a) = (q2,a,R)
δ(q2,b) = (q3,b,R)
The language L(M) accepted by the Turing Machine is given as:
A. aa*b B. abab C. aba*b D. aba*
26. 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)
A. Finite B. Not Finite but Regular
C. Context- free but not regular D. Recursive but not context free

27. 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 DD as the start symbol, and use six terminal symbols int ; id [ ] num.
Grammar G1 Grammar G2
D→intL D→int L;
L→ id[E L→id E
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

28. 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. L2∩L3 is recursively enumerable
C. L1 –L3 is Recursively enumerable D. L2∪L3is recursively enumerable

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

30. Match all items in Group 1 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. Dataflow 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 C. P-3, Q-4, R-1, S-2 D. P-2, Q-1, R-4, S-3

31. Let L = L1∩∩L2, where L1 and L2 are languages as defined below:

L1 ={am bm can bn | m, n ≥0}
L2 = {ai bj ck | i, j, k ≥ 0}
Then L is
A. Not recursive B. Regular
C. Context free but not regular D. Recursively enumerable but not context free.

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

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

34. Consider the following languages.

L1={0p1q0r|p,q,r≥0}
L2={0p1q0r|p,q,r≥0,p≠r}
Which one of the following statements is FALSE?
A. L2 is context-free. B. L1∩ L2 is context-free.
C. Complement of L2 is recursive. D. Complement of L1 is context-free but not regular.

35. Consider the languages L1=ΦL1=Φ and L2={a}L2={a}. Which one of the following
represents L1L∗2∪L∗1L1L2∗∪L1∗?
A. { ϵ } B. { Ø } C. {a*} D. { ϵ ,a}

36. 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}

37. Let T be the language represented by the regular expression Σ∗0011Σ∗ where Σ = {0, 1}. What is
the minimum number of states in a DFA that recognizes L’ (complement of L)?
A. 4 B. 5 C. 6 D. 8

38. Let δ denote the transition function and α denoted the extended transition function of the ε-NFA
whose transition table is given below:

Then, α (q2,aba) is
A. Ø B. {q1, q2, q3} C. {q0, q1, q2} D. {q0, q2, q3}
39. One of the following Regular Expressions is not the same as others. Which one?
A. (a* + b*a*)* B. (a*b* + b*a*)* (a*b*)*
C. ((ab)* + a*)* D. (a + b)* a*b*a*b*

40. Which of the following set can be recognized by DFA?

A. Numbers 1, 2, 4, 8, . . . 2n written in binary
B. Numbers 1, 3, 4, 8, . . . 2n written in unary
C. Set of binary strings in which number of zeroes is same as number of 1’s
D. Set {1, 101, 11011, 1110111, . . .}

Multiple Select questions (MSQ) – 2 Marks

1. Consider X and Y be any two Context sensitive languages and ‘R’ be any regular language.
Then which of the following is/are true?
A. X union of R is regular.
B. X intersection of Y is context sensitive.
C. Complement of Y is context sensitive language.
D. None.

2. Which of the following is decidable?

A. A Turing machine prints specific letter.
B. A Turing machine computes product of two numbers.
C. An arbitrary Turing machine halts after fifty steps.
D. none of the above.

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

“For every non-deterministic machine M1M1 there exists an equivalent deterministic
machine M2M2 recognizing the same language“.
A. M1 is nondeterministic finite automation
B. M1 is a nondeterministic PDA
C. M1 is a nondeterministic Turing machine
D. For no machine M1 use the above statement true

4. Context free languages and regular languages are both closed under the operation(s) of :
A. Union
B. Intersection
C. Concatenation
D. Complementation

5. Which of the following problems are un-decidable?

A. Membership problem in context-free language
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

6. It is decidable whether:
A. An arbitrary Turing machine halts after 10 steps
B. A turing machine prints a specific letter
C. A Turing machine computes the product of two numbers
D. None of the above

7. Which of the following regular expression identities are false?

A. (r+s)* =r* + s*
B. r*s* =r* + s*
C. r*=r*+s
D. (r*s*)*=(r+s)*

8. Which of the following statements are true?

A. Every left-recursive grammar can be converted to a right-recursive grammar and
vice-versa
B. All ε-productions can be removed from any context-free grammar by suitable
 transformations
C. The language generated by a context-free grammar all of whose productions are of the
form X→wX→w or X→wY (where, w is a string of terminals and Y is a non terminal), is
always regular
D. The derivation trees of strings generated by a context-free grammar in Chomsky
Normal Form are always binary trees.

9. Which one of the following regular expressions over {0,1} denotes the set of all strings not
containing 100 as substring?
A. 0*(1+0)*
B. 0*101
C. 0*(10+1)*
D. (1+01)*

10. Consider the DFA given.

Which of the following are FALSE?

A. Complement of L(A) is context-free.
B. L(A) = L((11*0+0)(0 + 1)*0*1*)
C. For the language accepted by A, A is the minimal DFA.
D. A accepts all strings over {0, 1} of length at least 2.

11. Consider the languages L1 = {0i1j | i != j}. L2 = {0i1j | i = j}. L3 = {0i1j | i = 2j+1}. L4 = {0i1j | i != 2j}.
A. Only L2 is context free
B. Only L2 and L3 are context free
C. Only L1 and L2 are context free
D. Only L2 is not context free
12. 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
A. I and II are undecidable
B. II and III are undecidable
C. III and Iv are undecidable
D. I and iv are undecidable

13. Which of the following problems are decidable?

A. If Lis a regular language then is L also regular
B. If L is a recursive language , then L also recursive.
 C.If L is a context free language, then is L also context free
D. does a given program ever produce a output.

14. Which of the following are decidable?

A. Whether the intersection of two regular languages is infinite
B. Whether a given context-free language is regular
C. Whether two push-down automata accept the same language
D. Whether a given grammar is context-free .

Let f : ∑ → ∑ be a polynomial time computable bijection such that (∀ x) [x ∈ L1 iff f(x) ∈ L2]. Further, let f-
15. Consider two languages L1 and L2 each on the alphabet ∑.

be also polynomial time computable. Which of the following CANNOT be true?

A. L1 is undecidable
B. L2 is decidable
C. L1 is recursive enumerable
D. L2 is Recursive
16. Which of the following is /are correct?
A. A language is context- free if and only if it is accepted by PDA
B. PDA is finite automata with push down stack
A. I is true.
B. II is true
C. I is false
D. II is false.
17. L = (an bn an | n = 1,2,3) is an example of a language that is______________
A . Context free
B. Not Context free
C. Not Context free but whose complement is CF
D. Not Context free.
18. Which of the following is/are undecidable?
A. G is a CFG. Is L(G)=Φ?
B. GG is a CFG. Is L(G)=∑∗?
C. M is a Turing Machine. Is L(M) regular?
D. A is a DFA and N is an NFA. Is L(A)=L(N)?

19. Given the language L = {ab, aa, baa}, which of the following strings are in L*?
A. abaabaaabaa
B. aaaabaaaa
C. baaaaabaaaab
D. baaaaabaa

20. Consider the following languages:

Which of the languages are context-free?
I. {ambncpdq|m+p=n+q,{ambncpdq|m+p=n+q, where m,n,p,q≥0}m,n,p,q≥0}
II. {ambncpdq|m=n{ambncpdq|m=n and p=q,p=q, where m,n,p,q≥0}m,n,p,q≥0}
III. {ambncpdq|m=n=p{ambncpdq|m=n=p and p≠q,p≠q, where m,n,p,q≥0}m,n,p,q≥0}
IV. {ambncpdq|mn=p+q,{ambncpdq|mn=p+q, where m,n,p,q≥0}m,n,p,q≥0}

Numerical answer type question – 2 Marks

1. Find the regular expression for the language recognized by the finite state automaton ______
Answer: 0*1*

L = {x ∈∈ {a, b}* | number of a’s in x is divisible by 2 but not divisible by 3}.The minimum
2. Consider the following language.

number of states in a DFA that accepts L is ______.

Answer: 6

3. Given a language L,𝐿, define LiLi as follows: L0={ε}L0={ε}, Li=Li−1. for

all i>0i>0.The order of a language LL 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 _____.

Answer: 2

4. The language accepted by a pushdown Automation in which the stack

is limited to10 items is best described as______
Answer: Deterministic Context free

5. 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-
state automation accepting L is____
Answer: 5

6. 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___________.
 Answer: 1
7. S→aSa|bSb|a|b
The language generated by the above grammar over the
alphabet {a,b} is the set of___
Answer: Strings that begin and with same symbol

8. S –> aSa| bSb| a| b ;The language generated by the above grammar over the alphabet {a,b} is the
set of ___________________
Answer : All odd length palindromes

9. How many minimum states are required in a DFA to find whether a given binary string has odd
number of 0's or not, there can be any number of 1's. ___________
Answer :2

10. 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 a deteninistic finite-state automaton (DFA) accepting L is
__________
Answer: 4

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

w2|≥3} is _________.
Answer: 8

12. Consider a language over ∑ ={a,b} such that all strings begin or end with “ab”. The number of states in minimal
DFA for this language will be ___________
Answer: 6

13. The set of all recursively enumerable languages is ________

Answer: Closed under intersection

14. __________ grammar gives multiple parse trees for the same string.
Answer: Ambiguous

15. A bottom up the parser generates ______

Answer: Right most derivation in reverse

16. Parsing is categorized in to ______ types.

Answer: Two types
17. There is a regular expression r = (11 + 111)* over Ʃ = {0, 1}. Then _____ and _____ are the number of states in minimal NFA and
DFA respectively.
Answer: 3 and 4
18. ______ of the following languages are context-free
L1 ={ambnanbm |m,n≥≥1}
L2 ={ambnambn|m,n ≥≥1}
L3 = {ambn|m = 2n+1}
Answer: L1 and L3

19. Consider the languages L1 = ϕ and L2 = {a}. _______ represents L1 L2* U L1*
Answer: { ε}
20. 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_____
Answer: 15