Re: Need help with proof - regular language

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

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