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