1 Feb 1999 23:37:28 -0500

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

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.