Theory of Automata MCQs with Answers
Practice important Theory of Automata MCQs with answers and explanations.
Chapter: 35
Q441:
What is the primary feature of Chomsky Normal Form in CFG?
A. All productions are of the form nonterminal → terminal
B. All productions are of the form nonterminal → nonterminal
C. All productions are either nonterminal → two nonterminals or nonterminal → terminal
D. All productions are of the form terminal → nonterminal
Correct Answer:
C
Chapter: 35
Q442:
Which of the following is not a method to remove null productions?
A. Deleting all null productions
B. Adding new productions
C. Removing nullable productions
D. Replacing nonterminals with terminals
Correct Answer:
D
Chapter: 35
Q443:
In CFG, a production of the form S → A, where A is a nonterminal, is called what?
A. Null production
B. Unit production
C. Nullable production
D. Nonunit production
Correct Answer:
B
Chapter: 36
Q444:
What is Chomsky Normal Form (CNF) for a CFG?
A. nonterminal → terminal
B. nonterminal → nonterminal
C. nonterminal → string of two nonterminals
D. nonterminal → one terminal or nonterminal → string of two nonterminals
Correct Answer:
D
Chapter: 36
Q445:
According to the theorem, what can be generated by a CFG in CNF?
A. Only null strings
B. Non-null strings of the CFL
C. Only regular languages
D. Infinite languages
Correct Answer:
B
Chapter: 36
Q446:
What must be done to convert a CFG to CNF?
A. Remove null productions and unit productions
B. Add more nullable productions
C. Introduce more terminals
D. Remove all nonterminals
Correct Answer:
A
Chapter: 36
Q447:
What is the purpose of introducing new nonterminals in CNF conversion?
A. To replace terminals with nonterminals
B. To simplify CFGs to CNF format
C. To remove all nonterminals
D. To create new terminals
Correct Answer:
B
Chapter: 36
Q448:
What type of derivation involves applying a production to the leftmost nonterminal?
A. Leftmost derivation
B. Rightmost derivation
C. Top-down derivation
D. Bottom-up derivation
Correct Answer:
A
Chapter: 36
Q449:
Which machine class corresponds to regular languages and CFGs?
A. Finite Automata (FA)
B. Pushdown Automata (PDA)
C. Turing Machines (TM)
D. Linear Bounded Automata (LBA)
Correct Answer:
A
Chapter: 36
Q450:
What is the new format of FAs used for?
A. Accepting regular languages
B. Accepting context-free languages
C. Accepting nonregular languages
D. Accepting context-sensitive languages
Correct Answer:
A
Chapter: 37
Q451:
What does the input TAPE of an FA accommodate?
A. Only strings of fixed length
B. All possible strings
C. Only binary strings
D. Only terminal symbols
Correct Answer:
B
Chapter: 37
Q452:
In an FA, what does the START state represent?
A. Final state
B. Initial state
C. Read state
D. Reject state
Correct Answer:
B
Chapter: 37
Q453:
How is the ACCEPT state represented in an FA?
A. By a filled circle
B. By an empty circle
C. By a square
D. By a diamond
Correct Answer:
A
Chapter: 37
Q454:
What does the REJECT state signify in an FA?
A. The process has ended successfully
B. The process has ended with an error
C. The machine is still running
D. The machine is paused
Correct Answer:
B
Chapter: 37
Q455:
In the new format of FA, what is a READ state used for?
A. To add a letter to the STACK
B. To remove a letter from the STACK
C. To read an input letter and lead to another state
D. To initialize the machine
Correct Answer:
C
Chapter: 37
Q456:
What is the function of the PUSH operation in a STACK?
A. To remove a letter from the STACK
B. To add a letter at the top of the STACK
C. To read a letter from the TAPE
D. To move to the next state
Correct Answer:
B
Chapter: 37
Q457:
How does the POP operation affect the STACK?
A. It adds a letter to the top
B. It removes the letter from the top
C. It replaces the letter at the top
D. It moves to the next state
Correct Answer:
B
Chapter: 37
Q458:
What is the effect of popping an empty STACK?
A. The machine halts
B. The machine crashes
C. It reads a blank character ∆
D. The machine continues to read
Correct Answer:
C
Chapter: 37
Q459:
What language does the FA with the format ∆ → REJECT, READ → a, b, ACCEPT recognize?
A. (a+b)bb(a+b)
B. (a+b)*a
C. (a+b)*b
D. (a+b)*ab
Correct Answer:
A
Chapter: 37
Q460:
In a PDA, what does the PUSH state do?
A. Removes the top letter from the STACK
B. Adds a letter to the top of the STACK
C. Reads a letter from the TAPE
D. Moves to a new state
Correct Answer:
B