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 have decided to teach myself formal languages and so I bought Peter Linz's Formal Languages and Automata. He presents the following problem (and many similar ones) in chapter 8 section 1, and I cannot see how his solution makes sense.

(7a) Show that the language on $\Sigma = \{a,b,c\}$ given by $L = \{a^nb^j : n \leq j^2\}$ is not context-free.

While this definitely seems plausible given that this formula involves a relationship between a number and it's square, when I tried to apply the pumping lemma, I was unable to. Here is the pumping lemma for reference (you can find better explanations elsewhere, I just want to make sure we are all on the same page with the letters).

Context-Free Pumping Lemma: Given a context-free language there must exist some positive integer $m$ such that for any $w \in L$ there exists a decomposition $w = uvxyz$ with $|vxy| \leq m$ and $|vy| \geq 1$ such that for every positive integer $i$ the string $uv^ixy^iz \in L$.

Peter Linz applies the pumping lemma to solve it but he does not address the following. Given any string that obeys $L = \{a^nb^j : n \leq j^2\}$, you can always pick a decomposition such that $vxyz=b$ and $u$ is the entire first part of the string except for the last character. This works because even though there is a limit on the maximum length of $vxy$, the only limit on the minimum length is that $|vy|$ must be at least $1$.

This particular decomposition causes $b$ to be repeated indefinitely, and since $n$ was already less than $j$, as $j$ increases $n$ is still less than $j$. Hence you simply cannot use the pumping lemma to show this formulation is not context free.

Now, I could chalk this off as a simple spelling mistake, but the very next question can be disproven with similar means. This problem is the same save that he replaces the formula with $L = \{a^nb^j : n \geq (j - 1)^3 \}$. In this case the argument goes in reverse (you repeat the beginning of the string, not the end).

This led me to the following generalization: if you have any description of a language in which the language is defined by an inequality between the counting of two different letters, there is no way to use the pumping lemma to disprove it. This is because given a string that follows the formulation, you can always pick a decomposition in which one letter is repeated over and over, and if this letter is on the side side that is greater than the other side, all of the generated languages are still in $L$. This actually can be shown to work with the pumping lemmas for regular and linear languages as well without too much difficulty.

Anyway, since such a formulation was not exactly hard for me to attain and since I am a lowly undergrad and Peter Linz is a respected researcher, I was wondering if someone could explain where my understanding of the pumping lemma went awry. What am I failing to understand about this theorem?

PS: Sorry about the length, I just wanted to make sure I was clear.

share|improve this question

2 Answers 2

The problem is with your statement of the pumping lemma: it should say that $uv^ixy^iz \in L$ for all non-negative integers $i$. Now you get in trouble when you try to decompose $ab$: if you take $u$ to be $a$, $b$ must be either $v$ or $y$, and when $i=0$, $uv^ixy^iz = a \notin L$.

share|improve this answer

Your statement of the pumping lemma contains two errors.

One is that you unnecessarily restrict i to be positive (as Brian M. Scott pointed out); i is allowed to be 0, and this is important to prove that your two languages are not context-free.

The other is that you assert the conclusion for any wL, but the correct version asserts the conclusion only for wL such that |w|≥m. Without this modification, your statement does not hold.

share|improve this answer

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.