# Questions tagged [pumping-lemma]

The tag has no usage guidance.

121 questions
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 ...
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: ...
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. ...
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 ...
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 ...
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 ...
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$, ...
27 views

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

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

### Show that $\{a^i b^j c^k \mid i>j>k>0\}$ is not a context free language by using pumping lemma

$\{a^i b^j c^k \mid i>j>k>0\}$ is not a context free language. I attempted to try this, but I keep on getting stuck. I was planning on solving it like a pumping lemma question for grammar, ...
71 views

43 views

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