# Questions tagged [pumping-lemma]

The tag has no usage guidance.

121 questions
0answers
6 views

### Prove L = a^n b^m c^(max(n,m)) is not regular with pumping lemma

I have the language L = a^n b^m c^(max(n,m)) and I have to prove it is not regular by using the pumping lemma. I don't understand how to do it. If I have m>n, c should be ^m. Now I take the v string ...
0answers
17 views

### Proving language is not context free using pumping lemma

Hi I'm completely stuck on an exercise which is to prove this language is not context free using pumping lemma for context free languages: ...
0answers
18 views

### Understanding the pumping lemma for CFL

I'm having a hard time with understanding the pumping lemma for CFL. I found this online and can't wrap my head around how it works. ...
1answer
27 views

### L = { u#w | u != w} context-free

So i am trying to proove that L = { u#w | u != w } (from {a,b}* ) is not a contex-free language. With the pumping lemma i tried a^p # a^r , but how can i pump so they would become equal. Or can I ...
1answer
27 views

1answer
23 views

### Proving a Context Free Language

I need to prove whether a Language L = $a^ib^jc^k$ ( with i = j x k ) is context Free. I am using the pumping lemma to prove that this is not a CFL. Currently I have been able to prove in the ...
3answers
62 views

### Prove that the language L is not a regular language, using pumping lemma

I have a language $L$: $$L = \{w : a^ib^j; i > j \}$$ I need to prove this language is not regular using Pumping Lemma. I'm wondering if I'm doing it correctly: I need to find a suitable $w$, ...
1answer
28 views

### Pumping lemma L={$a^i$ $b^j$, / 0<j<i<infinity}?

How to prove that above language is not regular. I tried using pumping lemma but am not able to prove and what to select as initial string. I also searched for other answers but this question is not ...
0answers
36 views

1answer
18 views

### How to determine the beginning of $uv^iw$ in the pumping lemma for regular languages?

Let $\sum=\{a,b,c,d\}$, $L=\{a^ib^jcd^k \big| i\ge0; k>j>0\}$. Prove that $L$ is not regular using pumping lemma. We can choose the word $Z=a^0b^{n}cd^{n+1}=b^{n}cd^{n+1}\in L$. Let $uvw$ be ...
0answers
71 views

1answer
43 views

1answer
136 views

### Prove that $L= \{w|$ $w$ ends with a palindrome of length greater than or equal to $4\}$ is nonregular using the pumping lemma.

The alphabet is $\{a, b\}$ Hi, I tried this: Assume to the contrary that $L$ is regular. Let $p$ be the pumping length given by the pumping lemma. Let $s$ be the string $a^{p}ba^{p}$. Because $s$ is ...
1answer
36 views

### Language that is CFL by Odgen but not by pumping lemma

I recently studied about Odgen's lemma and the pumping lemma. I deduced that Ogden's lemma is a general form and was interested: Is there a CFL language by Odgen's but not by the pumping lemma?
1answer
51 views

### i really don't know how to get $s = xyz$ for pumping lemma for this language

Let $L=\{a^i b^j c^k d^l : i, j, k, l > 0, 3(i+j) \geq 2(k+l)\}$. Proof that this language is not a regular language. I have no clue, cause i can't find any example for $3(i+j) \geq 2(k+l)$ or ...
1answer
38 views

### $A= \{w \in \{a, b\}^∗ \mid \text{length of$a \leqslant 5$and length of$b \leqslant 20$}\}$

I came across this proof-question to check the regularity of the following language: $A= \{w \in \{a, b\}^∗ \mid \text{length of$a \leqslant 5$and length of$b \leqslant 20$}\}$ I tried first ...
0answers
59 views

### Pumping lemma: Convert pumped, binary string $xy^iz$to integer

I am trying to use the pumping lemma to prove that the language consisting of the set of $0$'s and $1$'s, beginning with a $1$, such that when interpreted as an integer, that integer is prime, is not ...
0answers
32 views

### Proving that $L=\{xww^r\mid x,w \in \{0,1\}^+\}$ is not regular

In the alphabet $\Sigma=\{0,1\}$, I need to prove that this language is not regular. I've tried using the pumping lemma, choosing the string $a(ab)^p(ba)^p$ for a given $p$, any possible choose of a ...
2answers
63 views

### is a fractional i allowed in pumping lemma??

I checked the pumping lemma in many books(introduction to the theory of computation Michael Sipser) and website(wikipedia). they all give the same explanation:(definition from introduction to the ...
1answer
64 views

2answers
117 views

### Prove that a language is not context free

I was solving some hard exercises on context free grammer. Consider the language L={w∈{a,b}^{*} :the length of the longest substring of all b’s in w is longer than any of the length of substring of ...