How is an '$\epsilon -production' defined$ in a Context-Free Grammar?
$\Epsilon productions rewrite non-terminals$ into the empty string $\epsilon$.
In CFG simplification, what is a 'Nullable Non-terminal'?
Nullable non-terminals can expand to the empty string $\epsilon$.
What is the maximum number of production rules generated when converting a production rule A → X1 X2 X3 X4 (where Xi are non-terminals) into Chomsky Normal Form?
A non-terminal string of length $k = 4 splits$ into k - 1 = 3 CNF rules of length 2.
In Greibach Normal Form (GNF), can a production RHS contain two terminal symbols?
GNF strictly prohibits secondary terminals in production RHS.
What is the time complexity of checking if a string w of length n belongs to a Context-Free Language using a general Earley Parser?
Earley parsing handles general CFGs in O($n^3)$ time, reducing to O($n^2)$ for unambiguous grammars.