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.
A.
a DFA with exactly one transition
B.
a PDA with no stack
C.
a restricted Turing machine whose tape is bounded by a linear function of input length
D.
a TM with infinite output symbols only
Show Answer
Correct Answer: C. a restricted Turing machine whose tape is bounded by a linear function of input length
Explanation:
In this course context, linear bounded automaton means a restricted Turing machine whose tape is bounded by a linear function of input length.
Choose an option to check your answer.
A.
a finite automaton with no memory
B.
a grammar that derives only epsilon
C.
a model of computation with states, tape, head, and transition rules
D.
a database administrator role
Show Answer
Correct Answer: C. a model of computation with states, tape, head, and transition rules
Explanation:
In this course context, Turing machine means a model of computation with states, tape, head, and transition rules.
Choose an option to check your answer.
A.
a state in which a Turing machine stops computation
B.
a state not allowed in TMs
C.
a state that forces infinite movement
D.
a grammar terminal
Show Answer
Correct Answer: A. a state in which a Turing machine stops computation
Explanation:
In this course context, halting state means a state in which a Turing machine stops computation.
Choose an option to check your answer.
A.
storing a DFA inside a stack only
B.
representing a Turing machine as a string over an alphabet
C.
turning a language into a hardware chip
D.
removing all input symbols
Show Answer
Correct Answer: B. representing a Turing machine as a string over an alphabet
Explanation:
In this course context, TM encoding means representing a Turing machine as a string over an alphabet.
Choose an option to check your answer.
A.
a TM with infinite output symbols only
B.
a DFA with exactly one transition
C.
a restricted Turing machine whose tape is bounded by a linear function of input length
D.
a PDA with no stack
Show Answer
Correct Answer: C. a restricted Turing machine whose tape is bounded by a linear function of input length
Explanation:
The suitable explanation is a restricted Turing machine whose tape is bounded by a linear function of input length.
Choose an option to check your answer.
A.
a model of computation with states, tape, head, and transition rules
B.
a database administrator role
C.
a finite automaton with no memory
D.
a grammar that derives only epsilon
Show Answer
Correct Answer: A. a model of computation with states, tape, head, and transition rules
Explanation:
The suitable explanation is a model of computation with states, tape, head, and transition rules.
Choose an option to check your answer.
A.
a state that forces infinite movement
B.
a grammar terminal
C.
a state in which a Turing machine stops computation
D.
a state not allowed in TMs
Show Answer
Correct Answer: C. a state in which a Turing machine stops computation
Explanation:
The suitable explanation is a state in which a Turing machine stops computation.
Choose an option to check your answer.
A.
representing a Turing machine as a string over an alphabet
B.
removing all input symbols
C.
turning a language into a hardware chip
D.
storing a DFA inside a stack only
Show Answer
Correct Answer: A. representing a Turing machine as a string over an alphabet
Explanation:
The suitable explanation is representing a Turing machine as a string over an alphabet.
Choose an option to check your answer.
A.
the classification of grammars and languages into regular, context-free, context-sensitive, and recursively enumerable classes
B.
a programming language syntax only
C.
a list of all compiler phases
D.
a method for database indexing
Show Answer
Correct Answer: A. the classification of grammars and languages into regular, context-free, context-sensitive, and recursively enumerable classes
Explanation:
The correct answer is the classification of grammars and languages into regular, context-free, context-sensitive, and recursively enumerable classes.
Choose an option to check your answer.
A.
a single finite state
B.
an unbounded storage medium divided into cells
C.
a fixed-size stack only
D.
a regular expression operator
Show Answer
Correct Answer: B. an unbounded storage medium divided into cells
Explanation:
The correct answer is an unbounded storage medium divided into cells.
Choose an option to check your answer.
A.
a simple abstract computing model related to Turing machine computation
B.
a special type of regular expression
C.
a finite automaton with output only
D.
a stack-only grammar
Show Answer
Correct Answer: A. a simple abstract computing model related to Turing machine computation
Explanation:
The correct answer is a simple abstract computing model related to Turing machine computation.
Choose an option to check your answer.
A.
the classification of grammars and languages into regular, context-free, context-sensitive, and recursively enumerable classes
B.
a method for database indexing
C.
a programming language syntax only
D.
a list of all compiler phases
Show Answer
Correct Answer: A. the classification of grammars and languages into regular, context-free, context-sensitive, and recursively enumerable classes
Explanation:
Chomsky hierarchy is correctly described as the classification of grammars and languages into regular, context-free, context-sensitive, and recursively enumerable classes.
