# 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

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

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

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

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 ... 7 There is an example, and L = \{a^nb^na^{2m}b^ka^k \mid n,m,k \in \mathbb{N}\} does the trick. We get that \sqrt{L} = \{a^nb^na^n \mid n \in \mathbb{N}\}, which is a standard example of a non-context-free language. To elaborate a bit on how to get there: CFLs can express that two numbers are the same, but not that three numbers are the same. So I want the ... 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 ... 6 That is because of the "structure" of the languages that is observed by the respective pumping lemma's. Have a look at the proofs of the respective pumping results. For regular languages the structure is linear, and for every long word there is a state that is repeated twice in the accepting computation of a finite state automaton. The string read between ... 6 Write the word s' as$$ s' = 0^{(p-\beta)} \left(1^p01^p0^{\beta} \right)0^{(p -\beta)}$$to see that it is in fact in$L$. 6 Your use of the pumping lemma is incorrect. First, to show that the pumping lemma fails to hold in the case of your string$S$(and thereby prove$L$non-regular), you would have to show that every choice of$y$fails. You've picked a specific$y$. Second,$S'$is in$L$. Simply take the whole$S'$string as$b$and let$a$be empty. Every string of zeros ... 5 Sure,$y^0$is$\epsilon$, but that does not make$|y|=0$. Consider$y=\mathit{foo}$. Here,$|y|=|\mathit{foo}|=3$, yet$(\mathit{foo})^0=\epsilon$. No contradiction –$y\$ is unchanged.

5

The pumping lemma claims that if the language is context-free, then there exists a configuration such that you can pump the string. Therefore, to prove that the language isn't context-free, you must show that pumping fails for every possible arrangement.

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