2 Apr 2005 19:33:36 -0500

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

From: | torbenm@diku.dk (=?iso-8859-1?q?Torben_=C6gidius_Mogensen?=) |

Newsgroups: | comp.compilers |

Date: | 2 Apr 2005 19:33:36 -0500 |

Organization: | Department of Computer Science, University of Copenhagen |

References: | 05-03-058 05-03-063 05-03-073 05-03-082 05-03-130 |

Keywords: | lex, theory |

Posted-Date: | 02 Apr 2005 19:33:36 EST |

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

*> Torben Ęgidius Mogensen wrote:*

*> >> > [Method deleted]*

*> > [Alternative method deleted]*

*> >>*

*> >> L1: (ab)**

*> >> L2: (ab)*abab*

*> >>*

*> >> By your method, I get L3 to be (ab)*, but this is not right.*

*> >*

*> The problem that I needed to solve was:*

*>*

*> Find L3 such that*

*>*

*> For any string v in L1 and w in L3, vw is in L2, and*

*> for any string vw in L2, there is a v in L1 and w in L3.*

I think you mean "for any string x in L2, there is a v in L1 and w in

L3 such that x = vw". Otherwise, it implies that any prefix of L2 is

in L1, which is not teh case for your example.

*> In other words, L2 = L1.L3, where dot means "followed by"*

*>*

*> But this is not satisfied by the example above.*

I see. My solution satisfies the second condition, but not the first,

so I get L2 \subseteq L1.L3. I think I may have replaced a "forall"

by an "exist" in my head while making the construction.

In any case, here is a correct, though rather inefficient,

construction:

1. Construct minimal DFA's D1 and D2 for L1 and L2.

2. Enumerate all DFA's over the alphabet.

3. For each such DFA D3, construct an NFA D1.D3 by adding epsilon

transitions from all accepting states in D1 to the initial state

of D3. Convert this NFA to a minimal DFA.

4. If the minimal DFA is equal to D2, accept D3 as a DFA for L3.

The problem is that this will fail to terminate if there is no L3 that

satisfies the specification.

To find a more direct construction, we should first consider the

requirements:

1. For every string v in L1 and w in L3, vw is in L2.

2. Every string x in L2 can be written as vw, v in L1 and w in L3.

Let us assume a minimal DFA D2 for L2. We now mark all states t that

are reached by reading a string from L1. By requirement 2, there must

be at least one such on any path to an accepting state in D2.

If we are in such a state t, then by requirement 1 we can reach an

accepting state by reading any string w in L3. So, any valid L3 is a

subset of the language generated by a copy of D2 with starting state

changed to t. Consequently, any valid L3 is a subset of the

intersection of the languages generated by these changed copies of D2.

Will the intersection itself be a valid L3? We saw that any valid L3

must be a subset of the intersection language, it fulfils requirement

1 by construction and if requirement 2 is fulfilled by a L3, any

supersets of that L3 will also do so. So the intersection language

will fulfill both requirements.

For your example, the constructed L3 is equal to L2, which is easily

seen to be valid.

Torben

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.