20 Mar 2005 10:14:30 -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: | "Vinayak R. Borkar" <vborky@yahoo.com> |

Newsgroups: | comp.compilers |

Date: | 20 Mar 2005 10:14:30 -0500 |

Organization: | SBC http://yahoo.sbc.com |

References: | 05-03-058 05-03-063 |

Keywords: | lex |

Posted-Date: | 20 Mar 2005 10:14:30 EST |

Torben Ęgidius Mogensen wrote:

*> [Method deleted]*

*>*

*> I can't offhand determine if your method is O.K., but here is an*

*> alternative:*

*>*

*> Given DFA's D1 and D2 for L1 and L2, make a DFA D3 where each state in*

*> D3 is a pair of states from D1 and D2 and there is a transition from*

*> (s1,s2) to (t1,t2) on symbol c if there are transitions from s1 to t1*

*> and s2 to t2 in D1 and D2, respectively. Start with the pair of start*

*> states from D1 and D2 and find all that are reachable from this.*

*> Since any string in L1 is a prefix of a string in L2, all states from*

*> D1 will be represented in at least one pair of states in D3.*

*>*

*> Now look at the set S of states s2 where there exist a pair (s1,s2) in*

*> D3 such that s1 is an accepting state of D1. Make a new*

*> (nondeterministic) automata N that has the states of D2 but a new*

*> initial state s0 that has epsilon transitions to all the states in S.*

*> The final states are unchanged.*

*>*

*> Let us imagine a string w in L3. Then there exists a string v in L1*

*> such that vw is in L2. This means that we after reading v in D3 will*

*> reach a state that is a pair of a final state s1 from D1 and a state*

*> s2 from D2. Starting from s2, we can in D2 reach a final state after*

*> reading w (as vw is accepted by D2), so w will also be accepted by N.*

*>*

*> Conversely, assume a string w accepted by N. The first transition in*

*> N is an epsilon transition to a state s2 from D2. But since there is*

*> a pair of states (s1,s2) in D3, where s1 is accepting in D1, there*

*> exist a string v in L1 such that in D2, v leads to s2. Hence, vw will*

*> be accepted by D2, so vw is in L2.*

Thanks for the reply.

I tried your method on

L1: (ab)*

L2: (ab)*abab

The DFA for L2 is abab(ab)*

By your method, I get L3 to be (ab)*, but this is not right.

Am I missing something?

Thanks,

Vinayak.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.