Headlines
Loading...
Theory of Computation MCQ (Multiple Choice Questions) - SchoolingAxis

Theory of Computation MCQ (Multiple Choice Questions) - SchoolingAxis

Theory of Computation MCQ (Multiple Choice Questions)

 1. Every Kuroda Normal form grammar generates _____

a. Context free grammar

b. Context sensitive grammar

c. Unrestricted grammar

d. None of the mentioned


Ans- b. Context sensitive grammar


2. There is a linear grammar that generates a context free grammar:

a. always

b. never

c. sometimes

d. none of the mentioned


Ans- c. sometimes


3. A_____ is context free grammar with atmost one non terminal in the right handside of the production.

a. linear grammar

b. linear bounded grammar

c. regular grammar

d. none of the mentioned


Ans- a. linear grammar


4. If L1 and L2 are context free languages, L1-L2 are context free:

a. always

b. sometimes

c. never

d. none of the mentioned


Ans- c. never


5. Which of the following is/are CFL not closed under?

a. Reverse

b. Homomorphism

c. Inverse Homomorphism

d. All of the mentioned


Ans- d. All of the mentioned


6. Using the pumping constant n, If there is a string in the language of length between __ and ___ then the language is infite else not.

a. n, 2n-1

b. 2n, n

c. n+1, 3n+6

d. 0, n+1


Ans- a. n, 2n-1


7. If the start symbol is one of those symbols which produce no terminal through any sequence, the CFL is said to be:

a. nullable

b. empty

c. eliminated

d. none of the mentioned


Ans- b. empty


8. Which of the following is incorrect? There exists algorithms to decide if:

a. String w is in CFL L

b. CFL L is empty

c. CFL L is infinite

d. All of the mentioned


Ans- d. All of the mentioned


9. Context free languages are not closed under:

a. Intersection

b. Intersection with Regular Language

c. Complement

d. All of the mentioned


Ans- d. All of the mentioned


10. The context free languages are closed under:

a. Intersection

b. Complement

c. Kleene

d. None of the mentioned


Ans- c. Kleene