Re: Need help with proof - regular language

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)

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