Are Deterministic Context-Free Languages (DCFL) closed under Complementation?
Unlike general CFLs, Deterministic CFLs (accepted by DPDA) are closed under complementation.
Are Deterministic Context-Free Languages (DCFL) closed under Union?
DCFLs are not closed under union or intersection.
What type of language is accepted by a Pushdown Automaton with a BOUNDED stack size of at most k symbols?
A stack bounded to maximum depth k has finite possible stack states (|Γ|^k), reducing the machine to a Finite Automaton (Regular Language).
Which language L = { w c $w^R$ | w ∈ {a, b}* } is recognized by a Deterministic Pushdown Automaton (DPDA)?
The explicit center marker 'c' allows a DPDA to deterministically switch from pushing 'w' to popping '$w^R$'.
Why is the language L = { w $w^R$ | w ∈ {a, b}* } NOT accepted by any Deterministic PDA (requires NPDA)?
Unmarked palindromes require non-deterministic branching to guess the string midpoint.