Re: Need help with proof - regular language

"Gene Ressler" <>
3 Feb 1999 23:58:15 -0500

          From comp.compilers

Related articles
Need help with proof - regular language (1999-02-01)
Re: Need help with proof - regular language (Chris F Clark) (1999-02-03)
Re: Need help with proof - regular language (Gene Ressler) (1999-02-03)
Re: Need help with proof - regular language (1999-02-07)
| List of all articles for this month |

From: "Gene Ressler" <>
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.


Cmpstudent <> 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.