Theory of Automata MCQs with Answers
Practice important Theory of Automata MCQs with answers and explanations.
Multiple Choice Questions
Q441: What is the primary feature of Chomsky Normal Form in CFG?
- A: All productions are of the form nonterminal → terminal
- B: All productions are of the form nonterminal → nonterminal
- C: All productions are either nonterminal → two nonterminals or nonterminal → terminal
- D: All productions are of the form terminal → nonterminal
View Answer
C
Q442: Which of the following is not a method to remove null productions?
- A: Deleting all null productions
- B: Adding new productions
- C: Removing nullable productions
- D: Replacing nonterminals with terminals
View Answer
D
Q443: In CFG, a production of the form S → A, where A is a nonterminal, is called what?
- A: Null production
- B: Unit production
- C: Nullable production
- D: Nonunit production
View Answer
B
Q444: What is Chomsky Normal Form (CNF) for a CFG?
- A: nonterminal → terminal
- B: nonterminal → nonterminal
- C: nonterminal → string of two nonterminals
- D: nonterminal → one terminal or nonterminal → string of two nonterminals
View Answer
D
Q445: According to the theorem, what can be generated by a CFG in CNF?
- A: Only null strings
- B: Non-null strings of the CFL
- C: Only regular languages
- D: Infinite languages
View Answer
B
Q446: What must be done to convert a CFG to CNF?
- A: Remove null productions and unit productions
- B: Add more nullable productions
- C: Introduce more terminals
- D: Remove all nonterminals
View Answer
A
Q447: What is the purpose of introducing new nonterminals in CNF conversion?
- A: To replace terminals with nonterminals
- B: To simplify CFGs to CNF format
- C: To remove all nonterminals
- D: To create new terminals
View Answer
B
Q448: What type of derivation involves applying a production to the leftmost nonterminal?
- A: Leftmost derivation
- B: Rightmost derivation
- C: Top-down derivation
- D: Bottom-up derivation
View Answer
A
Q449: Which machine class corresponds to regular languages and CFGs?
- A: Finite Automata (FA)
- B: Pushdown Automata (PDA)
- C: Turing Machines (TM)
- D: Linear Bounded Automata (LBA)
View Answer
A
Q450: What is the new format of FAs used for?
- A: Accepting regular languages
- B: Accepting context-free languages
- C: Accepting nonregular languages
- D: Accepting context-sensitive languages
View Answer
A