# Questions tagged [pumping-lemma]

The tag has no usage guidance.

37 questions
116 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 ...
326 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 ...
87 views

### General question about pumping lemma statement for regular languages

According to the formal statement of the lemma here: https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages It is written at (3) that for all $i≥0, xy^iz∈L$. Until this ...
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 ...
22 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 ...
89 views

### Finding string in Pumping Lemma

I'm trying to prove that the Language $L_1$ = $\{1^m :$ m is not a perfect square$\}$ is not regular. I proved before that L = $\{1^m :$ m is a perfect square$\}$ is not regular, I thought that I ...
309 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 ...
80 views

### Pumping lemma proof and minimum length

What is the minimum pumping length for L=(0+1)1*0 ? I'm guessing it's 2 (since it's shortest word is 00), but how do I then split into word = xyz and pump it so that it still stays in?
397 views

### How to calculate the minimum pumping length for some L?

Prove that the following language holds the pumping lemma for context-free languages: (Although it is not context-free) L is a language under alphabet {a,b,c,d} L={$a^ib^ic^j$ : i,j $\ge$ ...
36 views

### Given language, say if it is regular, context-free and proove it.

I have the following language: $L = \{a^{2m + k}b^{3n+\ell}c^{m+n} \mid \ell\leq3 \space\text{and}\space k\gt2\space\text{and}\space m,n \in\mathbb{N}\}$ Is it regular? Is it context-free? What I ...
399 views

### prove that l={w ∈ {0, 1}*: n0(w) ≠ n1(w)} is a non regular language?

I tried doing this, but kept failing to prove. I know how to prove that the language is nonregular when n0(w) = n1(w). The following is the proof for n0(w) = n1(w) using pumping lemma: ...
29 views

### Proving that a certain language is or is not regular using pumping lemma

I have a language defined by $L = \{ a^{m}b^{n}:m,n \in N_{0}\}$ This means I have 3 cases: $1) \ m > n$ $2) \ m < n$ $3) \ m = n$ So I have to prove it in 3 different cases. Taking case 1 ...
266 views

### Pumping Lemma problem solved, but explanation appreciated. (Finite automata)

I have a problem that a friend helped solve but I did not entirely follow the explanation. I would hope someone could break it down for me. I understand the gist of the PL, but I do not understand how ...
101 views

### Pumping Lemma - non regular

Can everyone help me to show that: the language $$L = \{a,b\}^* \setminus \{a^m b^{2m} a^n\mid m,n \ge 0\}$$ is not regular. I don't know what is the meaning for the proof.
44 views

### What exactly is a pumping lemma and how do you do one

So I have a pumping lemma question A{www|w ∈ {a,b}*} I have the correct answer but I'm not fully sure how it works. I'll give the answer just so people know what I'm going with Assume A is REG let p ...
182 views

### Pumping lemma for context free. How do I define the string 'w' and define cases?

I am new to the pumping lemma for context free grammars. I have read books and researched online about the pumping lemma, however I am finding it difficult to understand the actual concept and how to ...
114 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 ...
70 views

40 views

### Verification of “Prove/Disprove that the language $L = \{ a^kba^{2k}ba^{3k} | k \geq 0\}$ is context free.”

I attempt to show that the language $L = \{ a^kba^{2k}ba^{3k} | k \geq 0\}$ is not context free by applying the Pumping lemma for context-free languages. This is achieved by a proof by ...
31 views

### How to prove that $L=\{a^kb^mc^{m-k}|m\ge k\ge0, m-k\ge k\}$ is not context-free language?

Prove that $L=\{a^kb^mc^{m-k}|m\ge k\ge0, m-k\ge k\}$ is not context-free language. We can suppose by contradiction that $L$ is context-free and choose $Z=a^kb^{2k}c^k$. Using pumping lemma, $vwx$ ...
30 views

### Why is this choice of $y$ not permitted in using pumping lemma?

Consider this snippet shown below from, An Introduction to Formal Languages and Automata 6th Edition by Peter Linz. As per the text, choosing a value of $y = a^k$, where $k$ is odd is not permitted ...
26 views

### To show that language is not regular using pumping lemma

L = $\left \{ a^{n}b^{n} : n \geq1 \right \}\cup \left\{a^{n}b^{n+2}: n \geq1\right \}$      L = $\left \{ a^{n}b^{n}(\lambda+bb) : n \geq1 \right \}$      Assuming L is a regular language. Let p be ...
I have language $L =\{ a^{3i} : i \in N_{0}\}$ if we choose sentence $a^{3p}$ We can decompose it such as $x = a^{k}$ where k >= 0 $y = a^{l}$ where l >= 1 $z = a^{m}a^{3p-p}$ where m >= 0 ; k +...
I have these two questions regarding the pumping lemma which, I do not quite fully understand. I was hoping someone can guide me through these questions. $PRIME$ = {$a^i$ where $i$ is a prime number} ...