Theory of Automata MCQs with Answers
Practice important Theory of Automata MCQs with answers and explanations.
Multiple Choice Questions
Q471: Which language is accepted by the nondeterministic PDA shown in the example?
- A: EVENPALINDROME={w reverse(w): w∈{a, b}*}
- B: {w : w is a palindrome}
- C: {w : w is a string of even length}
- D: {w : w is an odd length string}
View Answer
A
Q472: What does the PUSH state do in a PDA?
- A: Adds a character to the STACK
- B: Removes a character from the STACK
- C: Reads a character from the TAPE
- D: Moves to the REJECT state
View Answer
A
Q473: What is the role of the POP state in a PDA?
- A: Removes the top character from the STACK
- B: Adds a character to the STACK
- C: Reads a character from the TAPE
- D: Transitions to the REJECT state
View Answer
A
Q474: What does the REJECT state in a PDA signify?
- A: The string is rejected
- B: The string is accepted
- C: The machine is still running
- D: The machine has paused
View Answer
A
Q475: What does a nondeterministic PDA do if it encounters multiple edges with the same label at a READ state?
- A: Traces all possible paths
- B: Chooses one path at random
- C: Crashes
- D: Enters a loop
View Answer
A
Q476: In a PDA, what does the START state represent?
- A: The initial state of the machine
- B: The final state of the machine
- C: A state where input is read
- D: A state where the STACK is empty
View Answer
A
Q477: How does the PDA handle the null string in the example provided?
- A: It is accepted if only blank characters are left in the STACK
- B: It is rejected
- C: It is processed like any other string
- D: It cannot be processed
View Answer
A
Q478: What happens when the PDA reads an input letter that is not in the TAPE?
- A: The machine crashes and the string is rejected
- B: The machine accepts the string
- C: The machine ignores the letter
- D: The machine continues to read
View Answer
A
Q479: What is the purpose of the STACK in a PDA?
- A: To store characters for later use
- B: To read characters from the TAPE
- C: To initialize the machine
- D: To transition between states
View Answer
A
Q480: What does the theorem state about CFG and PDA?
- A: There exists a PDA for any CFG
- B: CFG cannot be converted to a PDA
- C: PDA can only handle regular languages
- D: CFG and PDA are unrelated
View Answer
A