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 ?
Are regular and context free languages closed against making them prefix-free?
formal languages;regular languages;context free;closure properties
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.