Re: Grammar Algebra?

jan@klikspaan.si.hhs.nl
Mon, 2 Nov 1992 13:41:48 GMT

          From comp.compilers

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)
| List of all articles for this month |

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.