MCQ Collection
Theory of Automata & Formal Languages MCQs
MCQs on automata theory, grammars, regular languages, and formal language concepts.
Choose an option to check your answer.
Correct Answer: D. a grammar type powerful enough to generate recursively enumerable languages
Explanation:
unrestricted grammar is correctly described as a grammar type powerful enough to generate recursively enumerable languages.
Choose an option to check your answer.
Correct Answer: B. an instruction based on current state and tape symbol that writes, moves, and changes state
Explanation:
TM transition is correctly described as an instruction based on current state and tape symbol that writes, moves, and changes state.
Choose an option to check your answer.
Correct Answer: A. a TM variant that may have multiple possible moves from a configuration
Explanation:
non-deterministic Turing machine is correctly described as a TM variant that may have multiple possible moves from a configuration.
Choose an option to check your answer.
Correct Answer: D. a language generated by a context-sensitive grammar
Explanation:
In this course context, context-sensitive language means a language generated by a context-sensitive grammar.
Choose an option to check your answer.
Correct Answer: B. a grammar type powerful enough to generate recursively enumerable languages
Explanation:
In this course context, unrestricted grammar means a grammar type powerful enough to generate recursively enumerable languages.
Choose an option to check your answer.
Correct Answer: D. an instruction based on current state and tape symbol that writes, moves, and changes state
Explanation:
In this course context, TM transition means an instruction based on current state and tape symbol that writes, moves, and changes state.
Choose an option to check your answer.
Correct Answer: C. a TM variant that may have multiple possible moves from a configuration
Explanation:
In this course context, non-deterministic Turing machine means a TM variant that may have multiple possible moves from a configuration.
Choose an option to check your answer.
Correct Answer: C. input is accepted when the PDA reaches an accepting state after processing input
Explanation:
The suitable explanation is input is accepted when the PDA reaches an accepting state after processing input.
Choose an option to check your answer.
Correct Answer: A. a production that derives the empty string
Explanation:
The suitable explanation is a production that derives the empty string.
Choose an option to check your answer.
Correct Answer: D. the process of analyzing a string according to a grammar
Explanation:
The suitable explanation is the process of analyzing a string according to a grammar.
Choose an option to check your answer.
Correct Answer: A. input is accepted when the stack becomes empty under the acceptance rules
Explanation:
The correct answer is input is accepted when the stack becomes empty under the acceptance rules.
Choose an option to check your answer.
Correct Answer: A. a production of the form A -> B where both are non-terminals
Explanation:
The correct answer is a production of the form A -> B where both are non-terminals.
