Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

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

484 questions
Filter by
Sorted by
Tagged with
162 views

### Is the set of languages satisfying the pumping lemma closed under concatenation?

Let $L$ be the set of all languages that satisfy the pumping lemma, including non-regular languages that satisfy it. Is the set $L$ closed under concatenation? I couldn’t prove it or find a ...
1 vote
71 views

### Prove that the language of regular expressions is not regular

I want to prove that the language of all regular expressions is not a regular language. I'm having trouble to approach this problem. I thought maybe to show that the parenthesis language is a part of ...
55 views

### How to prove ww^r is context free using pumping lemma for context free languages

I am having a hard time to prove it, what i know is we cannot prove that a language is regular by using pumping lemma cause even if the "pumped string" is in the language the language could ...
1k views

### Is this language a context-free language or not?

I try to determine if the following statement is true: for any given language $L \subseteq A^*$ if $L$ is a context-free language then $L_1 = \{u^Rv^R \ | \ uv \in L, |u|=|v| \}$ is also a context-...
• 55
1 vote
35 views

### Why L1 := { a^n b^m | m, n ≥ 0 and m ≥ n } is regular and L2 := { a ^ n b ^ n | n>= 0 } not regular?

I understand why L2 is not a regular language. We can use the pumping lemma to prove it In the case of L2: assume n = 1 and string = ab We assume that L2 is regular, so it has "pumping length&...
243 views

### What exactly is pumping length in pumping lemma?

Pumping Lemma : For any regular language $\mathbb{L}$, there exists an integer $n$, such that for all $x\in \mathbb{L}$ with $|x|\geq n$, there exists $u, v, w \in \Sigma^*$, such that $x = uvw$, and ...
29 views

### Using the pumping lemma, show that the following languages are not regular

L1 = {c^ia^jcb^i+j|i,j∈N0} L2 = {w∈{a,b,c}∗|w=uvmit#c(v)=0und#a(u)=#a(v)}
82 views

### Show that $\{ a^c \mid c \text{ is composite}\}$ is not regular using Dirichlet's theorem

Let $L=\{ a^c \mid c \text{ is composite} \}$. Prove that $L$ is not regular using the pumping lemma. You can use Dirichlet's theorem, which states that if $(a,b) = 1$ then there are infinitely many ...
• 115
1 vote
67 views

### How does Sipser's proof that $0^n1^n$ is not regular work?

In Sipser's Introduction to the Theory of Computation this is how $0^n1^n$ is proved to be not regular Example 1.73: Let $B$ be the language $\{0^n1^n|n \ge 0\}$ We use the pumping lemma to prove ...
57 views

1 vote
33 views

### Prove that $L=\{a^n b^l : n \leq l\}$ is not regular by pumping lemma

I'm currently trying to prove that $L=\{a^n b^l : n \leq l\}$ is not regular by pumping lemma My proof: If we choose $w$ such that $w=a^P b^P$, then since $|xy| \leq p$, $y$ must be $a^P$, meaning it ...
• 111
1 vote
71 views

### Show the pumping lemma is not a universal method for proving not context-free

I know that the pumping lemma is not powerful enough to prove a language is not context-free, but I don't understand how to show it. I have the same question as this one Show that the Pumping Lemma ...
• 13
51 views

51 views

### Pumping Lemma for $\mathcal{L} = \{ \omega \omega^R a^{|\omega|} : \omega \in \{a,b\}^* \}$

I have to show that this language is not context free $\mathcal{L} = \{ \omega \omega^R a^{|\omega|} : \omega \in \{a,b\}^* \}$, where the $R$ corresponds to the reverse. For this I will use the ...
23 views

### Show that a language with union is not regular by using pumping lemma

Given the language $L:= { \{ c^{2k} w \ \vert \ k \ge 1, \ w \in \{a,b,c\}^* \ and \ \vert w\vert_a \ = \ \vert w\vert_b \} \ \cup \ \{ a,b \}^* }$ I'm really unsure how to even start because of the ...
70 views

### Minimum pumping length of finite language

Background Let L = {aa}. We know that the minimum pumping length of L is |aa| + 1 = 3. For this length all the three conditions of the pumping lemma vacuously hold true. Doubt Let L = {aa, aab}. Is it ...
91 views

### Can a non-regular language $L$ have a non regular $L^*$?

I have been looking around and i cant seem to find an example of such case that a non-regular $L$ has a non regular $L^*$. Is it possible? If so, can you provide an example of such case please?
80 views

### Prove $\{xy \mid |x|=|y|, x \neq y\}$ is not a linear language

Show the language $$L = \{xy \mid |x| = |y|, x\neq y\}$$ is not linear. I've seen and proved a pumping lemma for linear languages, mentioned here: If $L$ is linear then there exists a constant $p$ ...
1 vote
### Proving $\{ a^n b^m \mid n \leq m^2 \}$ is not context-free using pumping lemma
I am working on a pumping lemma question and trying to prove that the following is not context-free, but I can't finish the proof. The language is $$L = \{ a^n b^m \mid n \leq m^2 \}$$ Assume Demon ...