patternModerate
Non-regular language whose prefix language is regular but not the whole set of words
Viewed 0 times
thewhosenonwholebutregularwordslanguageprefixnot
Problem
I've seen some questions regarding the regularity of prefix language of non-regular languages (for examples, here and here). In both cases, the prefix language ended up just being the whole set of words $\Sigma^*$, for $\Sigma$ the alphabet over which the languages are defined.
So I was thinking of examples where $\mathit{pref}\,(L)$ would be regular, but different from $\Sigma^*$, for $L$ some non-regular language. For a regular $L$, I could just take a finite language, but, for a non-regular language, I have yet to find an example.
Note that all languages over a unary alphabet are excluded, by one of the examples given in this question.
An example where $\mathit{pref}\,(L)$ would not be regular would be $L=\{0^{n^2}1,\,n\in\mathbb{N}\,\}$, whose prefix language is $\mathit{pref}\,(L)=\{0\}^*\cup L$.
So I was thinking of examples where $\mathit{pref}\,(L)$ would be regular, but different from $\Sigma^*$, for $L$ some non-regular language. For a regular $L$, I could just take a finite language, but, for a non-regular language, I have yet to find an example.
Note that all languages over a unary alphabet are excluded, by one of the examples given in this question.
An example where $\mathit{pref}\,(L)$ would not be regular would be $L=\{0^{n^2}1,\,n\in\mathbb{N}\,\}$, whose prefix language is $\mathit{pref}\,(L)=\{0\}^*\cup L$.
Solution
If there are no further rules, then there is a simple solution. In any existing example double all symbols in each string. That is, change the symbols $0$ and $1$ by the pairs $00$ and $11$. Formally that is an homomorphism.
Now the resulting language has no longer all strings as prefix. It also does not change context-freeness or regularity.
Now the resulting language has no longer all strings as prefix. It also does not change context-freeness or regularity.
Context
StackExchange Computer Science Q#154128, answer score: 14
Revisions (0)
No revisions yet.