Mon, 2 Nov 1992 13:41:48 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: | jan@klikspaan.si.hhs.nl |

Organization: | Compilers Central |

Date: | Mon, 2 Nov 1992 13:41:48 GMT |

Keywords: | parse, theory, comment |

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

The moderator writes:

*> Intersection and difference [of grammars] start to get interesting.*

Anton Marin Ertl writes:

*> Very interesting, as we can use intersection to construct all-time*

*> favourites like a^n b^n c^n:*

Which is not definable with a context-free grammar.

But intersection can be done with regular languages:

- Starting with two languages defined by deterministic finite automata.

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

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

- Create a deterministic equivalent with the subset construction with a

small modification: Final states are sets of states containing final

states from both originals.

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

automata together with all transitions to or from them.

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

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

Or do I overlook something?

--

Jan Schramp, Haagse Hogeschool - Sector Informatica. Louis Couperusplein 19,

2514 HP Den Haag, Netherlands. E-mail: jan@si.hhs.nl

[I'd think you might have trouble intersecting machines with equivalent but

not identical sets of states. -John]

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.