Finite State Automaon Question

"Vinayak R. Borkar" <vborkyREMOVE_THIS@yahoo.com>15 Mar 2005 01:44:00 -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)
[1 later articles]
| List of all articles for this month |

 From: "Vinayak R. Borkar" 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