Re: Q: regarding regular grammars ...

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

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