21 Oct 2004 22:19:44 -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: | mefrill@yandex.ru (Vladimir) |

Newsgroups: | comp.compilers |

Date: | 21 Oct 2004 22:19:44 -0400 |

Organization: | http://groups.google.com |

References: | 04-10-111 |

Keywords: | parse, theory |

Posted-Date: | 21 Oct 2004 22:19:44 EDT |

"valentin tihomirov" <spam@abelectron.com> wrote

*> 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?*

As you probably know, each Chomsky grammar is a device, which

generates some formal language (a set of strings). So, type 3 grammar

also defines some formal language. And this language can be defined by

applying three basic operations to vocabulary (terminals of the

grammar) of the language. These operations are: concatenation,

alternation and Kleene closure. each language that can be constructed

by using these three operations is named as regular. The text with

such the definition of operations applying to vocabulary is named as

regular expression. For instance, we have vocabulary V={a,b,c} and the

ragular expression a*(b|c). The expresion defines the formal language

L={b,c,ab,ac,aab,...}. This language can be defined also by using

Chomsky type 3 grammar:

S --> A B

S --> A C

A --> epsilon

A --> a A

A --> a

B --> b

C --> c

There is a theorem, which says each regular language (i.e. language,

which can be constructed by using three operation above) can be

defined by using three equivalent devices: Chomsky type 3 grammar,

regular expression and finite state machine. Thus, such the

equivalence is the reason to name type 3 grammars as "regular" ones.

Vladimir.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.