3 Jul 2003 23:59:51 -0400

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) |

From: | Xavier Nicollin <Xavier.Nicollin@imag.fr> |

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

Return to the
comp.compilers page.

Search the
comp.compilers archives again.