Which language is Context-Free but NOT accepted by any DPDA?
Without a middle marker 'c', a PDA must non-deterministically guess the midpoint of string w $w^R$. Thus it is CFL but not DCFL.
In a parse tree, what do the leaf nodes represent when read from left to right?
Reading the leaf nodes of a parse tree in left-to-right order produces the yield, which is the string of terminals generated by the derivation.
What is the relation between Regular Languages (RL), Deterministic Context-Free Languages (DCFL), Context-Free Languages (CFL), and Context-Sensitive Languages (CSL)?
The strict subset hierarchy holds: Regular Languages are a proper subset of DCFLs, which are a proper subset of CFLs, which are a proper subset of CSLs.
What operation allows constructing a DPDA for the complement of a language accepted by a DPDA by final state?
Complementing a DPDA requires ensuring the DPDA reads the full input (no infinite \epsilon -loops or deadlocks) and then flipping final/non-final states.
Which grammar format guarantees that no parse tree node has more than 2 children?
In CNF, productions are A->BC or A->a, ensuring every internal parse tree node has at most 2 child nodes (binary tree structure).