9
$\begingroup$

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

$\endgroup$

4 Answers 4

14
$\begingroup$

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.

$\endgroup$
2
  • 7
    $\begingroup$ Even simpler: take any existing example and add an unused symbol to $\Sigma$. $\endgroup$
    – Bubbler
    Sep 15 at 5:42
  • $\begingroup$ @Bubbler Yes, you are right. That symbol can even be made "visible" in the language by prefixing it to every word in the language, so it shows up in the strings. $\endgroup$ Sep 18 at 12:39
13
$\begingroup$

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^{*}$.

$\endgroup$
3
  • $\begingroup$ Why aa* and not a*? Are you using an N that excludes 0 or something? $\endgroup$
    – Yakk
    Sep 16 at 18:20
  • $\begingroup$ @Yakk The language a^m b^mn does not contain any strings consisting of only bs, except for the empty string. b is not in the prefix language, for example. $\endgroup$
    – kaya3
    Sep 16 at 18:24
  • $\begingroup$ Oh, multiplication. Got it. I misread it as a^m b^(m+n), which of course is not at all the same. $\endgroup$
    – Yakk
    Sep 16 at 18:50
8
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ The prefix language of a regular language $R$ is regular. It is not $\Sigma^*$ iff, assuming $D$ is a definitive automaton for $R$, there is a reachable state which can not reach a final state in $D$. It is infinite iff there is a path from the start state to a final state that contains a cycle. Hence we can enumerate all regular infinite prefix languages that are not $\Sigma^*$. $\endgroup$
    – John L.
    Sep 16 at 5:25
5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Nice one; since there is only one string when m = 0, you might as well just fix m = 1 and write (01)^n 0 where 2n + 1 is a prime number. $\endgroup$
    – kaya3
    Sep 15 at 20:38

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.