patternMinor
Non-regular language whose prefix language is regular
Viewed 0 times
whosenonregularlanguageprefix
Problem
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.
Give an example of a non-regular language $A ⊆ \{0, 1\}^*$ for which $\operatorname{Prefix}(A)$ is regular.
Solution
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.
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.
Context
StackExchange Computer Science Q#98112, answer score: 7
Revisions (0)
No revisions yet.