Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I can't figure out how to prove this is a non CFG.

$\{xy : x, y \in \{a,b\}^*, n_a(x) = n_a(y), n_b(x) = n_b(y) \}$, Where the number of a's in x = number of a's in y and number of b's in x = to the number of b's in y.

I've been able to come up with a few cases where setting

$ s = a^pb^pa^pb^p$

doesn't work.

Anything would be helpful. Thanks.

share|improve this question
    
That's clearly not a context free grammar, because it's not a grammar at all. You mean you want to prove it's not a context free language. –  Chris Eagle Nov 1 '11 at 10:43
    
@ChrisEagle yea, meant CFL. Was looking at grammars before, so i was thinking grammars. –  Matt Nov 1 '11 at 19:59
add comment

1 Answer 1

up vote 3 down vote accepted

Let $L=\{xy\in\{a,b\}^*:n_a(x)=n_a(y)\land n_b(x)=n_b(y)\}$, suppose that $L$ is context-free, and let $p$ be the critical number in the pumping lemma. Let $w_1=a^pb^p$, $w_2=(ab)^p$, and $w=w_1w_2=a^pb^p(ab)^p$. Suppose that $w=uvxyz$, where $|vxy|\le p$, $|vy|\ge 1$, and $uv^nxy^nz\in L$ for every $n\ge 0$. (Note that $uxz$ must belong to $L$: people often forget about the $n=0$ case, and it turns out to be very handy here.)

Suppose first that $vxy$ is a substring of $w_1$. It can’t be of the form $a^k$: after sufficient pumping, all of the $b$’s would be in the second half of the word. If it’s of the form $b^k$, then $uxz$, the $n=0$ case, will be of the form $a^pb^{p-2i}(ab)^p$ for some positive integer $i$. If $i$ is even, say $i=2j$, the first and second halves are $a^pb^{p-4j}(ab)^j$ and $(ab)^{p-j}$, with different numbers of $a$’s. If $i=2j-1$, the two halves are $a^pb^{p-4j+2}(ab)^ja$ and $b(ab)^{p-j+1}$, again with different numbers of $a$’s. Finally, suppose that $vxy$ is of the form $a^kb^j$, where $|v|,|y|\ge 1$. If $v=a^i$ and $y=b^j$, then the $n=2$ case of the pumping lemma will be $a^{p+i}b^{p+j}(ab)^p$; $i<p$, so the initial $a^{p+i}$ is in the first half of the word, while the second half has only $p$ $a$’s. The only remaining possibility is that one of $v$ and $y$ is of the form $a^ib^j$ for non-zero $i,j$, but this runs into the same problem as the previous case.

Now suppose that $vxy$ is a substring of $w_2$. It must be of even length (why?), so either it’s of the form $(ab)^i$ for some $i>0$, or it’s of the form $a(ba)^ib$ for some $i\ge 0$. In either event the $n=0$ case of the pumping lemma is $a^pb^p(ab)^{p-i}$, which has $p$ $a$’s in its first half and only $p-i$ in its second.

The only remaining possibility is that $vxy$ lies partly in $w_1$ and partly in $w_2$, and each of the subcases here is similar to one already handled.

share|improve this answer
    
Ok, that makes sense. Just couldn't find the right s. should have known that. Thanks. –  Matt Nov 1 '11 at 19:58
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.