Theory of Automata MCQs with Answers
Practice important Theory of Automata MCQs with answers and explanations.
Multiple Choice Questions
Q541: A nonterminal is considered self-embedded if it occurs as a _______ in its own derivation tree.
- A: Parent
- B: Node
- C: Descendant
- D: Child
View Answer
C
Q542: Theorem states that if a CFG is in CNF with p live productions, every word of length more than 2p can be decomposed as _______.
- A: w = uvxyz
- B: w = uvwxy
- C: w = xyzw
- D: w = uvwz
View Answer
B
Q543: In the example CFG provided, what is the CFG in CNF for the language EVENA?
- A: S โ SS|aa, A โ a
- B: S โ a, A โ b
- C: S โ SS|bb, A โ a
- D: S โ a, A โ b
View Answer
A
Q544: A CFG in CNF can generate a word with more than 2p letters if it is decomposed into _______.
- A: uvxyz, where v and y are not both null.
- B: xyz, where y is null.
- C: uv, where x and z are both null.
- D: w, where v is null.
View Answer
A
Q545: The theorem on self-embedded nonterminals deals with a nonterminal that appears as a _______ of itself.
- A: Descendant
- B: Parent
- C: Sibling
- D: Child
View Answer
A
Q546: In the CFG for the language L={anbncn :n=1,2,3,โฆ}, the word a200b200c200 of length more than 2p shows that it _______.
- A: Satisfies the pumping lemma
- B: Does not satisfy the pumping lemma
- C: Satisfies regular language pumping lemma
- D: Can be decomposed into xyz
View Answer
B
Q547: The theory of Automata includes the study of which types of languages?
- A: Context-Free Languages and Non-Context-Free Languages
- B: Only Context-Free Languages
- C: Only Regular Languages
- D: Only Non-Context-Free Languages
View Answer
A
Q548: A CFG that has a production of the form nonterminal โ string of two nonterminals is called a _______ production.
- A: Live
- B: Dead
- C: Self Embedded
- D: Terminal
View Answer
A
Q549: In the given CFG example, the derivation tree for the word bbabbb shows that the word can be decomposed into _______.
- A: uvxyz, where u = a, v = ฮ, x = b, y = ab, z = ฮ
- B: w = uvxyz
- C: xyz
- D: uvx
View Answer
B
Q550: The CFG in CNF that generates the language {anbmanbm :m,n=1,2,3,โฆ} is checked using which version of the Pumping Lemma for CFLs?
- A: Second version
- B: First version
- C: Regular language version
- D: Non-context-free version
View Answer
A