Theory of Computation MCQ (Multiple Choice Questions) - SchoolingAxis

Theory of Computation MCQ (Multiple Choice Questions)

1. Halting states are of two types. They are:

a. Accept and Reject

b. Reject and Allow

c. Start and Reject

d. None of the mentioned


Ans- a. Accept and Reject


2. The production of the form A->B , where A and B are non terminals is called

a. Null production

b. Unit production

c. Greibach Normal Form

d. Chomsky Normal Form


Ans- b. Unit production


3. NPDA stands for:

a. Non-Deterministic Push Down Automata

b. Null-Push Down Automata

c. Nested Push Down Automata

d. All of the mentioned


Ans- a. Non-Deterministic Push Down Automata


4. The context free grammar which generates a Regular Language is termed as:

a. Context Regular Grammar

b. Regular Grammar

c. Context Sensitive Grammar

d. None of the mentioned


Ans- b. Regular Grammar


5. A null production can be referred to as:

a. String

b. Symbol

c. Word

d. All of the mentioned


Ans- a. String


6. A context free grammar can be recognized by:

a. Push down automata

b. 2 way linearly bounded automata

c. Both (a) and (b)

d. None of the mentioned


Ans- c. Both (a) and (b)


7. Which of the following automata takes queue as an auxiliary storage?

a. Finite automata

b. Push down automata

c. Turing machine

d. All of the mentioned


Ans- c. Turing machine


8. Which of the following automata takes stack as auxiliary storage?

a. Finite automata

b. Push down automata

c. Turing machine

d. All of the mentioned


Ans- b. Push down automata


9. The closure property of context free grammar includes :

a. Kleene

b. Concatenation

c. Union

d. All of the mentioned


Ans- d. All of the mentioned


10. A context free grammar is a _____

a. English grammar

b. Regular grammar

c. Context sensitive grammar

d. None of the mentioned


Ans- c. Context sensitive grammar

 

Previous Post Next Post

Responsive Ad