Re: Grammar Algebra?

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

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