In a Deterministic Pushdown Automaton (DPDA), what constraint is placed on transition definitions $\delta (q, a, X)$ and $\delta (q, \epsilon , X)$?
A DPDA allows no choice of action: if an $\epsilon -move$ is possible for (q, X), no input-consuming transition $\delta (q, a, X) can be defined$.
What is the relationship between the class of Deterministic Context-Free Languages (DCFL) and Context-Free Languages (CFL)?
Languages like unmarked palindromes $L = { w w^R }$ are in CFL but strictly NOT in DCFL, proving DCFL ⊂ CFL.
Is the language L = { $a^n$ $b^n$ $c^m$ | n, m $\ge 1 } ∪ { a^n b^m c^m | n, m \ge 1 } a Deterministic Context-Free Language$?
A DPDA cannot decide whether to compare 'a's with 'b's or 'b's with 'c's upon reading initial 'a's without non-deterministic branching.
What class of languages is accepted by Pushdown Automata with a stack that allows PUSH and POP operations ONLY at the stack top?
Standard LIFO stack access (top-only push/pop) defines Pushdown Automata accepting Context-Free Languages.
In converting a CFG to an equivalent NPDA accepting by EMPTY STACK, how many control states are required in the constructed NPDA?
The standard top-down CFG-to-PDA reduction constructs a 1-state NPDA that simulates derivations directly on its stack.