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 language generated by a context-sensitive grammar
Explanation:
The suitable explanation is a language generated by a context-sensitive grammar.
Choose an option to check your answer.
Correct Answer: C. a grammar type powerful enough to generate recursively enumerable languages
Explanation:
The suitable explanation is 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:
The suitable explanation 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 suitable explanation is a TM variant that may have multiple possible moves from a configuration.
Choose an option to check your answer.
Correct Answer: B. a restricted Turing machine whose tape is bounded by a linear function of input length
Explanation:
The correct answer is a restricted Turing machine whose tape is bounded by a linear function of input length.
Choose an option to check your answer.
Correct Answer: C. a model of computation with states, tape, head, and transition rules
Explanation:
The correct answer is a model of computation with states, tape, head, and transition rules.
Choose an option to check your answer.
Correct Answer: C. a state in which a Turing machine stops computation
Explanation:
The correct answer is a state in which a Turing machine stops computation.
Choose an option to check your answer.
Correct Answer: C. representing a Turing machine as a string over an alphabet
Explanation:
The correct answer is representing a Turing machine as a string over an alphabet.
Choose an option to check your answer.
Correct Answer: A. a restricted Turing machine whose tape is bounded by a linear function of input length
Explanation:
linear bounded automaton is correctly described as a restricted Turing machine whose tape is bounded by a linear function of input length.
Choose an option to check your answer.
Correct Answer: B. a model of computation with states, tape, head, and transition rules
Explanation:
Turing machine is correctly described as a model of computation with states, tape, head, and transition rules.
Choose an option to check your answer.
Correct Answer: D. a state in which a Turing machine stops computation
Explanation:
halting state is correctly described as a state in which a Turing machine stops computation.
Choose an option to check your answer.
Correct Answer: B. representing a Turing machine as a string over an alphabet
Explanation:
TM encoding is correctly described as representing a Turing machine as a string over an alphabet.
