Re: context free languages under SCRAMBLE operation

PeterPan wrote:

TheGist wrote:

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?

Use SCRAMBLE(L) intersect a*b*c* which is equal to {a^n b^n c^n : n >= 0}.
a*b*c* is regular, CFL is closed under intersection with regular languages, {a^n b^n c^n : n >= 0} is not context free.
Hence, is not context free.

Bye
Sorry last sentence is: Hence, SCRAMBLE(L)is not context free
.

Relevant Pages