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

hamperhd@xxxxxxxxx wrote:
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?

You may need to use the pumping lemma for context free languages,
http://en.wikipedia.org/wiki/Pumping_lemma_for_context-free_languages

Patricia
.

Relevant Pages

  • Re: How to prove "Cfls are not closed under shuffling"
    ... In your solution, we have one counter-example, but does that suffice? ... Because L_3 which you have constructed is a subset of shuffle, ... generated by the following CF-grammar rules: ... L3 could not be recognized by a NPA; ...
    (comp.theory)
  • Re: How to prove "Cfls are not closed under shuffling"
    ... combinations while retaining previous order. ... following definition of the shuffle operator: ... The shuffle A$B of languages A and B is the language consisting of ... interleavings of all pairs of strings. ...
    (comp.theory)