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 grammar with no non-terminals
B.
a grammar equivalent to every DFA
C.
a grammar where the left side is always a terminal
D.
a grammar whose productions do not decrease string length, except limited start-symbol epsilon cases
Show Answer
Correct Answer: D. a grammar whose productions do not decrease string length, except limited start-symbol epsilon cases
Explanation:
The correct answer is a grammar whose productions do not decrease string length, except limited start-symbol epsilon cases.
Choose an option to check your answer.
A.
the start symbol of every grammar
B.
a grammar symbol that does not contribute to deriving terminal strings from the start symbol
C.
a terminal symbol in final strings only
D.
a symbol used in every derivation
Show Answer
Correct Answer: B. a grammar symbol that does not contribute to deriving terminal strings from the start symbol
Explanation:
useless symbol is correctly described as a grammar symbol that does not contribute to deriving terminal strings from the start symbol.
Choose an option to check your answer.
A.
a normal form for transaction schedules
B.
a finite automaton minimization rule
C.
a CFG form where productions begin with a terminal followed by zero or more non-terminals
D.
a form where productions begin with two terminals only
Show Answer
Correct Answer: C. a CFG form where productions begin with a terminal followed by zero or more non-terminals
Explanation:
Greibach Normal Form is correctly described as a CFG form where productions begin with a terminal followed by zero or more non-terminals.
Choose an option to check your answer.
A.
a grammar whose productions do not decrease string length, except limited start-symbol epsilon cases
B.
a grammar equivalent to every DFA
C.
a grammar with no non-terminals
D.
a grammar where the left side is always a terminal
Show Answer
Correct Answer: A. a grammar whose productions do not decrease string length, except limited start-symbol epsilon cases
Explanation:
context-sensitive grammar is correctly described as a grammar whose productions do not decrease string length, except limited start-symbol epsilon cases.
Choose an option to check your answer.
A.
the start symbol of every grammar
B.
a terminal symbol in final strings only
C.
a symbol used in every derivation
D.
a grammar symbol that does not contribute to deriving terminal strings from the start symbol
Show Answer
Correct Answer: D. a grammar symbol that does not contribute to deriving terminal strings from the start symbol
Explanation:
In this course context, useless symbol means a grammar symbol that does not contribute to deriving terminal strings from the start symbol.
Choose an option to check your answer.
A.
a form where productions begin with two terminals only
B.
a CFG form where productions begin with a terminal followed by zero or more non-terminals
C.
a finite automaton minimization rule
D.
a normal form for transaction schedules
Show Answer
Correct Answer: B. a CFG form where productions begin with a terminal followed by zero or more non-terminals
Explanation:
In this course context, Greibach Normal Form means a CFG form where productions begin with a terminal followed by zero or more non-terminals.
Choose an option to check your answer.
A.
a grammar with no non-terminals
B.
a grammar where the left side is always a terminal
C.
a grammar whose productions do not decrease string length, except limited start-symbol epsilon cases
D.
a grammar equivalent to every DFA
Show Answer
Correct Answer: C. a grammar whose productions do not decrease string length, except limited start-symbol epsilon cases
Explanation:
In this course context, context-sensitive grammar means a grammar whose productions do not decrease string length, except limited start-symbol epsilon cases.
Choose an option to check your answer.
A.
a terminal symbol in final strings only
B.
a symbol used in every derivation
C.
the start symbol of every grammar
D.
a grammar symbol that does not contribute to deriving terminal strings from the start symbol
Show Answer
Correct Answer: D. a grammar symbol that does not contribute to deriving terminal strings from the start symbol
Explanation:
The suitable explanation is a grammar symbol that does not contribute to deriving terminal strings from the start symbol.
Choose an option to check your answer.
A.
a finite automaton minimization rule
B.
a form where productions begin with two terminals only
C.
a normal form for transaction schedules
D.
a CFG form where productions begin with a terminal followed by zero or more non-terminals
Show Answer
Correct Answer: D. a CFG form where productions begin with a terminal followed by zero or more non-terminals
Explanation:
The suitable explanation is a CFG form where productions begin with a terminal followed by zero or more non-terminals.
Choose an option to check your answer.
A.
a grammar with no non-terminals
B.
a grammar where the left side is always a terminal
C.
a grammar whose productions do not decrease string length, except limited start-symbol epsilon cases
D.
a grammar equivalent to every DFA
Show Answer
Correct Answer: C. a grammar whose productions do not decrease string length, except limited start-symbol epsilon cases
Explanation:
The suitable explanation is a grammar whose productions do not decrease string length, except limited start-symbol epsilon cases.
Choose an option to check your answer.
A.
a transition that moves a TM left
B.
a production that derives the empty string
C.
a rule that rejects every string
D.
a production that always consumes input
Show Answer
Correct Answer: B. a production that derives the empty string
Explanation:
The correct answer is a production that derives the empty string.
Choose an option to check your answer.
A.
the process of complementing a language only
B.
the process of analyzing a string according to a grammar
C.
the process of adding more alphabets
D.
the process of converting memory into states
Show Answer
Correct Answer: B. the process of analyzing a string according to a grammar
Explanation:
The correct answer is the process of analyzing a string according to a grammar.
