Theory of Automata MCQs with Answers
Practice important Theory of Automata MCQs with answers and explanations.
Multiple Choice Questions
Q561: Fill in the blank: In Algorithm 1, if no productions have the form S→Λ, we need to repeatedly _______ until no new nonterminal is eliminated.
- A: replace terminals
- B: add productions
- C: remove nonterminals
- D: replace nonterminals
View Answer
C
Q562: Fill in the blank: To determine whether a nonterminal X is used to generate some words, we need to find all _______ nonterminals.
- A: productive
- B: unproductive
- C: self-embedded
- D: useless
View Answer
B
Q563: What does the term "finiteness" refer to in context-free grammars?
- A: Whether the CFG generates a finite language
- B: Whether the CFG contains useless nonterminals
- C: Whether a CFG generates any word
- D: Whether the CFG can parse a string
View Answer
A
Q564: Fill in the blank: In Algorithm 2, if a nonterminal is painted blue, it indicates that it is _______ for generating words.
- A: unproductive
- B: productive
- C: useless
- D: self-embedded
View Answer
B
Q565: What does a Turing machine accept in addition to context-free languages (CFLs)?
- A: Finite automata (FAs)
- B: Linear bounded automata (LBAs)
- C: Regular languages
- D: Non-context-free languages (non-CFLs)
View Answer
D
Q566: What does the TAPE Head in a Turing machine do?
- A: Read contents of a cell and move left or right
- B: Print characters and move left or right
- C: Replace characters in cells only
- D: Move left without reading or writing
View Answer
B
Q567: Which of the following is NOT a component of a Turing machine?
- A: Finite set of states
- B: TAPE Head
- C: Memory stack
- D: Alphabet of input letters
View Answer
C
Q568: In a Turing machine, what is the function of a HALT state?
- A: To terminate the program when a condition is met
- B: To move the TAPE Head to the start of the TAPE
- C: To initiate the TAPE Head movement to the right
- D: To print a specific character on the TAPE
View Answer
A
Q569: What happens if a Turing machine encounters a situation with no outgoing edge for a read letter?
- A: The machine halts
- B: The machine crashes
- C: The machine moves to a default state
- D: The TAPE Head starts from the beginning of the TAPE
View Answer
B
Q570: What does the DELETE subprogram do in a Turing machine?
- A: Insert characters into the TAPE
- B: Move characters to the right
- C: Remove characters from the TAPE
- D: Replace characters with blanks
View Answer
C