# Questions tagged [pumping-lemma]

The tag has no usage guidance.

121 questions
2answers
918 views

### Pumping Lemma for $L= \{a^{m}b^{n}| m,n > 0 , \gcd(m,n) > 1 \}$

Let language $L= \{a^mb^n \mid m,n > 0 , \gcd(m,n) > 1\}$ above the alphabet $\Sigma = \{a,b\}$ . I need to prove by the pumping lemma that $L$ is not a regular language but I am having ...
2answers
165 views

### Prove that the language is not regular using pumping lemma

Could anyone explain me how to prove that this language is not regular using pumping lemma? I can prove easier examples but with this one I do not even know with which word i should start proving it. ...
1answer
287 views

### Pumping lemma for regular language

On an exam we got this question: Let $B = \{w \in \{a,b\}^* : w \neq w^{rev}\}$ Prove $B$ is not regular. I only got 1 of 4 pts on this question and the teachers comments are below. My solution: ...
0answers
116 views

### Searching for a proof for a variant of the pumping lemma for context free languages

So I'm trying to understand the pumping lemma for CFL ( context free languages ).I've already used it to show that a language is not contextfree and I have considered the proof of this lemma (see the ...
1answer
327 views

### proving {$a^ib^jc^k |\;j=i\;or\;j=k$} is not regular

{$a^ib^jc^k |\;j=i\;or\;j=k$} what i tried so far was first splitting it into {$a^ib^jc^k |\;j=i$} or {$a^ib^jc^k |\;j=k$} then tried to use the pumping lemma to prove it. However i couldnt get very ...
1answer
491 views

### Proving a language is not context-free (pumping lemma)

below is my attempt at applying the pumping lemma to a language to prove that it is not context-free. I am new to using the pumping lemma, especially for context-free languages. My question is, is ...
3answers
620 views

### Can I prove, using Pumping Lemma, that $L=\{ a^i b^j a^j b^k | i,j,k \ge 1 \}$ is not a regular language?

By pumping lemma, we have that for each sufficiently large $z \in L$, there exists $u, v$ and $w$ such as $z=uvw$, whith $|uv| \leq p$, $|v| \ge 1$ and $uv^iw \in L$, for each $i \ge 0.$ ($p$ is the ...
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
102 views

### Prove that a language is not regular

I want to prove that $L$ is not regular: $$L = \{ww^Rv \mid |w|\ge1 , |v|\ge 0\},$$ where the alphabet contains at least two symbols. Can someone prove it? I prefer to use "Pumping Lemma for Regular ...
2answers
333 views

1answer
47 views

### Proving that the language $\{w\in \{a,b\}^* \big|\#_a(w)< \#_b (w)\}$ is non regular using the pumping lemma

I need to prove that the language $\mathscr L=\{w\in \{a,b\}^* \big|\#_a(w)< \#_b (w)\}$ is non regular using the pumping lemma My try: $\{a,b\}^*=\{\epsilon,a,b,aa,ab,ba,bb,aaa,aab,\dots\}$ ...
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
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 ...
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 ...
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 ...