Theory of Automata MCQs with Answers
Practice important Theory of Automata MCQs with answers and explanations.
Chapter: 33
Q421:
In prefix notation, what is the first step of evaluating +3*4 5?
A. 3+4
B. 4*5
C. +3 4
D. 3*(4+5)
Correct Answer:
B
Chapter: 33
Q422:
What type of notation is used for the expression *+3 4 5?
A. Infix notation
B. Postfix notation
C. Prefix notation
D. Reverse Polish notation
Correct Answer:
C
Chapter: 33
Q423:
The expression ((3+4)*5) results in which value?
A. 20
B. 23
C. 35
D. 12
Correct Answer:
C
Chapter: 33
Q424:
What is the result of evaluating the prefix expression *+1 2 +3 4?
A. 35
B. 21
C. 45
D. 50
Correct Answer:
B
Chapter: 34
Q425:
What type of grammar allows multiple production trees for the same word?
A. Regular Grammar
B. Ambiguous Grammar
C. Unambiguous Grammar
D. Finite Grammar
Correct Answer:
B
Chapter: 34
Q426:
What type of grammar generates only one unique production tree per word?
A. Ambiguous Grammar
B. Regular Grammar
C. Unambiguous Grammar
D. Context-Free Grammar
Correct Answer:
C
Chapter: 34
Q427:
In a total language tree, the root of the tree is the ________.
A. Nonterminal symbol
B. Start symbol
C. Production rule
D. Terminal symbol
Correct Answer:
B
Chapter: 34
Q428:
What does a total language tree represent?
A. All possible productions
B. All possible languages
C. All working strings
D. All terminals and nonterminals
Correct Answer:
C
Chapter: 34
Q429:
What is a semiword in the context of CFGs?
A. A string of terminals
B. A string of nonterminals
C. A mix of terminals and one nonterminal
D. A string with only terminals
Correct Answer:
C
Chapter: 34
Q430:
Which form of CFG productions is used to generate regular languages?
A. Nonterminal → semiword
B. Nonterminal → word
C. Both forms
D. None
Correct Answer:
C
Chapter: 34
Q431:
What is the purpose of building a TG from a regular grammar?
A. To simplify productions
B. To generate an FA
C. To transition between states
D. To represent a CFG in graphical form
Correct Answer:
C
Chapter: 34
Q432:
Fill in the blank: A CFG is said to be a regular grammar if it generates a ________.
A. Finite language
B. Regular language
C. Context-free language
D. Ambiguous language
Correct Answer:
B
Chapter: 34
Q433:
Which CFG production rule corresponds to a semiword?
A. Nonterminal → terminal
B. Nonterminal → semiword
C. Nonterminal → nonterminal
D. Nonterminal → word
Correct Answer:
B
Chapter: 34
Q434:
What is the result of removing the production S → aaS from an ambiguous CFG?
A. Makes it finite
B. Removes ambiguity
C. Introduces ambiguity
D. Keeps it ambiguous
Correct Answer:
B
Chapter: 35
Q435:
What does a TG stand for in automata theory?
A. Transition Graph
B. Transition Gate
C. Transmission Gate
D. Transduction Graph
Correct Answer:
A
Chapter: 35
Q436:
What is the form of a null production in CFG?
A. nonterminal → terminal
B. terminal → terminal
C. nonterminal → Λ
D. Λ → nonterminal
Correct Answer:
C
Chapter: 35
Q437:
What is the definition of nullable production?
A. nonterminal → terminal
B. nonterminal → Λ
C. nonterminal → another nonterminal
D. nonterminal → terminal and Λ
Correct Answer:
B
Chapter: 35
Q438:
What is the purpose of Chomsky Normal Form (CNF)?
A. Simplify context-free grammars
B. Create context-sensitive grammars
C. Convert regular expressions
D. Generate infinite languages
Correct Answer:
A
Chapter: 35
Q439:
What is a unit production in CFG?
A. A production that generates a terminal
B. A production that generates a nonterminal
C. A production of the form nonterminal → one nonterminal
D. A production of the form nonterminal → terminal
Correct Answer:
C
Chapter: 35
Q440:
What is removed to convert a CFG without null production?
A. Nonterminals
B. Unit productions
C. Null productions
D. Nullable productions
Correct Answer:
C