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 <nathan.moore@sdc.cox.net>
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.


  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


Post a followup to this message

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