Q.1 What is the primary feature that distinguishes a pushdown automaton (PDA) from a finite automaton?
The ability to move in multiple directions on the input tape
The use of a stack for memory
Acceptance by empty tape
The number of states
Explanation - A PDA differs from a finite automaton because it has a stack which allows it to recognize context-free languages, unlike finite automata which can only recognize regular languages.
Correct answer is: The use of a stack for memory
Q.2 Which class of languages is recognized by pushdown automata?
Regular languages
Context-free languages
Context-sensitive languages
Recursively enumerable languages
Explanation - Pushdown automata are specifically designed to recognize context-free languages, which are more powerful than regular languages but less powerful than context-sensitive languages.
Correct answer is: Context-free languages
Q.3 In a PDA, which operation is performed on the stack when a symbol is read from the input?
Push, pop, or no operation
Only push
Only pop
Reset stack
Explanation - A PDA can manipulate the stack in three ways for each input symbol: push a symbol, pop a symbol, or leave the stack unchanged.
Correct answer is: Push, pop, or no operation
Q.4 A PDA can accept input in which of the following ways?
By final state only
By empty stack only
By final state or empty stack
By counting input symbols
Explanation - Pushdown automata can accept strings either by reaching a final state or by emptying their stack, depending on the design of the PDA.
Correct answer is: By final state or empty stack
Q.5 Which of the following is true about deterministic PDA (DPDA)?
Every context-free language has a DPDA
DPDAs can recognize all context-free languages
DPDAs recognize a subset of context-free languages
DPDAs are equivalent to Turing machines
Explanation - Deterministic PDAs cannot recognize all context-free languages; they can only recognize deterministic context-free languages.
Correct answer is: DPDAs recognize a subset of context-free languages
Q.6 Which of the following languages can be recognized by a PDA?
{a^n b^n | n ≥ 0}
{a^n b^m | n, m ≥ 0}
{a^n b^n c^n | n ≥ 0}
{a^n b^n c^m | n, m ≥ 0}
Explanation - The language {a^n b^n | n ≥ 0} is a classic example of a context-free language recognized by a PDA. Languages like {a^n b^n c^n} require more than a single stack.
Correct answer is: {a^n b^n | n ≥ 0}
Q.7 What is the initial configuration of a PDA?
Initial state with an empty input
Initial state with an empty stack
Initial state with the first input symbol on the stack
Any arbitrary configuration
Explanation - A PDA begins computation in its initial state with an empty stack (or sometimes with a special bottom-of-stack symbol).
Correct answer is: Initial state with an empty stack
Q.8 Which of the following is NOT a component of a pushdown automaton?
Set of states
Input alphabet
Tape with read/write head
Stack alphabet
Explanation - PDAs do not use a tape with read/write heads; they use a stack in addition to states and input symbols.
Correct answer is: Tape with read/write head
Q.9 If a PDA accepts by empty stack, what happens when it finishes processing the input but the stack is not empty?
The input is accepted
The input is rejected
The PDA enters an infinite loop
The PDA ignores the remaining stack
Explanation - Acceptance by empty stack requires the stack to be empty at the end of the input; otherwise, the input is rejected.
Correct answer is: The input is rejected
Q.10 Which of the following languages cannot be accepted by any PDA?
{a^n b^n | n ≥ 0}
{a^n b^m | n, m ≥ 0}
{a^n b^n c^n | n ≥ 0}
{ε}
Explanation - Languages like {a^n b^n c^n} require two stacks to keep count and are therefore not context-free, making them unrecognizable by a PDA.
Correct answer is: {a^n b^n c^n | n ≥ 0}
Q.11 Which of the following best describes the transition function of a PDA?
δ: Q × Σ → Q
δ: Q × Σ × Γ → Q × Γ*
δ: Q × Σ × Γ → Q
δ: Q → Q × Σ
Explanation - The transition function of a PDA takes a state, an input symbol, and a stack symbol, and returns a new state and a string to replace the stack top.
Correct answer is: δ: Q × Σ × Γ → Q × Γ*
Q.12 Which of the following is an example of a deterministic context-free language?
{a^n b^n | n ≥ 0}
{a^n b^n c^n | n ≥ 0}
{ww^R | w ∈ {a,b}*}
{a^n b^m c^p | n = m or m = p}
Explanation - The language {a^n b^n | n ≥ 0} is deterministic context-free and can be recognized by a DPDA, whereas {a^n b^n c^n} cannot.
Correct answer is: {a^n b^n | n ≥ 0}
Q.13 Which operation on a PDA's stack corresponds to 'ε-transition'?
Pop without reading input
Push without reading input
Move to a new state without consuming input
All of the above
Explanation - An ε-transition in a PDA can involve popping or pushing a stack symbol or moving to a new state without consuming input, depending on the transition definition.
Correct answer is: All of the above
Q.14 Which of the following is true for nondeterministic PDAs?
They cannot accept context-free languages
They can explore multiple computational paths simultaneously
They are equivalent to finite automata
They require two stacks
Explanation - Nondeterministic PDAs can have multiple possible transitions for the same input symbol and stack symbol, allowing them to explore multiple paths simultaneously.
Correct answer is: They can explore multiple computational paths simultaneously
Q.15 Which of the following describes a PDA with no stack operations?
Equivalent to a DFA
Equivalent to a Turing machine
Equivalent to a NPDA
Not computationally meaningful
Explanation - If a PDA does not use its stack, it reduces to a finite automaton (DFA/NFA) that recognizes only regular languages.
Correct answer is: Equivalent to a DFA
Q.16 What is the stack alphabet in a PDA?
The set of input symbols
The set of symbols that can be pushed onto the stack
The set of states
The set of final states
Explanation - The stack alphabet Γ defines which symbols can be pushed or popped on the PDA's stack during computation.
Correct answer is: The set of symbols that can be pushed onto the stack
Q.17 Which of the following is a limitation of deterministic PDAs?
Cannot recognize any context-free language
Cannot recognize non-deterministic context-free languages
Cannot manipulate a stack
Cannot read input symbols
Explanation - Deterministic PDAs are limited to deterministic context-free languages and cannot recognize languages requiring non-determinism.
Correct answer is: Cannot recognize non-deterministic context-free languages
Q.18 How many stacks are required by a PDA to recognize {a^n b^n c^n | n ≥ 0}?
One stack
Two stacks
Three stacks
Zero stacks
Explanation - A single-stack PDA cannot recognize {a^n b^n c^n}. A PDA with two stacks is equivalent to a Turing machine and can recognize this language.
Correct answer is: Two stacks
Q.19 In PDA terminology, what does 'configuration' refer to?
The current state, remaining input, and stack contents
The final state only
The initial stack symbol
The set of all states
Explanation - A PDA configuration represents its instantaneous status: current state, unprocessed input, and current stack contents.
Correct answer is: The current state, remaining input, and stack contents
Q.20 Which of the following is true about the equivalence of context-free grammars (CFGs) and PDAs?
Every CFG can be converted to an equivalent PDA
Every PDA can be converted to an equivalent CFG
Both of the above
Neither of the above
Explanation - Every context-free grammar can be converted into an equivalent PDA and vice versa, demonstrating the equivalence of CFGs and PDAs.
Correct answer is: Both of the above
Q.21 What type of PDA is more powerful in recognizing languages?
Deterministic PDA
Non-deterministic PDA
Both are equally powerful
Neither can recognize context-free languages
Explanation - Non-deterministic PDAs can recognize all context-free languages, while deterministic PDAs can only recognize a subset.
Correct answer is: Non-deterministic PDA
Q.22 Which of the following is a valid stack operation in a PDA transition?
Push multiple symbols
Pop the top symbol
Leave the stack unchanged
All of the above
Explanation - A PDA can push one or more symbols, pop the top symbol, or leave the stack unchanged during a transition.
Correct answer is: All of the above
Q.23 If a PDA is nondeterministic, what is the implication for language acceptance?
The PDA must follow only one path
The PDA may accept if any computational path leads to acceptance
The PDA cannot accept any language
The PDA only accepts regular languages
Explanation - In a nondeterministic PDA, multiple paths are possible. If at least one path accepts the input, the PDA accepts the string.
Correct answer is: The PDA may accept if any computational path leads to acceptance
Q.24 Which of the following languages is context-free but not regular?
{a^n | n ≥ 0}
{a^n b^n | n ≥ 0}
{a^n b^m | n, m ≥ 0}
{ε}
Explanation - The language {a^n b^n} requires a stack to count symbols, making it context-free but not regular.
Correct answer is: {a^n b^n | n ≥ 0}
Q.25 Which component of a PDA ensures memory beyond finite states?
Input tape
Stack
Transition function
Final state
Explanation - The stack provides unbounded memory, allowing a PDA to recognize patterns that finite automata cannot.
Correct answer is: Stack