Re: Grammar Algebra?

jan@klikspaan.si.hhs.nl 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
ones.


>- 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
hdev@dutiaa.tudelft.nl
Delft University of Technology (TWI-ThI)
The Netherlands
--

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