Re: How to prove "Cfls are not closed under shuffling"

*** DISCLAIMER:
I'm just a bachelor student and made up an incomplete prove of the
issue as a useful exercise... it may be wrong!
***

Let L1 be the defined as
L1 = {a^2m . b^m | m >= 1}
Elements in L1 are: aab, aaaabb, aaaaaabbb, ...
L1 is a CF-language, due to the fact it can be generated by the
following CF-grammar rules:
S -> aab
S -> aaSb
where S is a non-terminal symbol (and the axiom).

Let L2 be the following
L2 = {c^n . d^2n | n >= 1}
Elements in L2 are: cdd, ccdddd, cccdddddd, ...
L2 is a CF-language, generated by the following CF-grammar rules:
T -> cdd
T -> cTdd
where T is a non-terminal symbol (and the axiom).

Let & be the shuffle operator.
If I understood what such an operator actually does :-), we can
consider
L3 = L1 & L2 = {(ac)^k . (ad)^k . (bd)^k | k >= 1}

Well, L3 is not contextual-free. I did not get rid of all the details
but... the prove could look like this:
1) CF-grammar can generate all and only the languages a non-
deterministic pushdown automaton (NPA) can recognize;
2) L3 could not be recognized by a NPA (a Turing machine is needed);
-> L3 (= L1 & L2) is not CF, while L1 and L2 are. Q.e.d..

Waiting for comments,
Good morning/afternoon/evening/night to you all!
Filippo Bollini


hamperhd@xxxxxxxxx ha scritto:

Hi,

Anyone have some hints or links talking about how to prove the
following claim?

"context-free languages are not closed under shuffle operation"


thanks,

.