Re: Grammar Algebra? (Hans de Vreught)
Tue, 3 Nov 1992 08:50:44 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
From: (Hans de Vreught)
Organization: Compilers Central
Date: Tue, 3 Nov 1992 08:50:44 GMT
References: 92-10-126 92-10-122 92-11-007
Keywords: parse, theory writes:

>But intersection can be done with regular languages:
>- Starting with two languages defined by deterministic finite automata.

Actually, you start with *fully* specified DFAs (including error states).

>- Merge the automata by assigning a new start state and epsilon
> transitions from the new start state to the start states of both originals.

No, it is not a matter of merging, it is a matter of forming the cross
product of two machines. The states are formed by the Carthesian product
of the state sets of the two machine. The new start symbol is the pair
formed by the two starting states of the original states and the final
states are formed by those pairs from which both original states are
final. The transition function is merely the cross product of the original

>- Create a deterministic equivalent with the subset construction with a
> small modification: Final states are sets of states containing final
> states from both originals.

No need, the cross product of DFAs is a DFA.

>- Next remove all states that are sets of states of only one of the original
> automata together with all transitions to or from them.

Well, shall we say "just minimize the DFA".

>- An alternative for the last step is converting the deterministic automaton
> to a grammar and making that `proper' to remove all useless parts.

BTW, the intersection of a CFL and a regular language is a CFL (see Harrison,
Introduction to Formal Language Theory, Addison Wesley, 1978).

It is nice to see that the old pupil can teach the Master a lesson (Jan is my
old lecturer in compiler design).
Hans de Vreught
Delft University of Technology (TWI-ThI)
The Netherlands

Post a followup to this message

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