# 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
75 views

### Prove that $L = \{a^rb^qc^q\}$ where $q > 0$, $r \geq 0$ is not a regular language

I've been working on this question for a few hours now and I've been trying to figure out the question above. My biggest problem is that I don't know what to do with the $>$ and $\geq$ symbols when ...
• 1
32 views

### Determining class of language with pumping lemma?

I have the language $L = \{ 0^{2l} 1^m | l,m >= 0 \} \ where \ \Sigma= \{0,1\}$ which I am trying to find the class of language for, e.g. not context-free, context-free, regular. By this notion I ...
33 views

### Show non regularity of a language using closure property

Show that the language $\{0^n1^m0^n| m,n\in \mathbb{N}\}$ is not regular using closure properties. I tried showing this using pumping lemma but I am stuck when it comes to closure properties. Please ...
54 views

### Context free language with valid Pumping Lemma use

Is this language context free? $L = \{a^kb^lb^ka^l \ | \ k,l \in \mathbb{N}\}$ Using Pumping Lemma and $z = a^nb^nb^na^n$ I find it contradicting PL. If $z = uvwxy$ and $|vwx| \leq n$, follows: $vwx$...
61 views

### Help with understanding a stipulation in pumping lemma

I have an example problem we are doing where we have xy. The special string I picked for the specific question was 0^p 1 1 0^p. My question is that when we "pump" Y, only part of y gets ...
• 1
1 vote
198 views

### pumping lemma length restrictions clarification

I know that this kind of question has been asked before, but I still see different kind of answers getting multiple upvotes, but I am not sure if they are all correct. That’s why I wanted to ask it ...
• 89
129 views

### Is $\{a,b,c\}^* \setminus \{a^nb^mc^k \mid n \leq m \leq k\}$ context free?

i have seen this question where someone was asking if $\{a,b,c\}^* \setminus \{a^nb^mc^k \mid n \leq m \leq k\}$ is context free. Then there was an answer that says that it is context free because: ...
• 17
44 views

### Use the Pumping Lemma to show $\Sigma^*\setminus\{0^n1^n: n\geq 0\}$ is not regular (without using complement closure)

Question: Use the Pumping Lemma to show $L_1 = \Sigma^*\setminus\{0^n1^n: n\geq 0\}$ is not regular, for $\Sigma=\{0,1\}$ (without using the complement closure property). My thoughts: I understand ...
102 views

### Use the Pumping Lemma to show $\Sigma^*\setminus\{0^n1^n: n\geq 0\}$ is not regular

Question: Use the Pumping Lemma to show $L_1 = \Sigma^*\setminus\{0^n1^n: n\geq 0\}$ is not regular, for $\Sigma=\{0,1\}$. My thoughts: I understand that $L_2 = \{0^n1^n: n\geq 0\}$ can be shown to be ...
57 views

### How to use Pumping Lemma $L = \{ wsw \mid w \in \{0,1\}^*, s \in \{2\}^* \text{, and } |w| = 2 \cdot |s| \}$?

I'm trying to use the Pumping Lemma to prove that $L = \{ wsw \mid w \in \{0,1\}^*,\ s \in \{2\}^*\text{ and } |w| = 2\cdot|s| \}$ is not a CFL.
1 vote
464 views

### How to prove the language of words $a^ib^jc^k$ where $\min(i,j)\le k\le\max(i,j)$ is not context-free?

I want to prove that $\mathcal M =\{a^ib^jc^k \mid \min(i,j)\le k\le\max(i,j)\}$ is not a CFL. Using the pumping lemma, let $p$ be the constant, then I choose $w=a^pb^pc^p$. When I separate to cases, ...
• 249
1 vote
155 views

### Variable Repetitions in Pumping Lemma for Context-Free Languages

The following is a proof of the pumping lemma for context-free languages from Theorem 8.1 in An Introduction to Formal Languages and Automata (5th ed.) by Peter Linz: Let $L$ be an infinite context-...
36 views

### How to show that $\{a^p ~|~ p\text{ is not prime}\}$ is not a CFL? [duplicate]

I want to show that the language $L=\{a^p ~|~ p\text{ is not prime}\}$ is not a CFL. If I look at $\bar{L}=\{a^p ~|~ p\text{ is prime}\}$, it is pretty straightforward to show that it is not a CFL ...
• 249
42 views

### show that $L=\{a^*\}\cup\{b^ja^{n^2}|0<j,1\leq n \}$ Holds the pumping lemma for context-free languages

prove this language verifies the conclusion of the pumping lemma show that $L=\{a^*\}\cup\{b^ja^{n^2}|0<j,1\leq n \}$ Holds the pumping lemma for context-free languages the problem is that I ...
76 views

### Is the language $L = \{{a^{2n+1}b^{m+2}a^n | m \neq 2n}\}$ context-free?

$L = \{{a^{2n+1}b^{m+2}a^n | m \neq 2n}\}$ I tried to split $L$ in 2: when $m > 2n$ and $m<2n$, however both resulting languages are not context-free, so I did not find out anything about $L$. ...
326 views

• 39
57 views

113 views

55 views

### Can a context-free Language have an infinite pumping length?

I have a language that would require an infinite pumping length, I know the language is not context-free, but is this sufficient prove ?
157 views

### $\{uuv\mid u\in\Sigma^+, v\in \Sigma^*\}$ and pumping lemma

As I am currently teaching regular languages and pumping lemma, I was searching for nice examples of languages, regular or not, for exercises. $L_1 = \{vv\mid v\in \Sigma^*\}$ is a classic example, ...
• 15.6k
1 vote
47 views

### Which z should I pick?

I'm currently trying to show that the language $L_2=\{0^n \text{ } | \text{ } n=2^k, k\geq 0\}$ is not regular by using the Pumping Lemma (at least I think it is not regular, because I couldn't find ...
• 225
1 vote
46 views

### Problem with Understanding Pumping Lemma

I'm trying to solve this exercise that asks to determine whether a language is regular or not. Following the flow of the course I figured that the exercise is a test for Pumping Lemma application. But ...
• 225
51 views

### I can't visualize what happens when we pump v and y in pumping lemma for $a^n b^n c^n$

If you need some context-: https://www.andrew.cmu.edu/user/ko/pdfs/lecture-11.pdf around page 7. Case 1-: Say vxy contains ab So when I pump v and y, what will get pumped? And how the result would be. ...
• 37
588 views

### Understanding the application of the pumping lemma to show that $L=\{0^{2^p}, p \geq 0\}$ is not regular

I want to understand how is this proof working. What I know: Pumping lemma for regular language-: Let $L$ be regular language. Then there exists a constant $n$ which depends on $L$ such that for every ...
• 47
315 views

### Can I solve pumping lemma for context free language proofs using examples?

Say I need to prove that $L=${$a^n b^n c^n; n\geq 1$} is not context free language I take n=3. w=aaabbbccc Here |w|=9. we know by pumping lemma-: |vxy| $\leq$n so vxy=abb |vy| $\geq$1 so vy=ab Hence I ...
• 47
1 vote
343 views

### Check Proof Using Pumping Lemma to Show Language Not Regular

Please check my proof where I use the pumping lemma to show that the language $B=\{0^n1^n | n≥0\}$ is not regular. I'll state the pumping lemma here for clarity: Pumping lemma If $A$ is a regular ...
• 43
1 vote
199 views

### Dividing a String According to the Pumping Lemma

I have some questions about how a string can be divided into pieces according to the pumping lemma. I am learning from Michael Sipser’s book Introduction to the Theory of Computation, 3rd Edition. He ...
• 43
63 views

### Summary of Pumping Lemma Application

For my own understanding I would like to summarize how to use the pumping lemma to show that a language is not regular. The pumping lemma is defined as follows. Pumping lemma If $A$ is a regular ...
• 43
1 vote
474 views

### What is the minimum pumping lemma length of $01^*0^*1$?

I've taken the following steps to prove that the minimum pumping length (PL) of the above language, $L= 01^*0^*1$: Set a PL. I chose $p=2$ Choose a string from $L$ where $|w|\geq p$, I chose $w=011$. ...
• 113
175 views

### Show that $\{xy : x \in \{a\}^*, y \in \{b\}^*, |x| = |y|\}$ is a not a regular language

I have been asked as an exercise how to prove that this is not a regular language. first I tried to use the pumping lemma, but I got stucked. Th erxercise hust said to prove thata this isn't a regular ...
Let me preface this by saying, I do NOT want an example of a proof, I would merely like pointers as to how I could approach this problem. For example, I have a language: L = \{w \mid w \in \{0, 1\}^*...