The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Tag Info

Hot answers tagged pumping-lemma

29

You are right - we cannot allow "pumping" words of a finite $L$. The thing you are missing is that the lemma says there exists a number $p$, but does not tell us the number. All words longer than $p$ can be pumped, by the lemma. For a finite $L$, it happens so that $p$ is larger than the length of the longest word in $L$. Thus, the lemma only holds ...

18

You can't. The pumping lemma can only be used to prove that a language is non-regular. How to prove that it is regular depends on how you've defined regular languages. You (or your course or textbook) might have defined them as any of languages described by regular expressions; languages accepted by deterministic finite automata (DFAs); languages accepted ...

17

The pumping lemma can be stated to take into account the number of states in the DFA. Every language $L$ accepted by a DFA with $p$ states satisfies the following pumping lemma: Each word $w$ of length at least $p$ can be broken up as $w=xyz$, where $|xy| \leq p$ and $|y| \geq 1$, such that $xy^iz \in L$ for all $i \geq 0$. You can use this ...

16

The pumping lemma states a proprety of regular languages: If $L$ is a regular language then there exists an integer $p$ such that if $w \in L$ has length at least $p$ then it can be written as $w = xyz$, where $|xy| \leq p$, $y \neq \epsilon$, and $xy^iz \in L$ for all $i \geq 0$. Unfortunately, this property doesn't characterize regular languages. That ...

13

Your PDA would also accept strings of the form $a^nb^ic^j$ where $i+j=2n$ and $i,j>0$. For example the string "aaabbbbbc" is accepted. There is no way to tell that there are exactly $n$ $a$'s still remaining on the stack once you've finished reading the $b$'s.

13

The classical example is $L = \{ a^i b^j c^k : i,j,k \text{ all different} \}$. Wise shows in his paper A strong pumping lemma for context-free languages that neither the Bar-Hillel pumping lemma nor Parikh's theorem (stating that the set of lengths of words in a context-free language is semi-linear) can be used to prove that $L$ is not context-free. Other ...

13

Both pumping lemmas have an intuitive explanation in terms of an automaton that can recognize a language. A regular language can be recognized by a finite automaton. All words are recognized through: either a finite path through the automaton: words that are shorter than the pumping length; or a path that goes through a node at which there is a loop, in ...

12

Yuval's answer is great. A simpler formulation of what he's described is that finite automata cannot count arbitrarily high, and the amount they can count to is bounded by the number states in the automata. More precisely, for an automata to count to $p$, it needs $p+1$ states (one state would be $0$). This is, in essence, the entire idea behind the pumping ...

11

The main property of DFA's/NFA's is the lack of unbounded memory. If you look at a language and the only algorithm (which should later be translated into a Finite Automaton) you can think of requires this property, that is, you feel that any algorithm that recognizes it will need to remember an arbitrary large number of things (like $n$ in your example) then ...

11

The pumping lemma states that: there exists a pumping length $p$ such that for any word $w \in L$ of length $|w| \ge p$, there exists a decomposition $w = xyz$ meeting certain properties. There are two errors in your proof. The first is that the lemma states that there exists a pumping length $p$ but doesn't say how to compute it; you assume without proof ...

10

Your concatenation idea doesn't work. Although the concatenation of two regular languages is guaranteed to be regular, the concatenation of a regular language and a non-regular language is not guaranteed to be non-regular. For example, take $L_1=\Sigma^*$, $L_2=\{a^nb^n\mid n\geq 0\}$. $L_2$ is not regular but $L_1L_2=\Sigma^*$ is regular. To prove that $S$ ...

9

Your proof is incomplete, there are many cases you don't cover. You are not ruling out, for example, $u = 0^{m/2-3}$, $v=0$, $x=00$, $y=00$, $z=0^{m/2-2}$. A good hint that your proof is wrong is that all you're using about prime numbers is that they're odd¹. Odd numbers do form a context-free language. The pumping lemma gives you $uvxyz=0^p \in L$ and for ...

9

It's not needed for the proof. You can prove the lemma without this condition. Adding this condition makes the statement stronger and so more useful. The intuition here is that if a DFA has $p$ states and there is a list of $p+1$ of them, then the list must contain two states which are the same. The string $x$ is the part that stretches from the beginning ...

9

Raphael is right: you can use a quite standard pumping argument. David Richerby is also right: your argument does not work in this way. However ... If you want to have a result about closure of non-regular languages you can consider this one. Theorem. If $L_1$ and $L_2$ are nonempty languages over disjoint alphabets, then their concatenation $L_1L_2$ is ...

8

You can't deduce that $uv = a^{k^2}$, all that the pumping lemma gives you is that $|uv| \leq m$. Not all numbers less than $m$ are squares. Not only that, but even supposing that $uv = a^{k^2}$, there is no reason to assume that $v = a^{2k-1}$; all the pumping lemma gives you is that $v$ is non-empty. Finally, in order to get a contradiction, it is not ...

8

Hint: Solution:

8

Take $k=1$. No need to go further, any more $a$ can be absorbed by $u$ without risk. So you need $u$ to have at least 1 $a$ and only $a$'s or $b$'s. Therefore, $L_1$ is described by $a(a|b)^*a(a|b)^*$ and is regular. For the side question (at most $k$ $a$'s, let's call that language $L_2$), you can reason in a similar fashion to get $u$ as small as ...

8

There is a Pumping Lemma specifically for DCFL, under the title "A Pumping Lemma for Deterministic Context-Free Languages", by Sheng Yu; Information Processing Letters 31 (1989) 47-51, doi 10.1016/0020-0190(89)90108-7. With this explicit title I must apologize that I missed it! The online copy unfortunately has a blank spot in one of the formula, so I hope ...

8

Even simpler: $\{a^m b^n c^n d^n\colon m \ge 1, n \ge 1\}$. Can always pump the $a$s; intersection with the regular $\mathcal{L}(a b^+ c^+ d^+)$ gives a non-CFL (and that can be proved by pumping lemma).

8

$\{\lambda, a, a^2, \dots, a^n\}$. All states in which these words are accepted must be different, in order to avoid loops (and stay finite).

8

Here is some evidence that there is no pumping lemma for the context-sensitive languages. Of course, an answer hinges on the question what constitutes a pumping lemma. The weakest reasonable definition I could think of is this: A language class $\mathcal{C}$ has a pumping lemma if there is a decidable ternary predicate $P(\cdot,\cdot,\cdot)$ where P(g,w,d)... 8 It's a "trick" question. The language is regular because \begin{align*} \{aba^{\mathrm{R}}\mid a,b\in\{0,1\}^*\} &= \big\{\varepsilon b\varepsilon^{\mathrm{R}}\mid b\in\{0,1\}^*\big\} \cup \big\{a b a^{\mathrm{R}}\mid a\in\{0,1\}^+,\ b\in\{0,1\}^*\big\}\\ &= \{0,1\}^* \cup \big\{a b a^{\mathrm{R}}\mid a\in\{0,1\}^+,\ b\in\{0,1\}^... 7 Pumping lemma is usually used on infinite languages, i.e. languages that contain infinite number of word. For any finite languageL$, since it can always be accepted by an DFA with finite number of state,$L$must be regular. According to wikipedia (http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages#Formal_statement), pumping lemma says:$\...

7

You're right, the superscript in this context means concatenation. To prove a language isn't regular, you use the fact that any regular language can be "pumped". First, find out what "pumping" a word means (I can't do your homework for you), and then show that your language can not be pumped, and thus, can not be regular. Basically you will take a ...

7

Not all non-regular languages fail the test of the pumping lemma. Wikipedia has an annoyingly complex example of a non-regular language which can be pumped. So even if a language is non-regular, we may not be able to prove this fact using the pumping lemma. But it turns out we can use the pumping lemma to prove your first language is not regular. I'm not ...

7

You can force the pumping to be in some places, using Ogden's lemma, for example by marking all the 0's. Suppose it is context free, then Ogden's lemma gives you a $p>0$, you give it $w=0^p1^p2^p$ which is in the language, and you "mark" all the 0's. Then any factorisation $w=uxyzv$ must be such that there is a $0$ in $x$ or $z$. You can also assume $x=a^... 7 Any finite state automaton that accepts an infinite number of words will necessarily have a loop in it. One such loop may go from state$q$to state$q$consuming word$y$– that is,$y$is the word based on the symbols on the transitions going from$q$back to$q$. The pumping lemma says, more or less, that you can get to such a state$q$from the initial ... 7 I'm not sure why the answer of Karolis doesn't satisfy you. Let me chew it a bit more for you. First, let's recall what the pumping lemma says (taken form the credible source of Wikipedia): If a language L is context-free, then there exists some integer p ≥ 1 such that any string s in L with |s| ≥ p (where p is a "pumping length") can be written as s ... 7 Note [2019-07-30] The proof is wrong ... the question is more complicated than it sounds. After a failed attempt here it is another idea. If we intersect$L$with the regular language$L_{reg} = 0^*10^*10^*10^*$we get a CF language. Perhaps we can have more luck if we use$L_{reg}' = 0^*10^*10^*10^*10^*$(a string with exactly 4 1s). Let$L_1 = L \cap ...

7

Let $p$ be the pumping length, and choose a prime $q > p$. The word $a^{q^2}$ is in $L$, and so it can be written as $a^{q^2} = uvwxy$ so that $|vwx| \leq p$, $|vx| \geq 1$, and $uv^iwx^iy \in L$ for all $i \geq 0$. If $|vx| = \ell$ then $1 \leq \ell \leq p$, and for all $i \geq 0$, $q^2 + (i-1)\ell$ is composite. Since $\ell \leq p$ and $q$ is prime, \$(q^...

Only top voted, non community-wiki answers of a minimum length are eligible