Re: Finite State Automaon Question

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.

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