# 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

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

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

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

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

The first condition, i.e. $|y| \geq 1$, is clearly necessary if you want to say something interesting: for $y = \varepsilon$, $xy^iz \in L$ trivially and always holds. The second condition, i.e. $|xy| \leq p$, is "arbitrary": the lemma still says something interesting if you drop it, and it is still true because the statement becomes weaker. But remember ...

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

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 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 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 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 intersectL$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

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 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 \... 6 They way I read the question for the first time, I understood k to be a fixed parameter. Define the following languages, for k\ge 1:L_k = \{ a^ku \mid u\in \{a,b\}^* \text{ andu$has at least$ka$'s }\}\tilde L_k = \{ a^ku \mid u\in \{a,b\}^* \text{ and$u$has at most$ka$'s }\}$$The difference is that for any$L_k$,$k$is only one ... 6 Consider the language of words over$\{a,b\}$consisting of words with an equal number of$a$s and$b$s. This language is context-free but not regular. To show that it is not regular using the pumping lemma, you start with the word$a^pb^p$and pump$y$, which must consist solely of$a$s. Without condition (2), this wouldn't work: you can pump$ab\$ (in the ...

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