Re: Finite State Automaon Question

torbenm@diku.dk (=?iso-8859-1?q?Torben_=C6gidius_Mogensen?=)
24 Mar 2005 21:13:05 -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: torbenm@diku.dk (=?iso-8859-1?q?Torben_=C6gidius_Mogensen?=)
Newsgroups: comp.compilers
Date: 24 Mar 2005 21:13:05 -0500
Organization: Department of Computer Science, University of Copenhagen
References: 05-03-058 05-03-063 05-03-073
Keywords: lex
Posted-Date: 24 Mar 2005 21:13:05 EST

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


> Torben Ęgidius Mogensen wrote:
>
> > [Method deleted]
> >
> > I can't offhand determine if your method is O.K., but here is an
> > alternative:


[Alternative method deleted]


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


Why is it not right?


Your definition was that L3 is such that for any string v in L1 there
is a string in w L3 such that vw is in L2. Furthermore, for any
string w in L3, there is a string v in L1 such that vw is in L2.


Both of these are certainly true for the above. As you said, there is
no unique solution to the problem. I think my method may give a
maximal solution, i.e., a maximal L3 where the above is true. You may
(without saying so) have wanted a minimal L3 (which in the example
above would be abab).


                Torben


Post a followup to this message

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