# Questions tagged [pumping-lemma]

Necessary properties of formal langagues in certain classes that rely on closure against repetition of certain subwords. Make sure your question isn't covered by applying the techniques in https://cs.stackexchange.com/q/1031/755.

554 questions
Filter by
Sorted by
Tagged with
274 views

• 57
31 views

### Pumping Lemma Contrapositive, why is this proof wrong?

I have this proof trying to show L={0}^* {1}^* is not a regular language, I know that L is regular but I don't know what in this proof is wrong. If y contains a 0 and 1 and is pumped wouldn't that ...
42 views

### How is $|xy^{2}z| < 2^{p+1}$ (Pumping Lemma application)

In the Question here it is said that $|xy^2z|<2^{p+1}$ Considering that $|x| = 0$ and $|z| = 0$, y consists of $2^{p}$. It's probably trivial, but how do I see, that $|xy^2z| < 2^{p+1}$?
• 57
29 views

### Why in the pumping lemma of a context free grammar $|vy| > 0$ and $|vxy| ≤ p$?

Let us consider the case where $p > 0$ exists and a string $|w| ≥ p$ can be divided into $uv^{i}xy^{i}z$ for each $i ≥ 0$. When we say that $|vy| > 0$ do we mean that at least one of the two ...
• 63
83 views

### Does the pumping lemma for context-free languages really require accepting a string with zero levels of nesting?

In the pumping lemma conditions for context-free grammar we have that the string can be divided into $uv^{i}xy^{i}z$, but in the case of $i = 0$, why does it still belong to the language?, is it ...
• 63
1 vote
65 views

### How to prove that $L = \{{a^{n} b^{n} c^{j} | n,j \geq 0}\}$ is a CFL?

In the text of my book it says that this language is context-free so I tried to prove that the conditions of the Pumping Lemma are fulfilled. If, for example, I take the word $aaabbbc$ I can divide it ...
• 63
42 views

### Proving a language is not regular using Pumping Lemma

So I am given the language qr where q is any combination of a's and b's. r is then the reverse of whatever q is. For example, abba is in the language because we can make a q = ab and r = ba I have to ...
23 views

### CFG PL for L=\{a^ib^j \mid j = i^2\}

where i got it from. This was weird so I wanted to try it myself because they way he did it seemed wrong. So this is my attempt is it correct? I did not add the basic parts of the pumping lemma proof ...
58 views

So this is the language that I need to prove is irregular via pumping lemma, however I am completely stuck with this and seeking some advice. The other ones I have done during my tutorial are much ...
62 views

### Proof that $\{0^m 1^n : 0\le m\le n^2\}$ is not a CFL

I am trying to prove by the pumping lemma that $L=\{0^m1^n:0\le m\le n^2\}$ is not a CFL. Here is what I have so far. Suppose for contradiction that it is a CFL and let $N$ be the pumping length. ...
• 367
438 views

### Is L={0^n 1^n ∣n≥0} context free language?

I looked through many sources which give this as an example for cfl. It also makes sense according to this: But it fails the pumping lemma test. Let's take n=5. According to the Pumping Lemma, we can ...
128 views

### Is the language regular A2 = {w1w2w3 | w1, w2, w3 ϵ {0, 1}* }? How to prove?

So I think the above language is regular. I tried using pumping lemma but pumping up or down, changes the value of w1 but has no relation with w2 or w3. The resulting string after pumping will also be ...
1 vote
713 views

### How to prove L := { a^n b^n c^m | n,m >= 0 & n != m } is not context-free?

I have following language $L:= \{a^n b^n c^m \mid n \neq m; n,m \ge 0 \}$ and would like to use proof by contradiction by applying Pumping Lemma for CFLs to show that $L$ is not a CFL. In any case, i ...
37 views

### Confused about decomposition in Context Free Pumping lemma

I am trying to decide whether the following language is context free: $$L = \{ a^nb^{3n}c^n \, | \, n \geq 0 \}$$ Assume $L$ is context-free. Let $p$ be the pumping length given by the Pumping Lemma. ...
1 vote
72 views

### Does this really define a 0L-system?

Looking through old exams I found a problem stated as the following: Define a 0L-system as a 3-tuple $S = (\Sigma, w, h)$ where $\Sigma$ is an alphabet, $h:\Sigma^* \to \Sigma^*$ is a homomorphism ...
• 13
49 views

### Doubt in pumping lema for context-free language

I have a doubt related to pumping lemma in CFL for which I dont find an answer, so I think is very easy because no one wonder about. The lemma says: My doubt is: Is there any restriction related to ...
1 vote
88 views

• 105