3 Feb 1999 23:55:54 -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: | Chris F Clark <cfc@world.std.com> |

Newsgroups: | comp.compilers,comp.theory |

Date: | 3 Feb 1999 23:55:54 -0500 |

Organization: | The World Public Access UNIX, Brookline, MA |

Distribution: | inet |

References: | 99-02-007 |

Keywords: | theory, lex |

cmpstudent@aol.com (Cmpstudent) writes:

*> Greetings All,*

*>*

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

*>*

*> I was wondering how/if this could be proved using the closure*

*> properties of regular languages (union, concat, star, complementaion.,*

*> etc)*

I think you might be looking for a proof along these lines:

Basis:

if L is {''} (the set containing only lambda, the empty string)

Perf(L) is also {''} which is an R.E.

if L is {'0'}, Pref(L) = {"", "0"} which is an R.E.

if L is {'1'}, Pref(L) = {"", "1"} which is an R.E.

Induction Step: how each operator concatenation, alternation, and

Kleene closure preserves Pref(L) in R.E. (Other operators, such as

complement can be done similarly.)

Suppose a and b are R.E.'s such that Pref(a) and Pref(b) are R.E.'s

Pref(a concat b) = Pref(a) union a concat Pref(b), which is an R.E.

{ because Pref(a) is an R.E. and Pref(b) in an R.E. and a is an R.E.,

and a concat Pref(b) is an R.E. { because R.E.'s are closed under

concat } and R.E.'s are closed under union }

Pref(a | b) = Pref(a) union Pref(b), which is an R.E.

{ similar argument }

Pref(a*) = a* concat Pref(a), which is an R.E.

{ again }<

Now, given the basis and the induction step, we can show how to

construct Pref(L) based upon L's syntactic form and prove that at

each step Pref(L) is still an R.E.

Hope this helps,

-Chris

*****************************************************************************

Chris Clark Internet : cfc@world.std.com

Compiler Resources, Inc. CompuServe : 74252,1375

3 Proctor Street voice : (508) 435-5016

Hopkinton, MA 01748 USA fax : (508) 435-4847 (24 hours)

------------------------------------------------------------------------------

Web Site in Progress: Web Site : http://world.std.com/~compres

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.