Theory of Automata MCQs with Answers
Practice important Theory of Automata MCQs with answers and explanations.
Chapter: 37
Q461:
What happens when the PDA reads the string aaabbb?
A. It is rejected
B. It is accepted after processing
C. It enters a loop
D. It crashes
Correct Answer:
B
Chapter: 37
Q462:
How does the PDA handle the null string?
A. It rejects it
B. It accepts it if only blank characters are left
C. It processes it like any other string
D. It cannot process it
Correct Answer:
B
Chapter: 37
Q463:
What does the new format of FAs include to accept context-free languages?
A. An enhanced input TAPE
B. A PUSHDOWN STACK
C. More states
D. Larger TAPE size
Correct Answer:
B
Chapter: 37
Q464:
In the example of a PDA processing the string aaabbb, what happens when the TAPE is empty and STACK contains only ∆?
A. The machine rejects the string
B. The machine accepts the string
C. The machine continues to process
D. The machine restarts
Correct Answer:
B
Chapter: 37
Q465:
What does a READ state in an FA do when processing the input string?
A. Reads an input letter and transitions to another state
B. Adds the letter to the STACK
C. Removes the top letter from the STACK
D. Rejects the input
Correct Answer:
A
Chapter: 37
Q466:
What operation is performed by the POP state in a PUSHDOWN STACK?
A. Adds a letter to the top
B. Removes a letter from the top
C. Reads a letter from the TAPE
D. Initializes the machine
Correct Answer:
B
Chapter: 37
Q467:
Which of the following describes the language accepted by the PDA with the format shown in the example?
A. {anbn : n = 0,1,2,...}
B. {a^nb^n : n > 0}
C. {a^nb^n : n < 0}
D. {anbm : n ≠ m}
Correct Answer:
A
Chapter: 38
Q468:
What language does the PDA with the table for running the string aaabbb accept?
A. {anbn : n=0,1,2,3,…}
B. {anbm : n ≠ m}
C. {anbm : n < m}
D. {anbm : n > m}
Correct Answer:
A
Chapter: 38
Q469:
In the PDA example for EVEN EVEN language, what does the PUSH X state do?
A. Adds X to the top of the STACK
B. Removes X from the STACK
C. Reads X from the TAPE
D. Moves to the REJECT state
Correct Answer:
A
Chapter: 38
Q470:
What does the READ state in a nondeterministic PDA do?
A. Reads the next letter from the TAPE
B. Pops a letter from the STACK
C. Adds a letter to the STACK
D. Transitions to the ACCEPT state
Correct Answer:
A
Chapter: 38
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}
Correct Answer:
A
Chapter: 38
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
Correct Answer:
A
Chapter: 38
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
Correct Answer:
A
Chapter: 38
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
Correct Answer:
A
Chapter: 38
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
Correct Answer:
A
Chapter: 38
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
Correct Answer:
A
Chapter: 38
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
Correct Answer:
A
Chapter: 38
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
Correct Answer:
A
Chapter: 38
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
Correct Answer:
A
Chapter: 39
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
Correct Answer:
A