MCQ Computer Science

# Automata Theory Multiple Choice Quaestion & Answers (MCQs) set-19

1. Which of the following conversion is not feasible?
a) Regular expression to automaton conversion
b) Automaton to Regular Expression Conversion
c) NFA to DFA
d) None of the mentioned

Explanation: Each of the four formats of representation of the regular language be it, DFA, NFA, Regular Expression or e-NFA can be converted to the rest three forms.

2. Which of the following are decision properties?
a) Emptiness
b) Infiniteness
c) Membership
d) All of the mentioned

Explanation: Emptiness, Infiniteness and Membership are the decision properties of any language class. Example: Is the language L empty? Or Is w, a string belongs to the regular language L?
3. If L1 and L2 are context free languages, which of the following is context free?
a) L1*
b) L2UL1
c) L1.L2
d) All of the mentioned

Explanation: The following is a theorem which states the closure property of context free languages which includes Kleene operation, Union operation and Dot operation.

4. For the given Regular expression, the minimum number of variables including starting variable required to derive its grammar is:
(011+1)*(01)*
a) 4
b) 3
c) 5
d) 6

Explanation: The grammar can be written as:
S->BC
B->AB|e
A->011|1
C->DC|e
D->01

5. Is the following statement correct?
Statement: Recursive inference and derivation are equivalent.
a) Yes
b) No

Explanation: Yes, they are equivalent. Both the terminologies represent the two approaches of recursive inferencing.

6. If |w|>=2h, then its parse tree’s height is at least _____
a) h
b) h+1
c) h-1
d) 2h

Explanation: It is the basic implication of Parse tree theorem (assuming CNF). If the height of the parse tree is h, then |w| <=2h-1.

7. LALR in LALR parser stands for:
a) Left aligned left right parser
b) Look ahead left to right parser
c) Language Argument left to right parser
d) None of the mentioned

Explanation: LALR stands for Look ahead left to right parsers. It has more language recognition power than LR(0) parser.

8. State true or false:
Statement: BNF is a metasyntax used to express CFG
a) True
b) False

Explanation: BNF is a metasyntax used to express context free grammar, moreover a formal way to express the language.
9. 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

Explanation: Regular grammar is a subset of Context free grammar. The CFGs which produces a language for which a finite automaton can be created is called Regular grammar.

10. The following move of a PDA is on the basis of:
a) Present state
b) Input Symbol
c) Both (a) and (b)
d) None of the mentioned

Explanation: The next operation is performed by PDA considering three factors: present state,symbol on the top of the stack and the input symbol.

11. The instantaneous PDA is has the following elements
a) State
b) Unconsumed input
c) Stack content
d) All of the mentioned

Explanation: The instantaneous description of a PDA is represented by 3 tuple:
(q,w,s)
where q is the state, w is the unconsumed input and s is the stack content.

12. The transition a Push down automaton makes is additionally dependent upon the:
a) stack
b) input tape
c) terminals
d) none of the mentioned

Explanation: A PDA is a finite machine which has an additional stack storage. Its transitions are based not only on input and the correct state but also on the stack.

13. 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

Explanation: The chomsky hierarchy lays down the following order: Regular<CFL<CSL<Unrestricted

14. Context free grammar is called Type 2 grammar because of ______________ hierarchy.
a) Greibach
b) Backus
c) Chomsky
d) None of the mentioned

Explanation: Chomsky hierarchy decide four type of language :Type 3- Regular Language, Type 2-Context free language, Type 1-Context Sensitive Language, Type 0- Unrestricted or Recursively Ennumerable language.

15. There exists a Context free grammar such that:
X->aX
Which among the following is correct with respect to the given assertion?
a) Left Recursive Grammar
b) Right Recursive Grammar
c) Non Recursive Grammar
d) None of the mentioned