|Grammar Algebra? email@example.com.EDU (1992-10-26)|
|Re: Grammar Algebra? firstname.lastname@example.org (1992-10-27)|
|Re: Grammar Algebra? email@example.com.EDU (1992-10-31)|
|Re: Grammar Algebra? firstname.lastname@example.org (1992-11-02)|
|Re: Grammar Algebra? email@example.com (1992-11-03)|
|Re: Grammar Algebra? Peter.Breuer@prg.oxford.ac.uk (1992-11-04)|
|Date:||Mon, 2 Nov 1992 13:41:48 GMT|
|Keywords:||parse, theory, comment|
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: firstname.lastname@example.org
[I'd think you might have trouble intersecting machines with equivalent but
not identical sets of states. -John]
Return to the
Search the comp.compilers archives again.