7 Feb 1999 00:15:25 -0500

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

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

Return to the
comp.compilers page.

Search the
comp.compilers archives again.