Non-regular language whose prefix language is regular but not the whole set of words

Question

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$.

Answer 1

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.

Answer 2

Here's a quite simple example: the language $\{a^m b^{mn} : m, n \in \mathbb{N}\}$ is not regular, but its prefix language is recognised by the regular expression $\epsilon \mathop{|} a a^{*} b^{*}$.

Answer 3

Several simple examples

The language $\{(01)^{n^2}: n\ge0\}$ is nonregular, but its prefix language is $(\epsilon+0)(10)^*(\epsilon + 1)$.

The language $\{0^n1^m: 0\le n\le m\}$ is nonregular, but its prefix language is $0^*1^*$.

Given a non-regular language $N$ such that $\mathit{pref}(N)$ is regular, we have

• $wN$ is a non-regular language, whose prefix language is regular but does not contain $1$, for any word $w$ that start with 0.

• $N_\overline\sigma=\{u\in N\mid u\text{ does not start with } \sigma\}$ must be nonregular for some symbol $\sigma$, $\mathit{pref}(N_\overline\sigma)$ is regular but does not contain $\sigma$.

• $N_\sigma=\{u\in N\mid u\text{ starts with } \sigma\}$ must be nonregular for some symbol $\sigma$, $\mathit{pref}(N_\sigma)$ is regular but does not contain $\sigma'$ where symbol $\sigma'\not=\sigma$.

Any infinite prefix language is the prefix language of a nonregular language

Call a language a prefix language if any one of the following three equivalent conditions holds

• it is the prefix language of some language.
• it is the prefix language of itself.
• it is prefix-closed, i.e., it contains all prefixes of any string in itself.

Let $P$ be some language.
Claim: $P$ is an infinite prefix language $\iff$ there is a nonregular language $N$ such that $\mathit{pref}(N)=P$.

Proof:
"$\impliedby$" As a nonregular language, $N$ must be infinite. Since $N\subseteq P$, $P$ is infinite.

"$\implies$" There is a sequence of words $s_0, s_1, s_2,\cdots $ in $P$ such that for all $n$, $|s_n|=n$, $s_n$ is a prefix of $s_{n+1}$ and there are infinitely many words in $P$ that start with $s_n$. Let us prove this by induction on $n$.

• $n=0$, $s_0$ is the empty string.
  Since $P$ is infinite, it is trivially true.
• Suppose it is true for $n$.
  There are infinitely many words in $P$ that start with $s_n$. A word that starts with $s_n$ must start with $s_n\sigma_i$ for some $i$, where $\Sigma=\{\sigma_1, \cdots, \sigma_k\}$ is the alphabet. Hence for some $i$, there are infinitely many words in $P$ that start with $s_n\sigma_i$. Let $s_n\sigma_iw$ be one of them, where $w\in\Sigma^*$. Since $P$ is prefix-closed, $s_n\sigma_i\in P$. Let $s_{n+1}=s_n$ and the induction step is complete.

Consider $N_J=P\setminus\{s_i:i\in J\}$, where $J$ is a set of some odd numbers. There are uncountable many $N_J$'s. Since there are only countable many regular languages, there exists $N_K$ such that $N_K$ is nonregular. Since $N_K$ contains $s_i$ for all even $i$, $\mathit{pref}(N_K)=P$. $\quad\checkmark$

Corollary: Every regular infinite prefix language is the prefix language of a nonregular language.

Note that if the prefix language of a nonregular language is regular, it must be a regular infinite prefix language.

Answer 4

I'd take the language $(01)^n 0^m$ where m = 0 or 1, and 2n + m is a prime number. That is a string alternating between 0 and 1, and the length is a prime number. The prefix language is the regular language of alternating 0's and 1's.

You can take any regular language L and then create a language L' consisting of strings in L with certain lengths where the length restriction makes it irregular.