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

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 ?

• 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. – Yuval Filmus Jul 22 '13 at 14:32
• "create a new NFA by making all accepting states sinks" You can replace here NFA with DFA. – sdcvvc Jul 22 '13 at 15:48
• In your example, $A(L)$ is empty since for every $0^i 1^j 2^n$, $0^i \in L$ is a prefix. – Raphael Jul 22 '13 at 16:36