If pref(L) is regular, does that imply L is also regular?

Question

I have this exercise for homework:

Say we have a language L. we know that the language pref(L) (all the prefixes of L, including all the words in L itself) is a regular language. Does this imply that the language L is regular as well?

I took the NFA of pref(L) and divided it (via 2 epsilon transitions from q0) to 2 separate NFA's, as 1 defines L and the other defines pref(L)\L.

What I actually got is a NFA for L, which means it is regular.

I am not sure this is the way or if it legal. I'd be glad for another lead.

Thanks in advance,

Yaron.

Answer 1

It is not necessarily the case that if pref(L) is regular, then L is regular as well.

As an example, let Σ = {a} be a unary alphabet. I'm going to claim that if L is any infinite language over Σ, then pref(L) = Σ*. To see this, first note that pref(L) ⊆ Σ* because every pref(L) is a language over Σ. Now, consider any string in Σ*, which must have the form aⁿ. If L is an infinite language over Σ, it must contain at least one string of the form a^m where m ≥ n. Then aⁿ would be a prefix of a^m, so aⁿ ∈ pref(L). This shows that Σ* ⊆ pref(L) and that pref(L) ⊆ Σ*, so in this case Σ* = pref(L).

Now, all we need to do is find a nonregular language over Σ = {a}. As an example, take the language { a²ⁿ | n ∈ N } of all strings whose length is a power of two. It's possible to prove using either the Myhill-Nerode theorem or the pumping lemma that this language is not regular. However, by the above result, we know that pref(L) is a regular language.

Hope this helps!