25 Mar 2005 21:56:29 -0500

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

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.