3 Feb 1999 23:58:15 -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: | "Gene Ressler" <resslere@erols.com> |

Newsgroups: | comp.compilers |

Date: | 3 Feb 1999 23:58:15 -0500 |

Organization: | O/Dean |

References: | 99-02-007 |

Keywords: | lex, theory |

This is actually a watered down version of the question that one

usually sees, which is, "Prove that if L is regular, then Pref(L) is

also regular." This requires you to figure out that an argument based

on DFAs is a good approach.

The beauty of proofs involving regular languages is that Kleene's

theorem gives you three equivalent and powerful tools. Just as you

don't use a saw to drive a nail, you usually can't use the three

"Kleene tools" with equal alacrity. For this one, the DFA is the

surely the best.

You might be able to prove this by induction over the structure of REs

(as you propose): Let R be a regex for L, then show you can get from

the null regex to R by adding pieces in a way the includes all strings

in Pref(L) (exploiting closure properties as you suggest), but this is

going to be hairy and messy and hard to get right; more importantly

hard to convince anyone else that you got it right.

Anyway, a thoughtful and good question, though you may get a more

lively discussion in comp.theory...

This is the kind of question one frequently sees in PhD qualifying

exams. If you're at a university, ask someone in the graduate program

if there is a review library.

Gene

Cmpstudent <cmpstudent@aol.com> wrote:

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.