# Re: Need help with proof - regular language

## hunk@alpha1.csd.uwm.edu (Mark William Hopkins)7 Feb 1999 00:15:25 -0500

From comp.compilers

Related articles
Need help with proof - regular language cmpstudent@aol.com (1999-02-01)
Re: Need help with proof - regular language cfc@world.std.com (Chris F Clark) (1999-02-03)
Re: Need help with proof - regular language resslere@erols.com (Gene Ressler) (1999-02-03)
Re: Need help with proof - regular language hunk@alpha1.csd.uwm.edu (1999-02-07)
| List of all articles for this month |

 From: hunk@alpha1.csd.uwm.edu (Mark William Hopkins) Newsgroups: comp.compilers Date: 7 Feb 1999 00:15:25 -0500 Organization: University of Wisconsin - Milwaukee, Computing Services Division References: 99-02-007 Keywords: theory

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

Post a followup to this message