Re: Grammar Algebra?
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? (1992-10-27)
Re: Grammar Algebra? hallpwcd@ucunix.san.uc.EDU (1992-10-31)
Re: Grammar Algebra? (1992-11-02)
Re: Grammar Algebra? (1992-11-03)
Re: Grammar Algebra? (1992-11-04)
| List of all articles for this month |

Newsgroups: comp.compilers
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:
[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.