Theory of Computation MCQ (Multiple Choice Questions) - SchoolingAxis

Theory of Computation MCQ (Multiple Choice Questions)

 1. Which of the following relates to Chomsky hierarchy?

a. Regular<CFL<CSL<Unrestricted

b. CFL<CSL<Unrestricted<Regular

c. CSL<Unrestricted<CF<Regular

d. None of the mentioned


Ans- a. Regular<CFL<CSL<Unrestricted


2. A language is accepted by a push down automata if it is:

a. regular

b. context free

c. both (a) and (b)

d. none of the mentioned


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


3. Let T={p, q, r, s, t}. The number of strings in S* of length 4 such that no symbols can be repeated.

a. 120

b. 625

c. 360

d. 36


Ans- b. 625


4. Which of the following is analogous to the following? :NFA and NPDA

a. Regular language and Context Free language

b. Regular language and Context Sensitive language

c. Context free language and Context Sensitive language

d. None of the mentioned


Ans- a. Regular language and Context Free language


5. Finite-state acceptors for the nested words can be:

a. nested word automata

b. push down automata

c. ndfa

d. none of the mentioned


Ans- a. nested word automata


6. Which of the following is a simulator for non deterministic automata?

a. JFLAP

b. Gedit

c. FAUTO

d. None of the mentioned


Ans- a. JFLAP


7. A language accepted by Deterministic Push down automata is closed under which of the following?

a. Complement

b. Union

c. Both (a) and (b)

d. None of the mentioned


Ans- a. Complement


8. If the PDA does not stop on an accepting state and the stack is not empty, the string is:

a. rejected

b. goes into loop forever

c. both (a) and (b)

d. none of the mentioned


Ans- a. rejected


9. A DPDA is a PDA in which:

a. No state p has two outgoing transitions

b. More than one state can have two or more outgoing transitions

c. Atleast one state has more than one transitions

d. None of the mentioned


Ans- a. No state p has two outgoing transitions


10. With reference of a DPDA, which among the following do we perform from the start state with an empty stack?

a. process the whole string

b. end in final state

c. end with an empty stack

d. all of the mentioned


Ans- d. all of the mentioned

Previous Post Next Post

Responsive Ad