Theory of Computation Multiple Choice Questions and Answers

1 Which of the following conversion is not possible (algorithmically)?

A regular grammar to context-free grammar

B nondeterministic FSA to deterministic FSA

C nondeterministic PDA to deterministic PDA

D nondeterministic TM to deterministic TM

View Answer

Answer: nondeterministic PDA to deterministic PDA

2 Which one of the following statement is FALSE?

A context-free languages are closed under union

B context-free languages are closed under concatenation

C context-free languages are closed under intersection

D context-free languages are closed under Kleene closure

View Answer

Answer: context-free languages are closed under intersection

3 Which of the following regular expression identity is true?

A r(*) = r*

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

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

D r*s* = r* + s*

View Answer

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

4 R1 and R2 are regular sets. Which of the following is not true?

A R1 n R2 neet not be regular

B S* – R1 is regular

C R1 ? R2 is regular

D is regular

View Answer

Answer: R1 n R2 neet not be regular

5 Recursive languages are

A a proper superset of CFL

B always recognized by PDA

C are also called type 0 languages

D always recognized by FSA

View Answer

Answer: a proper superset of CFL

6 Which of the following problem is undecidable?

A membership problem for CFL

B membership problem for regular sets

C membership problem for CSL

D membership problem for type 0 languages

View Answer

Answer: membership problem for type 0 languages

7 Recursively enumerable languages are not closed under

A union

B homomorphism

C complementation

D concatenation

View Answer

Answer: complementation

8 Which of the following statement is wrong?

A Any regular language can be generated by a context-free grammar

B Some non-regular languages cannot be generated by any CFG

C the intersection of a CFL and regular set is a CFL

D All non-regular languages can be generated by CFGs.

View Answer

Answer: All non-regular languages can be generated by CFGs.

9 Consider the following statements

I. Recursive languages are closed under complementation

II. Recursively enumerable languages are closed under union

III. Recursively enumerable languages are closed under complementation

Which of the above statement are TRUE?

A I only

B I and II

C I and III

D II and III

View Answer

Answer: I and II

10 Consider a language L for which there exists a Turing machine ™, T, that accepts every word in L and either rejects or loops for every word that is not in L. The language L is

A NP hard

B NP complete

C recursive

D recursively enumerable

View Answer

Answer: recursively enumerable

11 Which of the following strings is not generated by the following grammar? S ? SaSbS|e

A aabb

B abab

C aababb

D aaabb

View Answer

Answer: aaabb

12 Consider the following right-linear grammar G = (N, T, P, S) N = {S}

P : S ? aS|aA T = {a, b}

A ? bA|b

Which of the following regular expression denotes L(G)?

A (a + b)*

B a(ab)*b

C aa*bb*

D a*b*

View Answer

Answer: aa*bb*

13 Which of the following is not primitive recursive but partially recursive?

A McCarthy’s function

B Riemann function

C Ackermann’s function

D Bounded function

View Answer

Answer: Ackermann’s function

14 A language is represented by a regular expression (a)*(a + ba). Which of the following string does not belong to the regular set represented by the above expression.

A aaa

B aba

C ababa

D aa

View Answer

Answer: ababa

15 Which of the following regular expressions denotes a language comprising of all possible strings over S = {a, b} of length n where n is a multiple of 3.

A (a + b + aa + bb + aba + bba)*

B (aaa + bbb)*

C ((a + b)(a + b)(a + b))*

D (aaa + ab + a) + (bbb + bb + a)

View Answer