# Non-regular language whose prefix language is regular

I understand that prefix of a regular language is regular, but I am unable to get my head around this:

Give an example of a non-regular language $$A ⊆ \{0, 1\}^*$$ for which $$\operatorname{Prefix}(A)$$ is regular.

• Welcome to Computer Science! We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed / downvoted. You may also want to check out these hints, or use the search engine of this site to find similar questions that were already answered.
– Raphael
Oct 4 '18 at 8:37
• @hsnsd, was my answer helpful? Have you considered accepting it? (This comment will be removed.) Apr 22 '20 at 20:02

One approach to think of examples or counterexamples is to looking for the simplest examples or starting from some known situations.

What are some typical examples of non-regular languages? A typical example is the language of palindromes. Its prefix language contains every word $$w$$, since $$ww^R$$ is a palindrome. That is, its prefix language is a regular language.

However, as pointed out by Bader Abu Radi, the above example breaks down with unary alphabet, when the language of palindromes is the set of all words.

What are some typical examples of non-regular languages over unary alphabet, say $$\{a\}$$?

Let us try $$\{a^{n^2}\mid n\ge0\}$$ or $$\{a^{2^n}\mid n\ge0\}$$ or just any non-regular language you can think of. Since it is non-regular, its words can be arbitrarily long. That means its prefix language contains all words, $$\epsilon, a, a^2, \cdots$$. That is, its prefix language is regular.

Readers may enjoy the following two exercises.

Exercise 1 (easy). Show that an example over unary alphabet can be considered as an example over any larger alphabet.

Exercise 2. A language is prefix-closed if it is own prefix language. Give an example of non-regular prefix-closed language that does not contain a regular infinite language.

• Correct and if you want something that works with unary alphabet. You can consider the following non-regular languages: $\{0^p: where \ p \ is \ prime \}$ or $\{0^{n!}: n \ is \ natural\}$ Oct 4 '18 at 6:03
• How can computer science educators ever win this race? It's not fair. Oct 4 '18 at 6:25
• Please consider not to encourage undesirable posting behaviour.
– Raphael
Oct 4 '18 at 8:37
Fix an alphabet $$\Sigma$$, and let $$L$$ be a random language over $$\Sigma$$ sampled by putting in each $$w \in \Sigma^*$$ with probability 1/2. Since there are only countably many regular languages, almost surely $$L$$ is not regular. Conversely, for every fixed $$x \in \Sigma^*$$, almost surely one of the infinitely many words $$y \in \Sigma^*$$ is such that $$xy \in L$$. Since there are only countably many words in $$\Sigma^*$$, it follows that almost surely the prefix language of $$L$$ is $$\Sigma^*$$, which is regular.