Re: Q: regarding regular grammars ...

"Jos A. Horsmeier" <jos@and.nl>
29 Nov 1997 00:28:53 -0500

          From comp.compilers

Related articles
Q: regarding regular grammars ... mcr@visi.com (Michael Roach) (1997-11-24)
Re: Q: regarding regular grammars ... henry@zoo.toronto.edu (Henry Spencer) (1997-11-28)
Re: Q: regarding regular grammars ... karsten@tdr.dk (Karsten Nyblad) (1997-11-29)
Re: Q: regarding regular grammars ... jos@and.nl (Jos A. Horsmeier) (1997-11-29)
Re: Q: regarding regular grammars ... henry@zoo.toronto.edu (Henry Spencer) (1997-11-30)
Re: Q: regarding regular grammars ... adrian@dcs.rhbnc.ac.uk (1997-12-05)
| List of all articles for this month |

From: "Jos A. Horsmeier" <jos@and.nl>
Newsgroups: comp.compilers
Date: 29 Nov 1997 00:28:53 -0500
Organization: AND Software B.V. Rotterdam
References: 97-11-136
Keywords: lex

Michael Roach wrote:


> Could someone please shed some light on how regular grammars could be
> used to specify automata, or transducers, instead of using regular
> expressions? I think I've confused myself by reading into some papers.
>
> I thought regular expressions were regular grammars, is that assumption
> wrong? And if so, could you explain the differences or point me to some
> references. Thanks.


The class of languages described by regular expressions (RE), type 3
(regular) grammars (RG) and the class of languages accepted by NFAs
or DFAs are all equal. It's quite easy to construct an NFA given a
RG -- all rules of a RG are of the following form:


1: S_1 ---> t S_2
2: S_1 ---> S_2
3: S_1 ---> t
4: S_1 ---> <epsilon>


given a RG, construct a NFA as follows:


- for every S_i add a vertex <S_i> to the NFA
- add one 'accepting' vertex <S_a>
- for every type 1 rule, add an edge <S_1> ---> t ---> <S_2>
- for every type 2 rule, add an edge <S_1> ---> <S_2>
- for every type 3 rule, add an edge <S_1> ---> t ---> <S_a>
- for every type 4 rule, add an edge <S_1> ---> <S_a>


The transformation from a NFA to a DFA can be found in any reasonable
textbook
(the Dragon book (a _good_ book ;-) comes to mind ...)


kind regards,


Jos aka jos@and.nl
--


Post a followup to this message

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