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