# Theory of Computation MCQ (Multiple Choice Questions) - SchoolingAxis

1. Which of the theorem defines the existence of Parikhs theorem?

a. Parikh's theorem

b. Jacobi theorem

c. AF+BG theorem

d. None of the mentioned

Ans- a. Parikh's theorem

2. Which of the following statements are correct for a concept called inherent ambiguity in CFL?

a. Every CFG for L is ambiguous

b. Every CFG for L is unambiguous

c. Every CFG is also regular

d. None of the mentioned

Ans- a. Every CFG for L is ambiguous

3. The language accepted by Push down Automaton:

a. Recursive Language

b. Context free language

c. Linearly Bounded language

d. All of the mentioned

Ans- b. Context free language

4. If w belongs to L(G), for some CFG, then w has a parse tree, which defines the syntactic structure of w. w could be:

a. program

b. SQL-query

c. XML document

d. All of the mentioned

Ans- d. All of the mentioned

5. Which of the following is/are the suitable approaches for inferencing?

a. Recursive Inference

b. Derivations

c. Both Recursive Inference and Derivations

d. None of the mentioned

Ans- c. Both Recursive Inference and Derivations

6. Which of the following is not a notion of Context free grammars?

a. Recursive Inference

b. Derivations

c. Sentential forms

d. All of the mentioned

Ans- d. All of the mentioned

7. Which of the following statement is correct?

a. All Regular grammar are context free but not vice versa

b. All context free grammar are regular grammar but not vice versa

c. Regular grammar and context free grammar are the same entity

d. None of the mentioned

Ans- a. All Regular grammar are context free but not vice versa

8. Which of the following statement is false?

a. Context free language is the subset of context sensitive language

b. Regular language is the subset of context sensitive language

c. Recursively ennumerable language is the super set of regular language

d. Context sensitive language is a subset of context free language

Ans- d. Context sensitive language is a subset of context free language

9. Production Rule: aAb->agb belongs to which of the following category?

a. Regular Language

b. Context free Language

c. Context Sensitive Language

d. Recursively Ennumerable Language

Ans- c. Context Sensitive Language

10. The entity which generate Language is termed as:

a. Automata

b. Tokens

c. Grammar

d. Data

Ans- c. Grammar