Pushdown Automata MCQs

30 min Score: 0 Attempted: 0/30

1. What does a Pushdown Automaton (PDA) use in addition to finite states?
(A) Queue
(B) Tape
(C) Stack
(D) Register

2. Which class of languages can be recognized by a PDA?
(A) Context-free languages
(B) Regular languages
(C) Context-sensitive languages
(D) Recursively enumerable languages

3. What is the main function of the stack in a PDA?
(A) Store input symbols permanently
(B) Replace the input tape
(C) Count the number of states
(D) Help the automaton handle nested structures

4. How many stacks does a standard PDA have?
(A) Unlimited
(B) Two
(C) Three
(D) One

5. Which type of PDA accepts a language if it ends in a final state?
(A) PDA by final state
(B) PDA by empty stack
(C) Deterministic PDA
(D) Non-deterministic PDA

6. Which type of PDA accepts a language if the stack is empty?
(A) Deterministic PDA
(B) PDA by final state
(C) PDA by empty stack
(D) Non-deterministic PDA

7. Are all context-free languages recognized by deterministic PDAs?
(A) Yes
(B) Only regular languages
(C) No
(D) Only finite languages

8. Which PDA type can handle languages like {aⁿbⁿ | n ≥ 0}?
(A) Finite Automaton
(B) Deterministic PDA
(C) Turing Machine
(D) Non-deterministic PDA

9. Which of the following is an example of a deterministic PDA language?
(A) {wwᵣ | w ∈ {a, b}*}
(B) {aⁿbⁿcⁿ | n ≥ 0}
(C) {aⁿbⁿ | n ≥ 0}
(D) {aᵐbⁿ | m ≠ n}

10. What is the transition function of a PDA formally defined as?
(A) δ: Q × Σ → Q
(B) δ: Q × Σ × Γ → Q
(C) δ: Q × Σ × Γ → P(Q × Γ*)
(D) δ: Q × Σ × Γ → Γ*

11. In PDA notation, what does Γ represent?
(A) Input alphabet
(B) State set
(C) Stack alphabet
(D) Output symbols

12. What does non-determinism in PDA allow?
(A) Only one possible move per input
(B) No transitions at all
(C) Ignoring the stack
(D) Multiple possible moves from a state for the same input and stack symbol

13. Can a PDA recognize all regular languages?
(A) Only with two stacks
(B) No
(C) Only if non-deterministic
(D) Yes, because regular languages are a subset of context-free languages

14. Which of the following languages cannot be recognized by a single-stack PDA?
(A) {aⁿbⁿcⁿ | n ≥ 0}
(B) {aⁿbⁿ | n ≥ 0}
(C) {aᵐbⁿ | m, n ≥ 0}
(D) {aⁿbⁿ | n ≥ 1}

15. Which of the following is true about deterministic PDAs (DPDAs)?
(A) They can recognize all context-free languages
(B) They cannot recognize some context-free languages
(C) They can recognize all recursively enumerable languages
(D) They are equivalent to finite automata

16. In PDA, what happens when a symbol is popped from the stack?
(A) The symbol is removed from the top of the stack
(B) The symbol is copied to input
(C) The symbol is written to the output
(D) The symbol is pushed back immediately

17. Which formalism is equivalent in power to PDA?
(A) Turing Machine
(B) Finite automaton
(C) Linear bounded automaton
(D) Context-free grammar (CFG)

18. Can PDAs be used for parsing programming languages?
(A) No, they are only theoretical
(B) Only for undecidable languages
(C) Only for regular languages
(D) Yes, for languages with context-free grammar

19. What is the initial symbol of the stack in a PDA?
(A) ε (empty string)
(B) Input symbol
(C) Z₀ or bottom-of-stack marker
(D) Any alphabet symbol

20. How does a PDA process the input string?
(A) One symbol at a time, using state and stack for transitions
(B) Entire string at once
(C) Randomly
(D) Only by checking string length

21. Which of the following is an advantage of PDA over finite automata?
(A) Simpler design
(B) Faster execution
(C) Recognizes non-regular languages
(D) Smaller memory usage

22. Which operation is NOT part of PDA computation?
(A) Push
(B) Pop
(C) Read input symbol
(D) Multiply stack symbol

23. How many types of PDA acceptance are commonly defined?
(A) One
(B) Four
(C) Three
(D) Two (by final state and by empty stack)

24. Is every DPDA also a PDA?
(A) Only for regular languages
(B) No
(C) Yes, because DPDA is a special case of PDA
(D) Only if stack is empty

25. Which of the following is a non-deterministic PDA language?
(A) {aⁿbⁿ | n ≥ 0}
(B) {aᵐbⁿ | m, n ≥ 0}
(C) {aⁿbⁿcⁿ | n ≥ 0}
(D) {ε}

26. What is the stack used for in top-down parsing?
(A) Tracking grammar symbols to be expanded
(B) Storing input only
(C) Counting states
(D) Logging errors

27. Can a PDA have ε-transitions?
(A) Only for final states
(B) No
(C) Only in DPDA
(D) Yes, allowing transitions without consuming input

28. Which PDA component determines the next state?
(A) Stack top only
(B) Stack top, current state, and input symbol
(C) Current state and input symbol
(D) Input length only

29. What is the relation between CFGs and PDAs?
(A) CFGs are more powerful than PDAs
(B) Every CFG can be converted to an equivalent PDA
(C) PDAs cannot parse CFGs
(D) CFGs only represent regular languages

30. Which of the following is NOT true about PDA?
(A) PDA can recognize some non-regular languages
(B) DPDA cannot recognize all CFLs
(C) PDA always uses multiple stacks
(D) PDA uses a stack to handle nested structures

Leave a Comment Cancel reply