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 am trying to prove that $L=${$a^mb^n | n=m^2$} is not a CFL with the help of the pumping lemma for CFL's.

I chose $w=a^mb^{m^2}$ = $a^{m-S}a^Sb^Tb^{m^2-T}$ $\in L$

And now in order to contradict the pumping lemma assumption I am looking for $i$ such that $a^{m-S}a^{S^i}b^{T^i}b^{m^2-T}$ $\notin L$ for $i>=0$.

Is it possible to find such value of $i$ ? How do i prove that $b^{m^2-T+Ti}\neq b^{(m+1)^2}$ or $a^{m-S+Si}\neq a^{m+1}$ ?

share|improve this question
add comment

1 Answer

up vote 3 down vote accepted

You’re not using the pumping lemma correctly: you’ve not mentioned the pumping length, you’re not allowed to specify a particular breakdown of $w$ into five (not four) pieces, and you only have to show that there is at least one $i\ge 0$ such that $uv^ixy^iz\notin L$ (where $w=uvxyz$ with appropriate restrictions). I’ll do most of a correct argument and leave just the last bit for you.

Assume that $L$ is a CFL, and let $p$ be a pumping number for $L$. Let $w=a^pb^{p^2}$. By the pumping lemma we can decompose $w$ as $uvxyz$ so that $|vxy|\le p$, $|vy|\ge 1$, and $uv^ixy^iz\in L$ for all $i\ge 0$. There are three cases that have to be considered:

  1. $vxy=a^n$ for some positive $n\le p$.
  2. $vxy=a^mb^n$ for some positive $m$ and $n$ such that $m+n\le p$.
  3. $vxy=b^n$ for some positive $n\le p$.

In cases (1) and (3) you should have no trouble seeing that if $i\ne 1$, then $uv^ixy^iz\notin L$; only case (2) requires any real work.

Suppose, then, that $vxy=a^mb^n$ for some positive $m$ and $n$ such that $m+n\le p$. If $v$ contains a $b$, it’s easy to see that $uv^ixy^iz\notin L$ when $i>1$, since $v$ contains $ba$. Similarly, $y$ cannot contain an $a$. Thus, there are $r,s\ge 0$ such that $v=a^r$, $y=b^s$, and $r+s\ge 1$; of course $x=a^{m-r}b^{n-s}$. Then for $i\ge 0$ we have $$uv^ixy^iz=\underbrace{a^{p-m}}_u\underbrace{a^{ir}}_{v^i}\underbrace{a^{m-r}b^{n-s}}_x\underbrace{b^{is}}_{y^i}\underbrace{b^{p^2-n}}_z\;,$$ which is in $L$ iff

$$(p-m+ir+m-r)^2=n-s+is+p^2-n\;,$$ i.e., iff

$$\big(p+(i-1)r\big)^2=p^2+(i-1)s\;.$$

Let $k=i-1$ and multiply out and simplify to get $2kpr+k^2r^2=ks$. Thus, either $k=0$, or $2pr+kr^2=s$. Use this to show that there is at most one value of $i$ different from $1$ such that $uv^ixy^iz\in L$, and conclude that $L$ is not context-free; you’ll want to recall that $r$ and $s$ are not both $0$.

share|improve this answer
    
Thank you again..! –  Yoni Hassin Jan 13 '13 at 17:26
    
@Yoni: You’re welcome! –  Brian M. Scott Jan 13 '13 at 17:30
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.