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

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.

• Have you performed your construction on a small example? Did it work?
– Raphael
Nov 25 '14 at 7:21

What you say doesn't make sense. How can you operate with a NFA for $L$ if you cant be sure that $L$ is regular?
Try to consider this language $$L=\{ uu \mid u \in \Sigma^*\}$$ This language is not regular, it is not even context-free, which can be shown with the pumping lemma. I think from here you can continue by yourself. What is $\text{pref}(L)$?
• Languages based on unary alphabets are also very practical, they often simplify the problem. Assume $L=\{a^{2^n} \mid n \in N\}$. Is $L$ regular? What is $pref(L)$? Nov 25 '14 at 10:21