21 Oct 2004 22:20:05 -0400

Related articles |
---|

Why Chomsky Type 3 grammars are called "Regular"? spam@abelectron.com (valentin tihomirov) (2004-10-17) |

Re: Why Chomsky Type 3 grammars are called "Regular"? mefrill@yandex.ru (2004-10-21) |

Re: Why Chomsky Type 3 grammars are called "Regular"? torbenm@diku.dk (2004-10-21) |

Re: Why Chomsky Type 3 grammars are called "Regular"? dev@gioelebarabucci.com (Gioele Barabucci) (2004-10-23) |

Re: Why Chomsky Type 3 grammars are called "Regular"? spam@abelectron.com (valentin tihomirov) (2004-11-28) |

Re: Why Chomsky Type 3 grammars are called "Regular"? torbenm@diku.dk (2004-12-01) |

Re: Why Chomsky Type 3 grammars are called "Regular"? spam@abelectron.com (valentin tihomirov) (2004-12-05) |

Re: Why Chomsky Type 3 grammars are called "Regular"? henry@spsystems.net (2004-12-11) |

From: | torbenm@diku.dk (Torben Ęgidius Mogensen) |

Newsgroups: | comp.compilers |

Date: | 21 Oct 2004 22:20:05 -0400 |

Organization: | Department of Computer Science, University of Copenhagen |

References: | 04-10-111 |

Keywords: | parse, theory |

Posted-Date: | 21 Oct 2004 22:20:05 EDT |

"valentin tihomirov" <spam@abelectron.com> writes:

*> The context free grammars written using RegExps in their rules are called*

*> extended CF grammars or regular right part grammars. Why the Type 3 grammars*

*> expropriate the RE definition, what does the "regular" mean?*

Chomsky type 3 grammars can describe the same set of languages as

regular expressions, i.e., the regular languages. Hence the name.

Allowing regular expressions over terminals and nonterminals in

context-free grammars does not allow them to recognize more languages,

as the regular expressions can be eliminated by rewriting the grammar.

They do, however, make some languages marginally more compact to

describe (though only up to a constant factor).

The Chomsky hierarchy describes both a hierarchy of grammars and a

hierarchy of language classes. Each of these language classes have a

multitude of different equivalent characterizations, both by variant

forms of grammars and by automata. Examples:

Type 3: Left regular grammars, Right regular grammars, regular

expressions, deterministic finite automata, indeterministic

finite automata, ...

Type 2: Context free grammars, nondeterministic one-way pushdown

automata, syntax diagrams, ...

Type 1: Context sensitive grammars (several variants),

nodeterministic linear-bounded Turing machines, ...

Type 0: Unrestricted grammars, Turing machines, any Turing-complete

programming language.

Torben

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.