1. What is the primary characteristic of a Pushdown Automaton (PDA)?
A) It has a finite number of states
B) It has a finite tape
C) It has a stack
D) It uses a Turing machine as a base
Answer: C) It has a stack
2. Which of the following languages can be recognized by a Pushdown Automaton?
A) Regular languages
B) Context-free languages
C) Context-sensitive languages
D) Recursive languages
Answer: B) Context-free languages
3. Which of the following is a true statement about a Pushdown Automaton (PDA)?
A) It can recognize only regular languages
B) It can recognize context-free languages
C) It requires a Turing machine for processing
D) It can only accept finite languages
Answer: B) It can recognize context-free languages
4. A Pushdown Automaton is a finite automaton with an additional component. What is it?
A) A stack
B) A tape
C) A queue
D) A counter
Answer: A) A stack
5. Which of the following is a feature of a Pushdown Automaton (PDA) that distinguishes it from a Finite State Automaton (FSA)?
A) It has a finite tape for storage
B) It uses a stack to store symbols
C) It can store an infinite amount of data
D) It uses a finite number of states to recognize languages
Answer: B) It uses a stack to store symbols
6. In a Pushdown Automaton, what happens when an input symbol is read?
A) The state changes based on the input and the top of the stack
B) The top of the stack is always popped
C) The automaton halts and no further operations are possible
D) The stack is never modified
Answer: A) The state changes based on the input and the top of the stack
7. What is the main difference between a Pushdown Automaton (PDA) and a Finite State Automaton (FSA)?
A) PDA uses a stack, while FSA does not
B) PDA uses a queue, while FSA uses a stack
C) PDA uses an infinite tape, while FSA uses a finite tape
D) PDA uses a finite number of states, while FSA uses an infinite number of states
Answer: A) PDA uses a stack, while FSA does not
8. Which of the following is a language that cannot be recognized by a Pushdown Automaton?
A) {a^n b^n | n ≥ 0}
B) {a^n b^n c^n | n ≥ 0}
C) {a^n | n ≥ 0}
D) {a^n b^n | n ≥ 0, n is even}
Answer: B) {a^n b^n c^n | n ≥ 0}
9. Which of the following describes the types of languages that a Pushdown Automaton (PDA) can recognize?
A) Regular languages only
B) Context-free languages only
C) Context-free and regular languages
D) Context-sensitive languages
Answer: B) Context-free languages only
10. Which of the following is a true statement about the transition function of a Pushdown Automaton (PDA)?
A) It maps an input symbol and the stack symbol to a new state
B) It maps only the input symbol to a new state
C) It maps an input symbol to a stack symbol
D) It maps a state to an input symbol
Answer: A) It maps an input symbol and the stack symbol to a new state
11. What is the role of the stack in a Pushdown Automaton (PDA)?
A) It is used to store the output of the computation
B) It holds input symbols that need to be processed
C) It stores intermediate symbols for context-free grammar recognition
D) It is used to store the program code
Answer: C) It stores intermediate symbols for context-free grammar recognition
12. Which of the following is true for the acceptance condition of a Pushdown Automaton?
A) The PDA accepts an input if the stack is empty after reading the input
B) The PDA accepts an input if the stack contains a specific symbol after reading the input
C) The PDA accepts an input if the input is entirely processed with no transitions left
D) The PDA does not have an acceptance condition
Answer: A) The PDA accepts an input if the stack is empty after reading the input
13. In a Pushdown Automaton, how is the stack used when recognizing the language {a^n b^n | n ≥ 0}?
A) The stack is used to store ‘a’ symbols, which are popped when ‘b’ symbols are read
B) The stack is used to store ‘b’ symbols, which are popped when ‘a’ symbols are read
C) The stack is used to store alternating ‘a’ and ‘b’ symbols
D) The stack is not required for this language
Answer: A) The stack is used to store ‘a’ symbols, which are popped when ‘b’ symbols are read
14. Which of the following describes the time complexity of a Pushdown Automaton (PDA) for a language of length n?
A) O(n)
B) O(log n)
C) O(n^2)
D) O(2^n)
Answer: A) O(n)
15. Which type of automaton is more powerful than a Pushdown Automaton?
A) Finite state automaton
B) Turing machine
C) Linear-bounded automaton
D) Nondeterministic finite automaton
Answer: B) Turing machine
16. Which of the following can be recognized by a non-deterministic Pushdown Automaton (NPDA) but not by a deterministic Pushdown Automaton (DPDA)?
A) {a^n b^n | n ≥ 0}
B) {a^n b^n c^n | n ≥ 0}
C) {a^n | n ≥ 0}
D) {a^n b^n | n is even}
Answer: B) {a^n b^n c^n | n ≥ 0}
17. A Pushdown Automaton is more powerful than a Finite State Automaton because:
A) It can recognize non-context-free languages
B) It can handle an infinite number of states
C) It uses a stack to store symbols for context-free languages
D) It can recognize Turing machines
Answer: C) It uses a stack to store symbols for context-free languages
18. What happens in a Pushdown Automaton when the input is empty but the stack is not empty?
A) The PDA halts and accepts the input
B) The PDA rejects the input
C) The PDA continues processing the input
D) The PDA enters a loop
Answer: B) The PDA rejects the input
19. Which of the following is true about a deterministic Pushdown Automaton (DPDA)?
A) It requires a non-deterministic choice to accept certain languages
B) It can accept all context-free languages
C) It cannot accept all context-free languages
D) It is the same as a Turing machine
Answer: C) It cannot accept all context-free languages
20. What is the main limitation of a deterministic Pushdown Automaton (DPDA)?
A) It cannot recognize context-sensitive languages
B) It cannot process infinite tapes
C) It cannot handle languages that require non-determinism
D) It cannot perform any stack operations
Answer: C) It cannot handle languages that require non-determinism