|Finite State Automaon Question vborkyREMOVE_THIS@yahoo.com (Vinayak R. Borkar) (2005-03-15)|
|Re: Finite State Automaon Question email@example.com (2005-03-18)|
|Re: Finite State Automaon Question firstname.lastname@example.org (Vinayak R. Borkar) (2005-03-20)|
|Re: Finite State Automaon Question email@example.com (2005-03-24)|
|Re: Finite State Automaon Question firstname.lastname@example.org (2005-03-24)|
|Re: Finite State Automaon Question email@example.com (Nathan Moore) (2005-03-25)|
|Re: Finite State Automaon Question firstname.lastname@example.org (Vinayak R. Borkar) (2005-03-31)|
|Re: Finite State Automaon Question email@example.com (2005-04-02)|
|From:||"Vinayak R. Borkar" <firstname.lastname@example.org>|
|Date:||20 Mar 2005 10:14:30 -0500|
|Posted-Date:||20 Mar 2005 10:14:30 EST|
Torben Ęgidius Mogensen wrote:
> [Method deleted]
> I can't offhand determine if your method is O.K., but here is an
> 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
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?
Return to the
Search the comp.compilers archives again.