Re: Grammar Algebra?

hdev@dutiaj.twi.tudelft.nl (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? 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: hdev@dutiaj.twi.tudelft.nl (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

jan@klikspaan.si.hhs.nl writes:

>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.

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
--

Post a followup to this message