Which of the following languages is NOT Context-Free?
L = { $a^n$ $b^n$ $c^n$ | n >= 0 } requires tracking counts for three separate symbols simultaneously, which exceeds PDA single-stack capability; it is Context-Sensitive.
Is the language L = { w w | w ∈ {a, b}* } Context-Free?
$L = { w w } (string repetition) requires cross-serial matching$ which a single stack cannot perform; hence it is not Context-Free.
What type of grammar rules are eliminated during grammar simplification before converting to CNF?
Grammar simplification removes null productions, unit productions, and useless symbols prior to CNF/GNF conversion.
Determinism in PDAs (DPDA) vs Non-determinism (NPDA): Which statement is TRUE?
Unlike Finite Automata, non-deterministic PDAs accept ALL CFLs, whereas DPDAs accept only Deterministic CFLs (DCFLs). Thus NPDA > DPDA.
Which of the following languages is accepted by a DPDA (Deterministic Pushdown Automaton)?
All three languages L1={$a^n$ $b^n}$, L2={w c $w^R}$ (with middle marker 'c'), and L3={$a^n$ $b^2n}$ can be deterministically parsed without guessing, making them DCFLs.