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

549 questions
Filter by
Sorted by
Tagged with
1 vote
43 views

### A proof that $a^n b^m$ for $n\neq m$ is not regular by using the pumping lemma

I am looking at $L=\{a^nb^m |n\neq m \}$. I would like to prove that $L$ is not regular. This can easily done by assuming it is regular and looking at $\overline L$, or by using other theorems. ...
• 445
1 vote
33 views

### Parse tree choices for proving the pumping lemma for CFL

I was studying pumping lemma for CFL and in the proof it says that, we choose the shortest parse tree if there are multiple parse trees and we also choose $R$ the repeating variable such that it's the ...
• 69
73 views

### Deciding if a language is CFL or in $P$

I'm trying to decide whether $L_c=${$w=uxu, | \ u,x\in \Sigma ^* \ and \ |u|=c$} for some constant $c\in \mathbb{N}$ is context free or not. initialliy, I've thought about choosing $x=\epsilon$ ...
• 355
1 vote
388 views

### Proving that L = {x ∈ {a, b}∗ | na(x) < nb(x) < 2na(x)} is not a context free language

I've been working on proving that this language L = {x ∈ {a, b}∗ | na(x) < nb(x) < 2na(x)} is not Context Free. "na(x)" stands for "number of ...
267 views

### Pumping Lemma Applied to 3 Variables

Prove That the Language $L_1 = \{0^i1^j0^k | i < j\ or\ i > k\}$ is not regular using the pumping lemma. I am not sure how to begin with this I ended up using the string: $0^p1^{p+1}0^{p+1}$ S = ...
• 23
34 views

### How to handle odd word

Given the language $L = \{ a^n | \text{n is odd} \}$ I'm looking for a word $w$ using $p \in \mathbb(N)$. For example, if it would be even, instead of odd I'd choose $w = a^{2p}$. But with odd, I'm ...
• 57
365 views

### How to handle multiple exponents (Pumping-Lemma)

Example $L = {(ab)^na^k|n\ge k}$ When searching for a word $w$, using $p \in \mathbb{N}$, for instance $(ab)^pa^p$, but wanting to pump $a$ (which is not possible because $|xy| \le p$ holds), how do I ...
• 57
44 views

• 105
56 views

### regular languages under intersection and union, a bit of confusion to clarify

Let's assume that $L_1 = a^nb^{2n}$ and $L_2 = a^na^{2n}$, knowing that $L_1$ is not regular, and $L_2$ is. We also know that regular languages are closed under intersection and union, and complement. ...
• 105
48 views

### prove $a^nb^nc^m; n,m \geq 0$

I proved this language $L = a^nb^nc^m; n,m \geq 0$ is not regular the following way: Let $L \cap a^*b^* = a^nb^n$ We know that $a^nb^n$ is not regular, and $a^*b^*$ is regular. Thus, if $L$ is ...
• 105
1 vote
575 views

### Prove $a^nb^{n^2+n}$ is not regular by the pumping lemma

I want to prove this language $L=\{a^nb^{n^2+n}:n\in\Bbb N\}$ to be nonregular by the pumping lemma. This is my attempt, is this a correct way of doing it? Let's suppose $L$ is regular. Let \$s = a^kb^{...
• 105
41 views

### Is a^n , n = 3j+4k , n>=0, a context-free language?

I have no idea how to approach this question... How would I go about proving or disproving this? any explanation is appreciated.
41 views

### Is a^n b^k , 0 <= n <= k^2, a context-free language?

I don't think it's a CFL, but I'm having a hard time using the pumping lemma to prove this. Is there any way I can use homomorphism? Maybe h(a)= a, h(b) = lambda... If the pumping lemma is more ...