What is the result of converting a grammar with production S -> S a | b into an equivalent non-left-recursive grammar?
Left recursion elimination converts S -> S a | b into S -> b S' and S' -> a S' | $\epsilon$. Notice that both generate the language b a*.
Which rule removal must be performed FIRST when simplifying a Context-Free Grammar?
Standard CFG simplification order is: 1. Eliminate Null productions, 2. Eliminate Unit productions, 3. Eliminate Useless symbols.
Is the language L = { a^i $b^j$ c^k | i < j < k } Context-Free?
Simultaneously maintaining strict inequalities i < j < k across three distinct symbol counts requires two comparisons, violating CFL pumping lemma.
What is the yield of a parse tree containing a single node S -> $\epsilon$?
Expanding S to \epsilon produces an empty terminal string \epsilon as the yield.
If L is a Context-Free Language and R is a Regular Language, which of the following is Context-Free?
Since R is regular, L ∪ R is CFL, L ∩ R is CFL, and L - R = L ∩ R' is also CFL.