Re: Finite State Automaon Question

"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

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