Re: context free languages under SCRAMBLE operation

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
.

Relevant Pages