# Re: Finite State Automaon Question

## Nathan Moore <nathan.moore@sdc.cox.net>25 Mar 2005 21:56:29 -0500

From comp.compilers

Related articles
Finite State Automaon Question vborkyREMOVE_THIS@yahoo.com (Vinayak R. Borkar) (2005-03-15)
Re: Finite State Automaon Question torbenm@diku.dk (2005-03-18)
Re: Finite State Automaon Question vborky@yahoo.com (Vinayak R. Borkar) (2005-03-20)
Re: Finite State Automaon Question torbenm@diku.dk (2005-03-24)
Re: Finite State Automaon Question peter.ludemann@gmail.com (2005-03-24)
Re: Finite State Automaon Question nathan.moore@sdc.cox.net (Nathan Moore) (2005-03-25)
Re: Finite State Automaon Question vborky@yahoo.com (Vinayak R. Borkar) (2005-03-31)
Re: Finite State Automaon Question torbenm@diku.dk (2005-04-02)
| List of all articles for this month |

 From: Nathan Moore Newsgroups: comp.compilers Date: 25 Mar 2005 21:56:29 -0500 Organization: Cox Communications References: 05-03-058 Keywords: lex Posted-Date: 25 Mar 2005 21:56:29 EST

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.

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

Post a followup to this message