Bihar STET – TOC Practice Test | Set 2

In CNF, a parse tree deriving a string of length n has a maximum height of n (when binary productions form a degenerate single path).

A binary parse tree in CNF with height h has at most $2^{h-1}$ leaf terminal nodes at the bottom level.

To avoid re-introducing unit productions or useless symbols, $\epsilon productions must be eliminated first, followed$ by unit productions, and finally useless symbols.

Standard left-recursion elimination converts left-recursive rules into right-recursive auxiliary rules A' using trailing RHS components $\alpha$.

Left factoring transforms rules A → $\alpha \beta 1 | \alpha \beta 2$ into A → $\alpha A'$ and A' → $\beta 1 | \beta 2, enabling 1-token lookahead selection$.