Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Please help me understand, and if possible, tips, to determine a pumping length $K$.

Suppose I have the example :

Let $G$ be a Context-Free-Grammar with a set of variables $\{S,A,B,T\}$, set of terminals $\{0,1\}$, start variable $S$, and rules:

$$\begin{align}S&\to ABA \mid SS\\ A&\to S0 \mid 1C1\\ B&\to S1 \mid 0\\ C&\to 0 \end{align} $$

Now given the above, how would I give a suitable pumping length $K$, and please explain how you actually got it from $K$.

Thank you, learning this would be of great help. This is NOT HOMEWORK.


share|cite|improve this question
Have you read the proof of the pumping lemma? That should presumably tell you how to find the pumping length for any context-free grammar. (I haven't read it myself for years, so I can't promise it does, but that's where I'd start.) – Tara B Apr 10 '13 at 21:40
@TaraB Yes I read it 22 times, still no help. – Gaak Apr 10 '13 at 23:23
Was it no help because the proof doesn't say how to derive the pumping length from the grammar, or because you didn't completely understand it? (It's hard to tell which from the fact that you read it 22 times.) I'm at a conference right now and can't help, but if this question is still unanswered by the end of the week I can probably give it a go. – Tara B Apr 11 '13 at 9:13
By the way, why do you want to know how to compute the pumping length? It's not something I have ever needed to do, since just knowing it exists has always been enough to prove what I want to prove about the languages (in the cases where the pumping lemma helps). – Tara B Apr 11 '13 at 9:14

Your Answer


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

Browse other questions tagged or ask your own question.