Re: context free languages under SCRAMBLE operation

David Wagner wrote:
The language containing strings like
cabcab
is obviously regular, however we know from a previous result that
strings of the form a^nb^nc^n n>=0 are not context free.
Is that a sufficient proof?

No. Let L = (cab)^*. SCRAMBLE(L) != {a^n b^n c^n : n >= 0}.

Why not? Certainly there exists a permutation of, say, cabcab that looks like aabbcc (n=2), no?
.

Relevant Pages