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

Thanks filip*,

acturally i have constructed a similar counter-example as yours.
However, the result of shuffling is a like a set of all possible
combinations while retaining previous order. eg.

shuffle $ab$ with $cd$ may get

abcd, acbd, cdab

In your solution, we have one counter-example, but does that suffice?
Because the subset of a CFL is not necessarily c.f.

Because L_3 which you have constructed is a subset of shuffle, does
that suffice to prove the claim?

thanks again:)















On Apr 16, 12:00 am, filippoboll...@xxxxxxxxx wrote:
*** 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

hampe...@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,


.