Tue, 3 Nov 1992 08:50:44 GMT

Related articles |
---|

Grammar Algebra? hallpwcd@ucunix.san.uc.EDU (1992-10-26) |

Re: Grammar Algebra? wand@dec5120z.ccs.northeastern.edu (1992-10-27) |

Re: Grammar Algebra? hallpwcd@ucunix.san.uc.EDU (1992-10-31) |

Re: Grammar Algebra? jan@klikspaan.si.hhs.nl (1992-11-02) |

Re: Grammar Algebra? hdev@dutiaj.twi.tudelft.nl (1992-11-03) |

Re: Grammar Algebra? Peter.Breuer@prg.oxford.ac.uk (1992-11-04) |

Newsgroups: | comp.compilers |

From: | hdev@dutiaj.twi.tudelft.nl (Hans de Vreught) |

Organization: | Compilers Central |

Date: | Tue, 3 Nov 1992 08:50:44 GMT |

References: | 92-10-126 92-10-122 92-11-007 |

Keywords: | parse, theory |

jan@klikspaan.si.hhs.nl writes:

*>But intersection can be done with regular languages:*

*>- Starting with two languages defined by deterministic finite automata.*

Actually, you start with *fully* specified DFAs (including error states).

*>- Merge the automata by assigning a new start state and epsilon*

*> transitions from the new start state to the start states of both originals.*

No, it is not a matter of merging, it is a matter of forming the cross

product of two machines. The states are formed by the Carthesian product

of the state sets of the two machine. The new start symbol is the pair

formed by the two starting states of the original states and the final

states are formed by those pairs from which both original states are

final. The transition function is merely the cross product of the original

ones.

*>- Create a deterministic equivalent with the subset construction with a*

*> small modification: Final states are sets of states containing final*

*> states from both originals.*

No need, the cross product of DFAs is a DFA.

*>- Next remove all states that are sets of states of only one of the original*

*> automata together with all transitions to or from them.*

Well, shall we say "just minimize the DFA".

*>- An alternative for the last step is converting the deterministic automaton*

*> to a grammar and making that `proper' to remove all useless parts.*

BTW, the intersection of a CFL and a regular language is a CFL (see Harrison,

Introduction to Formal Language Theory, Addison Wesley, 1978).

It is nice to see that the old pupil can teach the Master a lesson (Jan is my

old lecturer in compiler design).

--

Hans de Vreught

hdev@dutiaa.tudelft.nl

Delft University of Technology (TWI-ThI)

The Netherlands

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.