# Decidability of regular partition construction given its existence

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?