15 Mar 2005 01:44:00 -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) |

[1 later articles] |

From: | "Vinayak R. Borkar" <vborkyREMOVE_THIS@yahoo.com> |

Newsgroups: | comp.compilers |

Date: | 15 Mar 2005 01:44:00 -0500 |

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

Keywords: | lex, theory, question |

Posted-Date: | 15 Mar 2005 01:44:00 EST |

Hi,

At work we were faced with the following problem.

Consider two regular languages L1, and L2. It is known that

L2 = L1, L3 where L3 is yet another regular language.

Given L1 and L2, what is the algorithm to find L3?

I realize that L3 may not be unique for any given L1 and L2.

All I need is any one L3 that satisfies the above relation.

What would be a good place to look for this kind of analysis?

I have a method in mind to figure a possible L3. It would be

great if someone could show if it is right or wrong, and why.

The method is as follows:

1. Let D1 is the min DFA of L1 and D2 the min DFA of L2.

2. Let S1 be the start state in D1 and S2 the start state

in D2.

3. Let M = { ( S1, { S2 } ) }

4. Let SEEN = { }

5. foreach (S, E) in M such that S not in SEEN

6. foreach state S_prime in D1 that has any in transition

from S

7. Find the union of states that are reachable from any

state in E in D2 and call that set E_prime

8. Let M = M U (S_prime, E_prime)

9. Let EF = { }

10. foreach F in accepting states of D1

11. EF = EF U E where (F, E) in M.

12. In D2, eliminate all states and their transitions that

are not reachable from any state in EF.

13. Add a new state B and epsilon transitions from B to each

state in EF.

My conjecture is that the resulting NFA with B as the start

state accepts L3 such that L2 = (L1, L3).

Does it make sense?

Thanks,

Vinayak.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.