# Questions tagged [pumping-lemma]

The tag has no usage guidance.

197 questions
Filter by
Sorted by
Tagged with
38 views

### Is $L_2=\{w^*\,:\,w\in L_1\}$ where $L_1$ is regular, a regular language?

Is language $L_2=\{w^*\,:\,w\in L_1\}$, where $L_1$ is regular, regular? Intuitively it seems that it's not: the automaton accepting $L_2$ would most probably just be a loop made from an automaton ...
• 33
31 views

### How to prove that a language is not context-free using pumping lemma?

How could I realize this using the pumping lemma? What if the pumping part is between b and c or between a and b so that after pumping the word is still in L?
57 views

### My proof of $\{a^p|p~~\mathbb{is~~prime}\}$ is not a CFL.

I want to show that the language $L=\{a^p~|~p~~\mathbb{is~~prime}\}$ is not a CFL. Assuming towards a contradiction that $L$ is a CFL. Let $p$ be the number from the Pumping lemma for context-free ...
• 656
78 views

### How can I prove that L = {w ∈ {a, b, c, d} ∗ | #a(w) = #b(w) = #c(w) = #d(w)} is not context-free without using the pumping lemma?

I am stuck on this problem, I can prove it using the pumping lemma, but I'm wondering if I can also prove it using closure properties
28 views

### Prove non regularity of the language a^n where n is an even or a prime number, with the pumping lemma

How to prove that the language that is the union of the language where $n$ is an even number and the language where $n$ is a prime number is non-regular with the pumping lemma? I know how to prove ...
144 views

### Proving a language is not regular using the pumping lemma

Let $$L =\Big\{ \ ba^{2^k}b^{i_1}ab^{i_2}a\dots b^{i_k}a \ \Big|\ k\ge 1,\ i_j\ge1 \ ,\ 1\le j \le k\ \Big\}\ .$$ Using the pumping lemma prove that $L$ isn't regular. The answer given to this ...
• 373
39 views

### Pumping lemma: if you pump to $uv^0wx^0y$, wouldn't $|vx| \ngeq 1$?

For pumping lemma for CFLs, for strings $s$ in $L$, they follow the form $s = uvwxy$ and $|vwx| \leq n$, $|vx| \geq 1$, and $uv^iwx^iy \in L$ for $i \geq 0$. If I want to prove a language is not CFL, ...
• 1,713
1 vote
74 views

• 2,051
38 views

### Proof of Pumping Lemma: Why can we set the pumping constant to the number of states?

I'm learning the proof of the Pumping Lemma for regular languages. The proof is carried out using an arbitrary string having length of at least the number of states in the DFA. As such: The language ...
• 1
1 vote
198 views

### a^m b^n c^n prove it's not regular/pumping lemma

How to prove that $L = \{a^mb^nc^n \mid n, m \geq 0\}$ is not regular by the pumping lemma My attempt: Let's suppose $L$ is regular. There exists a pumping constant p, and we choose $w = a^pb^pc^p$ ...
13 views

### Pumping Lemma-prove a language is not regular

The question is to prove that the Language below is not regular, and I have used the pumping lemma technique I wanted to know if this is the correct solution so the CFG for it is let the grammer be ...
55 views

### How can the following language be regular?

Lets assume the language $L=\{a^n b^m\}$ When we try proofing $L$ is regular using the Pumping lemma and say $w=xyz$ and thus for every $w=xy^iz$ , $w$ has to be $\in L$. now if we say $y$ only ...
28 views

### Proof of context free Language

$$L:=\{w\in\{a, b, c\}^*| ∃ i, j ∈ N :w = a^i⋅b^i⋅c^j ∧ i < j\}$$ I am trying to prove/disprove that this is context free. I was sure this was not context free, since there are 3 pumping operations,...
280 views

### Prove that L={$a^p$: p is prime } is not regular using pumping lemma

https://cs.stackexchange.com/questions/145675/understanding-about-pumping-lemma-for-regular-language-confusions-of-beginner This the reference idea I have used in this proof. But I am very clear that ...
• 11
51 views

### Is it true that for every regular language $L \subseteq \{0, 1\}^{*}$ the language $\{w^{|w|} |w \in L \}$ is also regular?

Is it true that for every regular language $L \subseteq \{0, 1\}^{*}$ the language $\{w^{|w|} |w \in L \}$ is also regular? I think the language is not regular because for a finite w we can easily ...
1 vote
52 views

### Pumping Lemma for regular languages

Given is the the following language. $L= \{ wa^{\vert w \vert} \mid w \in \{a,b\}^* \cup L(b^*a^*)\}$ Task: Prove that $L$ is not regular using pumping lemma. I am not sure wether I did this ...
37 views

### Proving $\{0^m1^{2m}2^i | m > i \geq 0\}$ is not context-free using the pumping lemma

I want to prove that the language $\{0^m1^{2m}2^i\;|\;m > i \geq 0\}$ is not context-free using the pumping lemma. I know there are at least 3 contradictions that exist, all of which are when $v$ ...
42 views

### Pumping Lemma proof for this language: $L= \{a^ib^jc^{ij} \mid i, j \geqslant 0\}$

i have troubles to show that this language is not context free with the pumping lemma. As a word I chose: $a^mb^mc^{m^2}$ I solved all the cases but one, which is: "$vy$ contains $b$'s and $c$'s&...
55 views

### Use pumping-lemma to prove that L is not a context-free language

Show using the pumping lemma that L = { $w$$w^{R}$$w$ | $w\in$ {a,b}* $w\notin$ context-free language where $w^{R}$ denotes the reversed word $w$. (if $w$ = $w_{1}$$w_{2}$$w_{3}$ ... $w_{n}$ ,$w^{R}$ ...
• 1
337 views

### Is $\{a^nb^mc^{n+m} \mid n, m \geqslant 0\}$ a context-free language (CFL)??

Considering this language $L = \{a^n b^m c^{n+m} \mid n, m \geqslant 0 \}$ is it a CFL? If I can make a PDA for it can I still prove with the pumping lemma that the language is not CFL? I mean if try ...
83 views

### Check if the Language is context-free using the Pumping Lemma

$$L=\{a^ib^jc^k \mid i, j, k \in N \text{ and } i <k<j\}$$ I want to check if this language is context-free. The part that confuses me is that if I choose $$w=a^nb^{n+2}c^{n+1}$$ then one ...
• 167
58 views

### Regularity of $w^{|w|}$

Is it true that for every regular language $L \subseteq \{0,1\}^*$, the language $\{ w^{|w|} \mid w \in L \}$ is also regular? It seems to me that it is not regular , so I will try to prove it with ...
• 63
1 vote
126 views

### Prove the following languages are irregular.

Prove the following language is irregular. $$\{w^n \mid w \in \{0,1\}^*,\ n ≥ 2 \}$$ I'm trying to prove this with the Pumping Lemma, but I'm kind of confused because $w$ is a language not an ...
• 69
66 views

### Can number of states of minimum accepting automaton be equal to a constan from the pumping lemma?

Let $L$ be a regular language. Prove that the number of states of the minimum accepting automata $L$ can be equal to a constant from the pumping lemma, but any smaller number can't. From what I ...
• 43
752 views

### Proof that the language $a^nb^ma^nb^m$ is not context free using the pumping lemma.

I need a proof that the language L = {$a^nb^ma^nb^m,\:n,m\geq0$} is context free using the pumping lemma. My problem is that I can actually show the conditions of the lemma hold for this language and ...
27 views

### Pumping Lemma to prove language not regular, formatting $x$

I need help with a question/verification I'm even thinking about it correctly. I'm trying to use the PL to prove $L$ is not regular. $L = \{\{a,b,c\}^* \mid |a| < |b| \wedge |a| < |c|\}$. This ...
### Why doesn't $|uv|\le k$ break the pumping lemma?
Let $N = \{ab^x | x \in\mathbb{N}\}$. Let the pumping length be $k$. So $ab^k$ belongs to $N$. Let $u = a, v = b^k, w = \operatorname{empty}$. Then $|uv|\le k$ does not hold. No other splitting I can ...