# Need help with proof - regular language

## cmpstudent@aol.com (Cmpstudent)1 Feb 1999 23:37:28 -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: cmpstudent@aol.com (Cmpstudent) Newsgroups: comp.compilers Date: 1 Feb 1999 23:37:28 -0500 Organization: AOL http://www.aol.com Keywords: theory, question, comment

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 can see how to show by taking the FA accepting L and making the
states that are not accepting states into accepting states. However,
I was wondering how/if this could be proved using the closure
properties of regular languages (union, concat, star, complementaion.,
etc)

Also, if anyone knows where I can get examples similar to this that
would be great.

Any help would be greatly appreciated.

Thank You,
Jennifer
cmpstudent@aol.com
[She promises this isn't a homework question. -John]

Post a followup to this message