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

## Xavier Nicollin <Xavier.Nicollin@imag.fr>3 Jul 2003 23:59:51 -0400

From comp.compilers

Related articles
Why the characterisitic language of a CFG is regular? hajhossein81@yahoo.com (2003-07-02)
Re: Why the characterisitic language of a CFG is regular? Xavier.Nicollin@imag.fr (Xavier Nicollin) (2003-07-03)
| List of all articles for this month |

 From: Xavier Nicollin Newsgroups: comp.compilers Date: 3 Jul 2003 23:59:51 -0400 Organization: Institut IMAG, Grenoble References: 03-07-004 Keywords: parse Posted-Date: 03 Jul 2003 23:59:51 EDT

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

Post a followup to this message