Re: Need help with proof - regular language

cmpstudent@aol.com (Cmpstudent) writes:
> I was wondering if anyone could offer some insight on how to go about proving
> the following:
>
> If L is a language over the alphabet {0,1}
> and
> Pref(L) = {w in {0,1}* : x = wy for some x in L, y in {0,1}*}
> (ie. the set of prefixes of L)
> Prove that if L is accepted by some finite automaton then so is Pref(L).


There's nothing lost by doing the proof with postfixes instead. Let the
alphabet be denoted X (so here, X = {0,1}) and for any subset L of X* define
Post(L) = { w in X*: yw is in L for some y in X* }


To find prefixes, use the formula:
                                                      Pre(L) = Post(L')'
where A' denotes the set of reverses of words in A. (A' can be written
down by reversing the order of all products in the regular expression for
A).


For any subset S of X* and w in X* let
dS/dw = { v in X*: wv is in S }
and let d/dw denote the operation that transforms S into dS/dw.


The Post(L) is the union of all dL/dw for w in X*.


This operation has the properties:
dL/d(vw) = d/dw (dL/dv)
dL/de = L


so every dL/dw can be decomposed into the form
dL/dw = d/dxn ... d/dx2 (dL/dx1),
w = x1 x2 ... xn, x's symbols from the alphabet X


It also has the properties, for any symbol x in X, that:


d0/dx = 0
de/dx = 0 e = empty word
dx/dx = 1
dy/dx = 0, y in X
d(A + B)/dx = dA/dx + dB/dx ---- + denotes union here
d(A*)/dx = dA/dx A*
d(AB)/dx = dA/dx B + A_0 dB/dx


where A_0 is obtained from A by substituting 0's for every symbol of X in A
Example:
      if x, y are in X and A = x* (yxx)* + xyx, then A_0 = 0* (000)* + 000 = e


Therefore, if L is any ratinal subset of X*, then the formulas above prove
that dL/dx is as well.


Therefore, by successive application of this property, it also follows that
dL/dw = d/dxn ... d/dx2 (dL/dx1),
w = x1 x2 ... xn, x's symbols from the alphabet X


is also a rational subset of X*.


But ...
          cl(L) = { dL/dw: w is in X* } is finite
          <--> L is a rational subset of X*


and the union of a finite number of rational subsets is also rational.


Let s(L) denote the number of items in cl(L). In other words, define
s(L) = the number of distinct dL/dw as w ranges over X*


Then s(L) has the bounds:
    cl(0) = {0} ------- s(0) = 1
    cl(e) = {0,e} ----- s(e) = 2
    cl(x) = {0,e,x} --- s(x) = 3, x in X
    cl(A*) subset of { (v1 + ... + vn) A*: v's in cl(A) }
s(A*) <= 2 ^ s(A)
    cl(A + B) subset of { u + v: u in cl(A), v in cl(B) }
s(A + B) <= s(A) x s(B)
    cl(A B) subset of
          { (u1 + ... + un) B + (v1 ... + vp): u's in cl(A), v's in cl(B) }
s(AB) <= 2 ^ s(A) x 2 ^ s(B) = 2 ^ (s(A) + s(B))


Example: (Derived expressions labeled A, B, ... for convenience)
                  Over alphabet X = { a, b }
L = a* (b a)* + b b* a
            A = dL/da = a* (b a)*
            B = dL/db = a (b a)* + b* a


dA/da = a* (b a)* = A
            C = dA/db = a (b a)*
            D = dB/da = (b a)* + e = (b a)*
            E = dB/db = b* a


dC/da = (b a)* = D
            F = dC/db = 0
dD/da = 0 = F
dD/db = a (b a)* = C
            G = dE/da = e
dE/db = b* a = E


                    dF/da = dF/db = 0 = F
dG/da = dG/db = 0 = G


So the closure of L is cl(L) = { L, A, B, C, D, E, F, G } and
Post(L) = L + A + B + C + D + E + F + G
= (A + bE) + A + (C + E) + C + D + E + 0 + e
= A + bE + C + D + E + e
= (A + C + D + e) + bE + E
= A + bE + E, since C, D and e are subsets of A
= a* (b a)* + b b* a + b* a

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