# Tag Info

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

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 ...

10

$\{\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).

10

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 ...

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

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, ...

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

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

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 Your proof is correct, and I was wrong. It took me a while to nail down where my confusion was, but with Yuval's help I think I got it. Let's consider the three languages$\qquad\begin{align*} &L_= &\!\!\!\!\!\!\!\!\! &= \{ xy \mid |x| = |y|, x \neq y \}, \\ &L_{\#} &\!\!\!\!\!\!\!\!\! &= \{ x\#y \mid x \...

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

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 The pumping lemma states that if a language$L$is regular then there exists$p$such that every word$w \in L$that is long enough ($\lvert w \rvert \ge p$) can be split as$w = xyz$such that$|y| \geq 1$.$|xy| \leq p$. For all$i \geq 0$,$xy^iz \in L$. You give an example of a language$L$and a string$s \in L$which can be split as$s = xyz$such ... 7 The problem is in the quantifiers. The pumping lemma says that any string$s$with$|s|\geq p$can be written as$xyz$such that the three properties hold. It doesn't say that every way of writing it as$xyz$that makes the first two properties hold also makes the third one hold. For the language$\{0^{2n}\mid n\geq 0\}$, we proceed as follows. First, note ... 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^...

7

You can use Parikh's theorem to prove this claim. Indeed, if such a language was context-free, then its Parikh image would be regular. But the Parikh image would also satisfy the condition (as it only talks about length of words). It's very easy to prove that no regular language can satisfy this condition (e.g. by complementing it and using the pumping ...

7

You don't need to invoke the PL directly here. Instead, we'll do a proof by contradiction. Suppose $L$ was regular, then, since regular languages are closed under complement, $\overline{L}$ is regular (where the overbar represents complement), and since regular languages are closed under intersection, $\overline{L}\cap 0^*1^*$ would be regular (where the ...

7

It's not so evident, but you can also apply the PL directly: let $p$ be the pumping length pick $w = 0^p 1^{p + p!}$ Clearly $w \in L$ The pumping lemma says that $w = xyz$ with $|xy| \leq p, |y| \geq 1$, so we have that $y$ must be "made of" $0$s; suppose that $y = 0^a\;, 0< a \leq p$; then by the PL we have: xyz = 0^{p-a} 0^{ai} 1^{p +p!} \in L\...

7

For $i \ge 0$ define $w_i = b^i aa$. For any $i,j \ge 0$ with $i \neq j$ you have that $b^i$ is a distinguishing extension for $w_i$ and $w_j$. Indeed, $w_i b^i \not\in L_2$ but $w_jb^i \in L_2$. Then the number of equivalence classes of the set $\{ w_i \mid i \ge 0\}$ with respect to the equivalence relation "having a distinguishing extension" is ...

6

Your basic idea (in particular the choice of $t$) works, but there are some issues with the "proof" as such: What is $n$? Why do you have $y=b$ have to be pumped? You have to work against all allowed decompositions of $t$! $n+i < n+2$ does indeed not work for all $i$, but that's kind of the point. Just drop that condition. I suggest you read our ...

6

The idea is that there is some partition that fulfills the condition of the pumping lemma - you do not have the choice of the x, y, and z - you have to show that there exists no x, y, and z that satisfies the conditions.

6

It's not context free for the same reason that $L' = \{w w \mid w \in \Sigma^*\}$ is not context free, and the proof below is a simple adaption of the standard proof for the language $L'$, using the pumping lemma: Choose the string $0^p1^p1^p0^p0^p1^p1^p0^p$, (which is $\omega \omega^r \omega \omega^r$ where $\omega = 0^p 1^p$). [Note 1] Now any $vwx$ whose ...

6

If you are not sure, it is probably because you want to know why. This question is frequent among students in computer science that are learning the pumping lemma for the first time and it is the cause of a lot of errors. Logic The reason is very simple. It is because of logic. I will explain it considering the pumping lemma for the regular languages but ...

6

You're on the right track. Here are a few missing details. First, note that $(a^n)^n=a^{n^2}$, so you want to prove that $L=\{a^{n^2}\mid n\ge 0\}$ isn't regular. Assume $L$ is regular. Since $L$ is infinite, there's an integer $p$ for which the PL applies, so choose $s=a^{p^2}$ and write $s=xyz$ with $|xy|\le p$ and $|y|\ge 1$. Hence, $y=a^k$ with $1\le k\... 6 The pumping length of a regular language$L$is the minimal$p$such that every word$w \in L$of length at least$p$can be split as$w = xyz$such that (i)$|xy| \leq p$, (ii)$y \neq \epsilon$, (iii)$xy^iz \in L$for every$i \geq 0$. The pumping length of$(01)^*$using this definition is$2$. Anybody claiming that the pumping length is$1\$ is either ...

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