Re: Finite State Automaon Question

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


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


[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.


                Torben

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