Theory of Computation MCQ (Multiple Choice Questions) - SchoolingAxis

Theory of Computation MCQ (Multiple Choice Questions)

 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

Previous Post Next Post

Responsive Ad