Re: Finite State Automaon Question

I just thought up the following. It is possible that it is a
more English version of one of the already mentioned algorithms,
but those are hard to read and this should be easier to understand.


  Using an adjacency matrix to represent each of the FSAs and start with
L1 and L2 in reduced DFA form to avoid headaches. M1 accepts L1 and M2
accepts L2.


Find all ending nodes in M1.


Find nodes in M2 that correspond to the ending nodes in M1.


Make a copy of M2 without marking the existing start node as the start node.


Make a new start node in `M2 with lambda transitions to all
of the nodes that were found to correspond to the final nodes
of M2.


`M2 will accept the language M3, but you will probably want to
remove all the unreachable nodes and make it deterministic before
you call it M3.


This should yield the full L3 (M3 accepts L3).


Anyone spot any errors?


Nathan Moore

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