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

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