Let $G = (N,T,P,S)$ be a context-free grammar where $T,N$ are sets of terminals and nonterminals respectively, $P$ contains all the productions of the grammar, and $S \in N$.

If we know that $G$ is LL($k$) it is possible to construct a parser for $G$, since the construction of a LL($k$) parsing table is decidable, despite the problem of determining whether an arbitrary grammar is LL($k$) being undecidable. This is possible even if we don't know the exact value of $k$.

The problem of determining whether given arbitrary grammar is LL-regular is undecidable. Assume that we know that $G$ is LL-regular. Is the problem of constructing a regular partition $\pi$ for $G$ decidable?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.