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


Proginoskes wrote:
Please don't top-post; put your response AFTER the text that you're
responding to.

On Jun 11, 2:58 pm, hamperhd <shih....@xxxxxxxxx> wrote:
The problem is i don't know how to pump this problem.

On Jun 11, 2:57 pm, Proginoskes <CCHeck...@xxxxxxxxx> wrote:

On Jun 10, 11:44 pm, hamperhd <shih....@xxxxxxxxx> wrote:

Hi all,

How to prove the following language is not context-free?

{a^i b^j | i != k*j for every positive integer k}

It is actually in Sipser's book Intro to Theory of Computation 2nd.
problem 2.33

How about trying the Pumping Lemma for Context-Free Languages?http://en.wikipedia.org/wiki/Pumping_lemma_for_context-free_languages

((Your response should go here.))

The problem is i don't know how to pump this problem.

The Pumping Lemma states that: "If a language L is infinite and
context-free, then there exists some integer p > 0 such that any
string w in L with length(w) >= p (where p is a pumping length) can be
written as
w = uvxyz with strings u, v, x, y and z, such that length(vxy) <= p,
length(vy) >= 1, and
u(v^i)x(y^i)z is in L for every integer i >= 0." (I've rewritten this
so that it's easier to follow in plain text.)

Let p be the integer guaranteed by the Pumping Lemma. Then you will
let w be a certain string with length >= p, and you'll just have to do
some work looking for a suitable w. You might start with (IMO) the
simplest case:

w = aab...b,

where the number of b's is p or p+1 (whichever is odd, so that w is in
L). Now comes an argument by cases; you have to write w as uvxyz
subject to the conditions above, but since you have 2 a's followed by
a bunch of b's, at most one of u,v,x,y,z will have both a and b in it
(which helps a lot). Some possibilities are:

(1) u = aa[and maybe b's], v, x, y, z are strings of b's (where at
most one of v and y is the empty string);
(2) u = a, v = a, and x, y, z are strings of b's;
(3) u = a, v = ab[maybe more b's], and x,y,z are strings of b's; ...

Now take the cases one by one, and find a new string that should be in
L, which you can show really isn't.

For instance, if p happens to be 5, suppose you choose w=aabbbbb. If
you try case (3) --- with u=a, v=ab, x empty, y=b, and z=bbb --- the
Pumping Lemma states that the string u(v^2)x(y^2)z is in L. But
u(v^2)x(y^2)z = a.(ab)^2..(b)^2.bbb = aababbbbbb,

which can't be in L since there is an a after a b in it. Hence, case
(3) can't happen. (In fact, you find out more, namely that neither of
v or y can contain both an a and a b.) In other cases, you might find
out (and probabily will) that your new string (concatting v and y i
times) consists of a^I.b^J, where I is a multiple of J, and this new
string can't be in L, either, even though the Pumping Lemma says it
must.

If you can eliminate all of your cases, then you have a proof. But
(and this is the bad news) you have some work ahead of yourself.

(You should also look through the section containing that problem for
any theorems of the form "If L is context-free, then L [satisfies some
condition]." If you can show [some condition] doesn't hold for your
particular L, you can bypass all this case-checking and use that
theorem. Unfortunately I don't have access to Sipser's book, as I'm on
vacation.)

Do you know for a fact that this result can be proved using the
pumping lemma, or are you just guessing? I can't see how to do it. The
difficult case is when v=a^i and y=b^j for some i and j, and I
don't see immediately how to get a contradiction in that case.

I think I can prove this result using Parikh's Theorem about context
free languages with bounded syllable length being semilinear sets, but
I doubt whether that is the intended solution.

Derek Holt.

.

Quantcast