Deterministic PDA vs Non-deterministic PDA MCQs

By: Prof. Dr. Fazal Rehman Shamil | Last updated: September 23, 2024

Deterministic PDA vs Non-deterministic PDA
Which of the following statements is true about Deterministic Pushdown Automata (DPDA) and Non-deterministic Pushdown Automata (NPDA)?

A) DPDA can accept all languages accepted by NPDA.
B) NPDA can accept all languages accepted by DPDA.
C) DPDA and NPDA accept exactly the same languages.
D) DPDA and NPDA cannot accept any context-free languages.
Answer: A

In a DPDA, for each state and input symbol, there can be at most how many transitions?

A) 0
B) 1
C) 2
D) Unlimited
Answer: B

An NPDA can have multiple transitions from a state on the same input symbol and stack symbol combination due to:

A) Its non-deterministic nature.
B) Its stack operations.
C) Its acceptance condition.
D) Its input alphabet.
Answer: A

Which of the following operations is not allowed in a DPDA?

A) Reading an input symbol.
B) Pushing a symbol onto the stack.
C) Popping a symbol from the stack.
D) Non-deterministically choosing a transition.
Answer: D

The stack of a DPDA is used to:

A) Store the input symbols.
B) Store the current state.
C) Implement a Last-In-First-Out (LIFO) structure.
D) Implement deterministic transitions.
Answer: C

Which of the following is true for NPDA compared to DPDA?

A) NPDA has more states.
B) NPDA has fewer transitions.
C) NPDA has non-deterministic transitions.
D) NPDA has a simpler acceptance condition.
Answer: C

The transition function of a DPDA is of the form:

A) δ: Q × Σ × Γ → Q × Γ*
B) δ: Q × Σ × Γ → P(Q × Γ*)
C) δ: Q × Σ × Γ → Q × Γ
D) δ: Q × Σ × Γ → Q
Answer: C

NPDA is more powerful than DPDA because:

A) NPDA can accept non-context-free languages.
B) NPDA has a simpler transition function.
C) NPDA always uses fewer states.
D) NPDA has a larger stack alphabet.
Answer: A

Which of the following properties is true for DPDA but not necessarily for NPDA?

A) Deterministic transitions.
B) Non-deterministic transitions.
C) Multiple final states.
D) Infinite stack capacity.
Answer: A

The acceptance of a string by a DPDA is based on:

A) Reaching a final state and emptying the stack.
B) Reaching a final state and having non-empty stack.
C) Reaching any state with an empty stack.
D) Reaching any state with a non-empty stack.
Answer: A

 

Related Posts: