Re: Why the characterisitic language of a CFG is regular?

Hossein Hojjat wrote:


> I've seen in the most of the compiler texts that the viable prefixes of
> a CFG form a regular language.Then they attempt to build DFA/NFA for
> recognizing this language, but the don't give a proof or an intuition why
> this language is regular.Does anyone have an idea about the reason of this
> regularity?


This is because the grammar of viable prefixes is linear
(right-recursive).
For the CFG grammar G = (V, T, S, P) (V vocabulary, T terminals, N = V\T
nonterminals, S start symbol, P productions), the grammar of viable
prefixes
G' is:


G' = (V', T', P', S') with
    V' = V U { [X] | X \in N }
    T' = V (and thus N' = { [X] | X \in N })
    S' = [S]
    P' = { [X] -> alpha | X -> alpha beta \in P } U
              { [X] -> alpha [Y] | X -> alpha Y beta \in P }
with X, Y \in N and alpha, beta \in V*


G' is linear (right-recursive), so the langage of viable prefixes is
regular.


> Thanks


You're welcome!


--
| Xavier NICOLLIN (mailto:Xavier.Nicollin@imag.fr) -- INPG (ENSIMAG)
| VERIMAG -- Centre Equation -- 2, ave. de Vignate -- F-38610 Gières

Return to the comp.compilers page.
Search the comp.compilers archives again.