Consider the grammar S -> aSa | bSb | a | b | $\epsilon. What language does$ this grammar generate?
The rules S -> aSa | bSb | a | b | epsilon generate all even and odd length palindrome strings over the alphabet {a, b}.
A grammar G is ambiguous if there exists at least one string in L(G) that has:
Ambiguity is defined as the existence of more than one distinct parse tree (or leftmost/rightmost derivation) for at least one string in the language.
Eliminating immediate left recursion from rule A -> A alpha | beta yields which equivalent right-recursive rules?
Standard left-recursion removal replaces A -> A alpha | beta with A -> beta A' and A' -> alpha A' | epsilon.
Given grammar S -> A B, A -> a A | $\epsilon, B -> b B | \epsilon$. What is FIRST(S)?
FIRST(S) = FIRST(A). Since A can derive $\epsilon, FIRST(S) also includes FIRST(B)$. Thus FIRST(S) = {a, $\epsilon} U {b, \epsilon} = {a, b, \epsilon}$.
For the grammar S -> A b, A -> c | $\epsilon, what$ is FOLLOW(A)?
In rule S -> A b, symbol b immediately follows non-terminal A. Thus FOLLOW(A) = { b }.