2
$\begingroup$

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 ?

$\endgroup$
  • 1
    $\begingroup$ You are answering your own question. Can you clarify what it is that you are not sure of? Try working out the proof to see if it works. $\endgroup$ – Yuval Filmus Jul 22 '13 at 14:32
  • $\begingroup$ "create a new NFA by making all accepting states sinks" You can replace here NFA with DFA. $\endgroup$ – sdcvvc Jul 22 '13 at 15:48
  • 1
    $\begingroup$ In your example, $A(L)$ is empty since for every $0^i 1^j 2^n$, $0^i \in L$ is a prefix. $\endgroup$ – Raphael Jul 22 '13 at 16:36
  • $\begingroup$ You can fix the example by taking $\{0^i 1^j \$ 2^n\}$ $\endgroup$ – sdcvvc Jul 22 '13 at 19:06
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Why is that so ? If the non-determinism is the problem does it imply that it won't work for NFA either ? $\endgroup$ – Robert777 Jul 22 '13 at 15:36
  • 3
    $\begingroup$ @Robert777: It won't work for NFA either, unless you determinize it first. For example, consider an automaton over unary alphabet, states A,B,C,D, transitions A -> B, B -> C, C -> C, A -> D, D -> D, initial state A, accepting states C,D. This automaton accepts all nonempty words. If you make C,D sinks the resulting language will be $\{a,aa\}$ instead of $\{a\}$. $\endgroup$ – sdcvvc Jul 22 '13 at 15:43
  • 2
    $\begingroup$ The way I understand "sink" (all outgoing edges loop back) this won't work at all. $\endgroup$ – Raphael Jul 22 '13 at 16:34
  • 1
    $\begingroup$ I assumed that as a mental shortcut by "sink" OP meant removing all outgoing edges (or pointing them to a sink in your sense). $\endgroup$ – sdcvvc Jul 22 '13 at 17:13
  • $\begingroup$ @Raphael I really did mean removing all outgoing edges, sorry if I wasn't clear about it. $\endgroup$ – Robert777 Jul 22 '13 at 18:18
5
$\begingroup$

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

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.