Cheap and Secure Web Hosting Provider : See Now

# [Solved]: Lookahead set: Determining minimum $k$ such that $G$ is a strong $LL(k)$ grammar

, ,
Problem Detail:

How do we determine minimum $k$ such that $G$ is a strong $LL(k)$ Grammar

Like for grammar $G$ with the following rules $S\rightarrow aAcaa \mid bAbcc,A\rightarrow a \mid ab \mid \epsilon$

I do not believe one can obtain directly a minimum $k$ such that $G$ is a strong $LL(k)$ grammar. However, as it is possible to (dis)prove that a grammar is strong $LL(k)$, one can iterate the proof over $k$.

A grammar $G$ is strong $LL(k)$ iff for every pair of distinct production rules $A \to \alpha$ and $A \to \beta$ (with $\alpha \neq \beta$), we have:

$$First_k( \alpha \; Follow_k(A) ) \; \cap \; First_k( \beta \; Follow_k(A) ) = \emptyset$$

The steps to obtain a $k$ for a certain grammar $G$ are thus as follows:

• For each $n > 0$:
1. Check wether $G$ is $LL(n)$
2. If so, try proving $G$ is $LL(n)$
3. If not, we have found our $k = n - 1$

Some documents that might help with the actual proof: