Re: Finite State Automaon Question

"Vinayak R. Borkar" <vborky@yahoo.com>20 Mar 2005 10:14:30 -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)
Re: Finite State Automaon Question torbenm@diku.dk (2005-04-02)
| List of all articles for this month |

 From: "Vinayak R. Borkar" Newsgroups: comp.compilers Date: 20 Mar 2005 10:14:30 -0500 Organization: SBC http://yahoo.sbc.com References: 05-03-058 05-03-063 Keywords: lex 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
> 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.

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.

Post a followup to this message