Finite State Automaon Question

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.

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