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. the component that reads, writes, and moves on the tape
Explanation:
TM head is correctly described as the component that reads, writes, and moves on the tape.
Choose an option to check your answer.
Correct Answer: D. a TM variant with more than one tape but equivalent in computational power to a standard TM
Explanation:
multi-tape Turing machine is correctly described as a TM variant with more than one tape but equivalent in computational power to a standard TM.
Choose an option to check your answer.
Correct Answer: C. a grammar that generates regular languages
Explanation:
In this course context, regular grammar means a grammar that generates regular languages.
Choose an option to check your answer.
Correct Answer: B. the component that reads, writes, and moves on the tape
Explanation:
In this course context, TM head means the component that reads, writes, and moves on the tape.
Choose an option to check your answer.
Correct Answer: A. a TM variant with more than one tape but equivalent in computational power to a standard TM
Explanation:
In this course context, multi-tape Turing machine means a TM variant with more than one tape but equivalent in computational power to a standard TM.
Choose an option to check your answer.
Correct Answer: C. a grammar that generates regular languages
Explanation:
The suitable explanation is a grammar that generates regular languages.
Choose an option to check your answer.
Correct Answer: A. the component that reads, writes, and moves on the tape
Explanation:
The suitable explanation is the component that reads, writes, and moves on the tape.
Choose an option to check your answer.
Correct Answer: C. a TM variant with more than one tape but equivalent in computational power to a standard TM
Explanation:
The suitable explanation is a TM variant with more than one tape but equivalent in computational power to a standard TM.
Choose an option to check your answer.
Correct Answer: A. a grammar type powerful enough to generate recursively enumerable languages
Explanation:
The correct answer is a grammar type powerful enough to generate recursively enumerable languages.
Choose an option to check your answer.
Correct Answer: A. an instruction based on current state and tape symbol that writes, moves, and changes state
Explanation:
The correct answer is 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:
The correct answer is a TM variant that may have multiple possible moves from a configuration.
Choose an option to check your answer.
Correct Answer: A. a language generated by a context-sensitive grammar
Explanation:
context-sensitive language is correctly described as a language generated by a context-sensitive grammar.
