(A) Deterministic Push Down Automata (DPDA) and Non-deterministic Push Down Automata (NPDA)

(B) Deterministic Finite Automata (DFA) and Non-deterministic Finite Automata(NFA)

(C) Single tape turning machine and multi tape turning machine.

(D) Deterministic single tape turning machine and Non-Deterministic single tape turning machine

View Answer / Hide Answer

**ANSWER: Deterministic Push Down Automata (DPDA) and Non-deterministic Push Down Automata (NPDA)**

(A) Finiteness problem for FSA’s

(B) Membership problem for CFG’s

(C) Equivalence problem for FSA’s

(D) Ambiguity problem for CFG’s

View Answer / Hide Answer

**ANSWER: Ambiguity problem for CFG’s**

(A) Strings that begin and end with the same symbol

(B) All odd and even length palindromes

(C) All odd length palindromes

(D) All even length palindromes

View Answer / Hide Answer

**ANSWER: All odd length palindromes**

(A) π is NP-complete

(B) π is NP-hard but not NP-complete

(C) π is in NP but not NP-complete

(D) π is neither NP-hard nor in NP

View Answer / Hide Answer

**ANSWER: π is NP-complete**

(A) Q is NP-complete

(B) R is NP-complete

(C) Q is NP-hard

(D) R is NP-hard

View Answer / Hide Answer

**ANSWER: R is NP-complete**

(A) X2 ∩ X1 is recursively enumerable

(B) X2 ∪ X1 is recursively enumerable

(C) X2 – X1 is recursively enumerable

(D) X1 – X3 is recursively enumerable

View Answer / Hide Answer

**ANSWER: X1 – X3 is recursively enumerable**

(A) It is not regular but context free

(B) It is regular but not context free

(C) It is neither regular nor context free, but accepted by a turing machine

(D) It is not accepted by turing machine

View Answer / Hide Answer

**ANSWER: It is neither regular nor context free, but accepted by a turing machine**

(A) Infinite union of finite sets is regular

(B) The union of two non-regular set is not regular

(C) Every finite subset of a non-regular set is regular

(D) Every subset of a regular set is regular

View Answer / Hide Answer

**ANSWER: Every finite subset of a non-regular set is regular**

(A) All strings containing at least two 1’s

(B) All strings containing at least two 0’s

(C) All strings that begin and end with either 0’s or 1’s

(D) All strings containing the substring 00

View Answer / Hide Answer

**ANSWER: All strings containing at least two 0’s**

(A) NP-complete and in P respectively

(B) Undecidable and NP-complete

(C) Both NP-complete

(D) Both in P

View Answer / Hide Answer

**ANSWER: NP-complete and in P respectively**

(A) The intersection of two context free languages is context free

(B) A context free language can always be accepted by a deterministic push down automaton

(C) The union of two context free languages is context free

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

View Answer / Hide Answer

**ANSWER: The union of two context free languages is context free**

(A) 2k + 1

(B) k + 1

(C) 2n + 1

(D) n + 1

View Answer / Hide Answer

**ANSWER: n + 1**

(A) Regular

(B) Deterministic context free

(C) Context free

(D) Recursive

View Answer / Hide Answer

**ANSWER: Regular**

(A) L is not context free

(B) L is regular but not 0+

(C) L = 0+

(D) L is context free but not regular

View Answer / Hide Answer

**ANSWER: L is regular but not 0+**

(A) 0 + (0 + 10) *

(B) (0 +1) * 10 (0 + 1) *

(C) (1 * 0) * 1*

(D) None of the above

View Answer / Hide Answer

**ANSWER: None of the above**

(A) n

(B) 2n

(C) n + 1

(D) n - 1

View Answer / Hide Answer

**ANSWER: n + 1**

(A) End with 00

(B) End with 0

(C) Begin either with 0 or 1

(D) Contain the substring 00

View Answer / Hide Answer

**ANSWER: End with 00**

S1 – {0

S2 – {0

Which one of the following statements is correct?

(A) Both S1 and S2 are correct

(B) Only S2 is correct

(C) Only S1 is correct

(D) Neither S1 nor S2 is correct

View Answer / Hide Answer

**ANSWER: Only S1 is correct**

(A) L = {s ∈ (0+1)* I for every prefix s’ of s, I no(s’)-n1(s’) I ≤ 2}

(B) L = {s ∈ (0+1)* I no(s) mod 7 = n1(s) mod 5 = 0}

(C) L = {s ∈ (0+1)* I no(s) is a 3 digit prime}

(D) L = {s ∈ (0+1)* I no(s)-n1(s) I ≤ 4

View Answer / Hide Answer

**ANSWER: L = {s ∈ (0+1)* I no(s)-n1(s) I ≤ 4**

(A) In Chomsky Normal Form the derivative trees of strings generated by a context-free grammar are always binary trees

(B) If W is the string of a terminals and Y is a non-terminal, the language generated by a context free grammar, all of whose productions are of the form x->W or X->WY is always regular

(C) By using suitable transformation all ε-productions can be removed from any context-free grammar.

(D) Every left recursive grammar can be converted to a right recursive grammar and vice-versa

View Answer / Hide Answer

**ANSWER: If W is the string of a terminals and Y is a non-terminal, the language generated by a context free grammar, all of whose productions are of the form x->W or X->WY is always regular**

Let the initial state be A = 0 and B = 0. To take the machine to the state A = 0 and B = 1 with output = 1 the minimum length of input string required will be

(A) 2

(B) 7

(C) 4

(D) 3

View Answer / Hide Answer

**ANSWER: 3**

For questions 22 and 23 refer to the data given below:

The figure shown below is a finite state automaton

(A) b*ab*ab*ab*

(B) b*a(a+b)*

(C) b*ab*ab*

(D) (a+b)*

View Answer / Hide Answer

**ANSWER: b*a(a+b)***

(A) 1

(B) 2

(C) 3

(D) 4

View Answer / Hide Answer

**ANSWER: 2**

(A) P3 is decidable if P3 is reducible to compliment of P2

(B) P3 is decidable if P1 is reducible to P3

(C) P3 is undecidable if P1 is reducible to P3

(D) P3 is undecidable if P2 is reducible to P3

View Answer / Hide Answer

**ANSWER: P3 is undecidable if P2 is reducible to P3**

a. G is ambiguous

b. G produces all strings with equal number of a’s and b’s.

c. Deterministic PDA accepts G

Which of the following statement is true about G?

(A) a, b, c all are true

(B) Only and b are true

(C) Only b and c are true

(D) Only a is true

View Answer / Hide Answer

**ANSWER: a, b, c all are true**

(A) 5

(B) 7

(C) 9

(D) 11

View Answer / Hide Answer

**ANSWER: 9**

(A) 20 states

(B) 5 states

(C) 10 states

(D) 15 states

View Answer / Hide Answer

**ANSWER: 15 states**

α – Does G have an independent set of size IVI – 4?

β – Does G have an independent set of size 5?

The statement that holds true is

(A) α is NP-complete and β is in P

(B) α is in P and β is NP-complete

(C) Both α and β are NP-complete

(D) Both α and β are in P

View Answer / Hide Answer

**ANSWER: α is in P and β is NP-complete**

(A) 1

(B) 9

(C) 3

(D) 5

View Answer / Hide Answer

**ANSWER: 5**

(A) L must be either {a

(B) L must be {a

(C) L must be {a

(D) L must be {a

View Answer / Hide Answer

**ANSWER: L must be either {a ^{n} I n is odd} or {a^{n} I n is even}**

(A) Only DHAM3 is NP-hard

(B) Only SHAM3 is NP-hard

(C) Both SHAM3 and DHAM3 are NP-hard

(D) Neither SHAM3 nor DHAM3 is NP-hard

View Answer / Hide Answer

**ANSWER: Both SHAM3 and DHAM3 are NP-hard**

(A) It is context-free but not regular

(B) It is regular

(C) It is type-0 but not context-sensitive

(D) It is context-sensitive but not context-free

View Answer / Hide Answer

**ANSWER: It is regular**

P1: Does a given finite state machine accept a given string?

P2: Does a given context-free grammar generate an infinite number of strings?

The statement that holds true for P1 and P2 is

(A) Only P2 is decidable

(B) Only P1 is decidable

(C) Neither P1 nor P2 are decidable

(D) Both P1 and P2 are decidable

View Answer / Hide Answer

**ANSWER: Both P1 and P2 are decidable**

We have a turing machine M over the input alphabet ∑, any state q of M and a word W ∈ ∑*, does the computation of M on W visit the state q? The statement, which holds true

about X, is

(A) X is undecidable but partially decidable

(B) X is decidable

(C) X is not a decision problem

(D) X is undecidable and not even partially decidable.

View Answer / Hide Answer

**ANSWER: X is undecidable but partially decidable**

(A) Whenever the input sequence is 10 it outputs 00

(B) Whenever the input sequence is 11 it outputs 01

(C) It outputs the sum of the present and the previous bits of the input

(D) None of the above

View Answer / Hide Answer

**ANSWER: It outputs the sum of the present and the previous bits of the input**

(A) It is a regular language

(B) It is context-sensitive language

(C) It is context-free language

(D) It is parsable fully only by a turing machine

View Answer / Hide Answer

**ANSWER: It is context-free language**

(A) 5

(B) 4

(C) 3

(D) 2

View Answer / Hide Answer

**ANSWER: 4**

(A) 4

(B) 6

(C) 3

(D) 5

View Answer / Hide Answer

**ANSWER: 5**

(A) (r*s*)* = (r+s)*

(B) (r+s)* = r* + s*

(C) r*s* = r* + s*

(D) r(*) = r*

View Answer / Hide Answer

**ANSWER: (r*s*)* = (r+s)***

(A) n(n-1)/2

(B) n

(C) (n (n+1)/2) + 1

(D) n

View Answer / Hide Answer

**ANSWER: (n (n+1)/2) + 1**

(A) Set of all languages over ∑ accepted by turing machine

(B) Set of all regular languages over ∑

(C) Set of all strings over ∑

(D) Set of all languages over ∑

View Answer / Hide Answer

**ANSWER: Set of all languages over ∑**

(A) n+1

(B) n+2

(C) n

(D) 2n

View Answer / Hide Answer

**ANSWER: n+2**

(A) 10

(B) 01

(C) 101

(D) 110

View Answer / Hide Answer

**ANSWER: 10**

(A) The set {1, 101, 11011, 1110111, …….}

(B) The set of binary string in which the number of 0’s is same as the number of 1’s

(C) 1, 2, 4, 8……2

(D) 1, 2, 4, 8……2

View Answer / Hide Answer

**ANSWER: 1, 2, 4, 8……2 ^{n} ….. written in binary**

a. (00)*( ε+0)

b. (00)*

c. 0*

d. 0(00)*

The equivalent regular expression out of the four is

(A) b and c

(B) c and d

(C) a and b

(D) a and c

View Answer / Hide Answer

**ANSWER: a and c**

(A) Φ

(B) a*

(C) {ε}

(D) {ε, a}

View Answer / Hide Answer

**ANSWER: {ε}**

I) abaabaaabaa

II) aaaabaaaa

III) baaaaabaaaab

IV) baaaaabaa

The strings present in L* are

(A) I, II and IV

(B) I, II and III

(C) II, III and IV

(D) I, III and IV

View Answer / Hide Answer

**ANSWER: I, II and IV**

(A) It is a context free language

(B) It is a context sensitive language

(C) It is a regular language

(D) None of the above

View Answer / Hide Answer

**ANSWER: It is a context sensitive language**

(A) Recursive procedure Syntax

(B) Syntax of if-then-else statement

(C) Arbitrary length of variable names

(D) Variable declared before its use

View Answer / Hide Answer

**ANSWER: Variable declared before its use**

(A) These are closed under union, Kleene closure

(B) These are closed under complement, Kleene closure

(C) These are closed under union, intersection

(D) These are closed under intersection, complement

View Answer / Hide Answer

**ANSWER: These are closed under union, Kleene closure**

(51) S -> a α b I b a c I ab

S -> α S I b

S -> α bb I ab

S -> bdb I b

The grammar described above is

(A) Context free

(B) Context sensitive

(C) Regular

(D) LR(k)

View Answer / Hide Answer

**ANSWER: Context sensitive **

a. Regular expression I. Syntax analysis

b. Pushdown automata II Code generation

c. Dataflow analysis III Lexical analysis

d. Register allocation IV Code optimization

(A) a - III, b - IV, c - I, d - II

(B) a - IV, b - III, c - I, d - II

(C) a - III, b - I, c - IV, d - II

(D) a - II, b - III, c - IV, d - I

View Answer / Hide Answer

**ANSWER: a - III, b - I, c - IV, d - II**

(A) There exists an equivalent deterministic turing machine for every non-deterministic turing machine

(B) Turing decidable languages are closed under intersection and complementation

(C) Turing recognizable languages are closed under union and intersection

(D) Turing recognizable languages are closed under union and complementation

View Answer / Hide Answer

**ANSWER: Turing recognizable languages are closed under union and complementation**

(A) Finding bi-connected problem of a graph

(B) The graph colouring problem

(C) Hamiltonian circuit problem

(D) The 0/1 Knapsack problem

View Answer / Hide Answer

**ANSWER: Hamiltonian circuit problem**

(A) NP-hard = NP

(B) NP-complete ∩ P = Φ

(C) P=NP-complete

(D) NP-complete=NP

View Answer / Hide Answer

**ANSWER: NP-complete ∩ P = Φ**

**RE: Theory of Computation questions and answers -likitha (08/20/15)**- Can u please give breif descriptions to the problems

Solution along with the answer **RE: Theory of Computation questions and answers -kumarraj (05/22/15)**- thanking you so much......
**RE: Theory of Computation questions and answers -Preethi (02/12/15)**- answer for question 36 is 3 .
**RE: Theory of Computation questions and answers -Preethi (02/12/15)**- swapnil n+2is also correct becs it accepts dead state.since it's not given non deterministic.if mentioned then n+1 is correct.
**RE: Theory of Computation questions and answers -Preethi (02/12/15)**- ans. For question 29 is 7 and not 5
**RE: Theory of Computation questions and answers -Preethi (02/12/15)**- i think there is a mistake in question29.instead is S it should be either 0 or 1 according to the given diagram.
**RE: Theory of Computation questions and answers -swapnil (08/17/14)**- i think the answer of Question no. 42 is n+1 .....am i right ??