# Re: Need help with proof - regular language

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