Are regular and context free languages closed against making them prefix-free?

Question

For a language L we define:

$\qquad A(L) = \{ x \in L \mid \text{ no proper prefix of x is in L} \} $

Are regular / context free languages closed under this operation ?

For regular languages I thought about taking the DFA that accepts the language L and create a new NFA by making all accepting states sinks (so the only way of being accepted by the automata is that when reading the last letter we reach an accepting state for the first time).

Can't we make the same thing with a pushdown automata for context free languages ?

Edit (as Raphael pointed out, the example below is wrong):

But here is a strange language that I think implies the opposite:
$L = \{ 0^{i}1^{j}2^{n} \mid i \le n \ \text{ or }\ j \le n \} $
$A(L) = \{ 0^{i}1^{j}2^{n} \mid n = \min(i,j) \} $

$L$ is context free but $A(L)$ isn't. Obviously, at least one of the things I wrote above is wrong. Anyone have any clue what is going on here ?

Answer 1

Can't we make the same thing with a pushdown automata for context free languages ?

No. Your construction needs to start with a deterministic automaton, and PDAs cannot be determinized.

Answer 2

$\newcommand{\Pref}{\operatorname{Pref}}$With $\Pref(x)$ the set of all prefixes of $x$ (note that $x \in \Pref(x)$), I assume you intended to define

$\qquad A(L) = \{ x \in L \mid (\Pref(x) \setminus \{x\}) \cap L = \emptyset$.

Now, note that

$\qquad A(L) = L \setminus ( L \cdot \Sigma^+ )$

and we immediately get that

$\qquad L \in \mathrm{REG} \implies A(L) \in \mathrm{REG}$

because regular languages are closed against concatenation and difference.

An automaton construction similar to yours works, too. Instead of making all final states sinks you have to reroute all edges leaving final states to (non-accepting) sinks, though. And you need to use deterministic automata, as otherwise only some accepting paths for non-prefix-free words may be cut short.

Towards an answer for context-free languages, we make two observations.

• $\mathrm{CFL}$ is not closed against difference¹.

• The Dyck language provides a non-trivial example, i.e. the size of both

  $\qquad A(\mathrm{Dyck} \setminus \{\varepsilon\}) = \{(^n )^n \mid n \geq 1\}$

  and its complement w.r.t. $\mathrm{Dyck}$ is infinite².

So we might guess that $\mathrm{CFL}$ is not closed against $A$ and start looking for a counter example. And indeed we find

$\qquad L = \{ a^n b^n \mid n \geq 1 \} \cup \{ a^m b^n c^n \mid m, n \geq 1 \} \in \mathrm{CFL}$

for which

$\qquad A(L) = \{ a^n b^n \mid n \geq 1 \} \cup \{ a^m b^n c^n \mid m > n \geq 1 \}$.

We can show that $A(L) \notin \mathrm{CFL}$ with Ogden's lemma.

Use $a^{2p} b^{p+1} c^{p+1}$ and mark all $b$. This ensures that $b$ have to be pumped, but not both $a$ and $c$ can be pumped; therefore pumping destroys (at least one of) the "conditions" $\#_a > \#_b$ or $\#_b = \#_c$.

---

1. That does not prove anything!
2. Showing that either $A(L)$ or $L \setminus A(L)$ is always finite would be one way to prove closure.

Answer 3

Here is a proof that context-free languages in general, not only regular ones, are not closed against making them prefix-free.

Bare with me, as I will try to make it as formal as possible.

---

We will demonstrate that:

Theorem 1. $NOPREFIX(L)$ are the $u\in L$ such that no proper prefix of $u$ is in $L$. Context-free languages are not closed under $NOPREFIX$.

First off, we will use the following three lemmas:

Lemma 1.1. If $L_1$ and $L_2$ are context-free languages, then the concatenation of both languages, $L_1.L_2$, and the union of both languages, $L_1 \cup L_2$, are both context-free.

Proof. Let $G_i$ be the context-free grammar that generates $L_i$, with starting variable $S_i$, for $i \in \{1,2\}$.

Then, a grammar that generates $L_1.L_2$ can be obtained by combining the productions of both grammars (distinguishing the variables) and adding the production: $$S \rightarrow S_1S_2$$

which is context-free, therefore being the language context-free.

Finally, a grammar that generates $L_1 \cup L_2$ is done with the same fashion: $$ S \rightarrow S_1,\;S\rightarrow S_2 $$

which is also context-free, therefore also being the language context-free.

Lemma 1.2. The language $L$, defined as: $$L=\{a^ib^ic^i \;:\; i \geq 0\}$$ is not context free. However, its complementary language, $\overline{L}$, is.

Proof. The proof that $L$ is not context-free can be easily done using the pumping lemma for context-free languages.

However, to prove that $\overline{L}$ is context-free, we must note that $\overline{L} = \overline{L_1} \cup L_2$, where:

$$L_1\;\text{is the language generated by the regular expression}\;a\text{*}b\text{*}c\text{*}$$ $$L_2 = \{a^ib^jc^k\;:\;i\neq j \;\vee\;j\neq k\}$$

$\overline{L}$ is context-free, as it is the union of two context-free languages, using lemma 1.1: $\overline{L_1}$ is regular for being the complementary of a regular language, therefore being context-free; $L_2$ is context-free for being the union of two context-free languages (the one that verifies condition $i\neq j$ and the one that verifies condition $j \neq k$).

Lemma 1.3. The language $\hat{L}_i$, defined as: $$\hat{L}_i=\{a^jb^jc^j\\\$^i \;:\; j \geq 0\}$$ is not context free for any $i \geq 0$.

Proof. Note that $$\hat{L}_i=\{a^jb^jc^j: j \geq 0\}.\{\\\$^i\}$$ is the concatenation of two context-free languages, $\hat{L}_i = \hat{L}^a.\hat{L}_i^b$, where $$\hat{L}^a = \{a^ib^ic^i \;:\; i \geq 0\}$$ $$\hat{L}_i^b = \{\\\$^i\}$$

By lemma 1.2, $\hat{L}^a$ is context-free, and $\hat{L}_i^b$ is regular, as it is finite and only has one word, therefore context-free. Using lemma 1.1, the concatenation of context-free languages is context-free, therefore being $\hat{L}_i$ context-free for every $i \geq 0$. Note that the case $i=0$ is exactly lemma 1.2.

---

Now we can prove theorem 1.

Proof. The main idea behind the proof is to find a language that is context free, whose complement is not context-free. A perfect candidate is $\overline{L} = \overline{\{a^ib^ic^i \;:\; i \geq 0\}}$, although for this proof we can use any $L_0$ that verifies that is context-free, but whose complementary doesn't, eveng when concatenating a finite amount of symbols that are not in the language's alphabet. We'll note $L_0 = \overline{L}$. Our language is part of the alphabet $A = \{a,b,c\}$, $L_0 \subseteq A\text{*}$.

Now we'll use the following language: $$L=L_0.\{\\\$\} \cup A\text{*}.\{\\\$\\\$\}$$

Where $\\\$$ is a character such that $\\\$ \notin A$. Clearly, $L$ is a context-free language, as it is formed as concatenations and unions of context-free languages (according to lemma 1.1): $A\text{*}$ is regular, therefore context-free, and every finite language is regular, therefore $\{\\\$\\\$\}$ is regular, and also context-free; on the other hand, $L_0.\{\\\$\}$ is also context-free because of the same reason.

We will see $NOPREFIX(L)$ is not context-free.

Basically, we have to see that $u\\\$\\\$$ has no prefixes in $L$ if and only if $u \notin L_0$. Indeed, if it were $u \in L_0$, then we would have $u\\\$ \in L$, because $u\\\$ \in L_0.\{\\\$\}$. On the other hand, if $u\notin L_0$, $u\\\$\\\$$ has no proper prefixes in $L_0$: it is enough to see that $u\\\$ \notin L_0$ because the only words that end in just a single $\\\$$ are from $L_0.\{\\\$\}$ (and $u \notin L_0$); of course, $u$ neither any other of its prefixes will be in $L_0$ because they do not end in $\\\$$.

Therefore, we conclude that $NOPREFIX(L)$ is not context-free, as $NOPREFIX(L)=\{u.\{\\\$\\\$\}:u\notin L_0\}=\overline{L_0}.\{\\\$\\\$\}$ which is not context-free, using lemma 1.3.

---

Hope you found it helpful. This was one of the problems from my computing models exam in University of Granada, Spain. Have a great day you all!