Theory of Automata MCQs with Answers
Practice important Theory of Automata MCQs with answers and explanations.
Chapter: 44
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
Correct Answer:
C
Chapter: 44
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
Correct Answer:
B
Chapter: 44
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
Correct Answer:
A
Chapter: 44
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
Correct Answer:
B
Chapter: 45
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)
Correct Answer:
D
Chapter: 45
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
Correct Answer:
B
Chapter: 45
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
Correct Answer:
C
Chapter: 45
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
Correct Answer:
A
Chapter: 45
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
Correct Answer:
B
Chapter: 45
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
Correct Answer:
C
Chapter: 45
Q571:
In the INSERT subprogram, what is the role of the marker Q?
A. To indicate the start of insertion
B. To replace a character with a blank
C. To mark the cell for the next character to be inserted
D. To terminate the insertion process
Correct Answer:
C
Chapter: 45
Q572:
In the given Turing machine example, what is the final TAPE content when the input string "aba" is processed?
A. aba
B. ab
C. bba
D. None of the above
Correct Answer:
A
Chapter: 45
Q573:
Which of the following is TRUE about a Turing machine's TAPE?
A. It is finite in length
B. It can move only to the right
C. The input string is placed on the TAPE and initially filled with blanks
D. It has a fixed number of cells
Correct Answer:
C
Chapter: 45
Q574:
What does the Turing machine's program consist of?
A. States and transitions between them
B. Operations on the TAPE only
C. Memory locations and their contents
D. Printing rules for characters only
Correct Answer:
A
Chapter: 45
Q575:
How does the INSERT subprogram affect the TAPE content?
A. It moves characters to the right and inserts a new character
B. It deletes characters and moves others to the left
C. It changes the characters in the cells
D. It replaces the entire TAPE with new content
Correct Answer:
A
Chapter: 45
Q576:
What happens when a Turing machine reaches a HALT state?
A. The machine accepts the input string
B. The TAPE Head moves to the left
C. The TAPE content is erased
D. The machine continues execution
Correct Answer:
B
Chapter: 45
Q577:
Which example illustrates the acceptance of a non-context-free language by a Turing machine?
A. The string "aaabbbaaa"
B. The language (a+b)b(a+b)*
C. The language defined by (a,a,R)
D. The language a^n b^n a^n
Correct Answer:
A
Chapter: 45
Q578:
What is the purpose of the TAPE Head’s movement in the INSERT subprogram?
A. To reposition the TAPE Head for insertion
B. To erase characters from the TAPE
C. To move the TAPE Head to the left only
D. To scan the entire TAPE for insertion
Correct Answer:
A
Chapter: 45
Q579:
When the DELETE subprogram is executed, what is the effect on characters to the right of the TAPE Head?
A. They are moved one cell left
B. They are replaced by blanks
C. They remain unchanged
D. They are moved one cell right
Correct Answer:
A