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.

  • $\begingroup$ 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. $\endgroup$ – Raphael Oct 4 '18 at 8:37

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.

The question has been answered.

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.

  • 2
    $\begingroup$ 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\}$ $\endgroup$ – Bader Abu Radi Oct 4 '18 at 6:03
  • $\begingroup$ How can computer science educators ever win this race? It's not fair. $\endgroup$ – reinierpost Oct 4 '18 at 6:25
  • $\begingroup$ Please consider not to encourage undesirable posting behaviour. $\endgroup$ – Raphael Oct 4 '18 at 8:37
  • 1
    $\begingroup$ @reinierpost I think it'd help your point if you elaborated what the problem is from your perspective. $\endgroup$ – Raphael Oct 4 '18 at 8:37

The other answer gives a particular example of a language fitting your bill. You can also show that almost all languages satisfy your condition.

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.

  • 3
    $\begingroup$ Nice. And in fact over a single letter alphabet every language has a regular prefix language. $\endgroup$ – Hendrik Jan Oct 4 '18 at 9:58

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.