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.

  • $\begingroup$ Have you performed your construction on a small example? Did it work? $\endgroup$
    – 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)$?

  • $\begingroup$ I'm pretty sure pref(L) isn't regular either. All the words in L are also in pref(L) because a whole word is a prefix of itself. If there's no NFA for L, there won't be an NFA for pref(L). $\endgroup$
    – user76508
    Nov 25 '14 at 8:37
  • 2
    $\begingroup$ 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)$? $\endgroup$
    – Mike B.
    Nov 25 '14 at 10:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.