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

463 questions
Filter by
Sorted by
Tagged with
50 views

### Proving language is not context-free with pumping lemma

I'm trying to prove that this language is not context free using pumping lemma. I am having difficulty as to where to even start on this. $$\{c^{2i} d^j b^{2j} d^k c^{3j} \mid i,j,k \ge 0\}$$
33 views

43 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 ...
20 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 ...
49 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 ...
32 views

### Prove $L =\{0^{2^n}\mid n \geqslant 0\}$ is not context free [duplicate]

Here $0^j$ means $0$ repeated $j$ times e.g. $0^2$ is $00$. So to prove this I was asked to use the pumping lemma. So let $m$ be the pumping length and assume $L$ is a CFL by contradiction. We can ...
81 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?
65 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$ ...
55 views

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

52 views

64 views

### How to prove a language isn't necessarily regular? [duplicate]

Assuming we have a regular language $L$, how can we prove that $L'= \{ xz \mid \exists y : xyz \in L \text{ and } |x|=|y|=|z|\}$ isn't necessarily regular. So far I can't come up with much for how to ...
34 views

### Subexponential size of string to prove $\{xy : x,y \in \{0,1\}^\star, |x| = |y|, x \ne y\}$ is not regular?

In the standard proof of this language not being regular using the Pumping Lemma for Regular languages, one picks $0^p 1^p 0^{p+p!} 1^p$ where $p$ is the pumping constant and using that can derive the ...
99 views

### Is $L:=\{a^k \mid k \text{ is prime}\}$ regular?

For this exercise the pumping lemma should be used. My instructor gave me a tip it should start with $w:= a^{prime(n)}$ where prime is a while program returning the nth prime number. This does make ...
Looking at the pumping lemma, I've noticed that in the string $xy^pz$, there seems to be no rule explicitly stated for $x$ and $z$. If I understand correctly, $x$ and $z$ are basically anything on the ...