Which of the following languages is a classic example of an Inherently Ambiguous CFL?
L = { a^i $b^j$ c^k | i = j or j = k } is inherently ambiguous because strings where i = j = k always force overlapping derivations.
In a Pushdown Automaton, acceptance by Final State and acceptance by Empty Stack are:
For non-deterministic PDAs, acceptance by final state and acceptance by empty stack are equivalent; any NPDA of one type can be converted to the other.
Which decision problem is UNDECIDABLE for Context-Free Grammars?
Ambiguity of a CFG, equivalence of two CFGs, and universality (L(G)=$\Sigma *) are ALL undecidable problems$ for CFGs.
Which decision problem IS DECIDABLE for Context-Free Languages?
Emptiness, Finiteness, and Membership (via CYK) are DECIDABLE for CFLs.
What is the Pumping Lemma form for Context-Free Languages? Any string z ∈ L with |z| >= p can be written as z = u v w x y such that:
CFL pumping lemma splits string z into u v w x y where non-empty v and x (|vx| >= 1) can be pumped simultaneously within substring length |vwx| <= p.