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.

Filter by
Sorted by
Tagged with
0 votes
1 answer
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 ...
80s's user avatar
  • 1
0 votes
1 answer
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 ...
S.web's user avatar
  • 3
0 votes
0 answers
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 ...
kk1997's user avatar
  • 1
0 votes
1 answer
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$...
cs_student's user avatar
0 votes
2 answers
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 ...
apex's user avatar
  • 1
1 vote
1 answer
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 ...
Ronald's user avatar
  • 89
0 votes
2 answers
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: ...
tomato's user avatar
  • 17
0 votes
1 answer
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 ...
Clair Goodman's user avatar
0 votes
1 answer
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 ...
Clair Goodman's user avatar
-2 votes
1 answer
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.
ZisIzHell's user avatar
1 vote
3 answers
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, ...
Math4me's user avatar
  • 249
1 vote
1 answer
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-...
Tryer outer's user avatar
0 votes
0 answers
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 ...
Math4me's user avatar
  • 249
-4 votes
1 answer
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 ...
Emma Carter's user avatar
2 votes
0 answers
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$. ...
Andrei Hodoroaga's user avatar
-3 votes
1 answer
326 views

Prove a stronger version of the pumping lemma for context-free languages

Let $L$ be a context-free language. Prove that there exists integer $p>0$ such that $ \forall z\in L $ such that $ |z|\ge p $, there exists a partition $ z=uvwxy $ such that $|vwx|\le p$ $|vx|\...
maya cohen's user avatar
4 votes
2 answers
205 views

Is $\{a^ib^ja^k \mid j \text{ is odd, then } k=i^2+j ;\ j \text{ is even, then } k =i+j\}$ context-free?

$L=\{a^ib^ja^k \mid j \text{ is odd, then } k=i^2+j ;\ j \text{ is even, then } k =i+j\}$ I tried writing $L$ as the union of the language created with $j$ odd and the one with $j$ even. When $j$ is ...
Pete42's user avatar
  • 51
5 votes
1 answer
261 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 ...
Clifford Royals's user avatar
1 vote
1 answer
172 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 ...
user150587's user avatar
0 votes
1 answer
1k 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 ...
Pratik Hadawale's user avatar
3 votes
2 answers
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-...
pblass's user avatar
  • 55
1 vote
1 answer
3k 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&...
Pratik Hadawale's user avatar
4 votes
4 answers
5k 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 ...
Pratik Hadawale's user avatar
-2 votes
2 answers
228 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 ...
maya cohen's user avatar
1 vote
2 answers
314 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 ...
Fackelmann's user avatar
2 votes
3 answers
290 views

Can we choose different words for pumping Lemma to prove $a^n b^m:n\neq m$ is not regular?

$L=\{a^n b^m:n\neq m\}$ $L=\{a^n b^l c^k :k\neq n+l\} $ Can we take in case 1 $w=0^{2p}1^p$? But my resource says that, we need to take $w=0^{p}1^{p+p!}$ Similarly in case 2, I want to take $w=a^p b^...
jewkes's user avatar
  • 39
0 votes
1 answer
57 views

Context-free pumping lemma of $a^nb^n$

I know $a^nb^n$ with $n\geq0$ is considered a context-free language, but if I try: Using pumping length $p = 3$ $n = p$, thus we have $aaabbb$ $u =aa$ and $y = bb$ $v = a$, $w = b$ and $x=λ$, then $|...
Akari Oozora's user avatar
1 vote
1 answer
67 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 ...
Andre's user avatar
  • 111
1 vote
1 answer
124 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 ...
YX L's user avatar
  • 13
0 votes
1 answer
62 views

I require assistance in proving this language as not regular

I'm trying to prove that L = {$0^n1^m0^n | m,n >= 1$} in NOT regular but I am struggling with the demostration process. I know the conditions are that: $|y| > 0$; $'y'$ can't be empty $|xy| <...
BadProgrammer's user avatar
0 votes
2 answers
113 views

Irregularity of $\{a^{b+cd} : d \in \mathbb{N}\}$

I was solving some basic problems about the theory of machines and automata. The topic was about pumping lemma, but I could not solve the below question and prove that it is not regular. $$L=\{a^{b+cd}...
Aylin Naebzadeh's user avatar
1 vote
1 answer
34 views

Argument as to why a word does not belong to a language (pumping lemma)

Given the language $D = \{x^n y^n y^m \mid n,m \geq 0\}$, I have applied the pumping lemma with $k>0$, $n=k$ and $m=0$ and found a word $z = x^{k+q} y^k$ with $q>0$ that does not belong to $D$. ...
Warsick's user avatar
  • 55
-2 votes
1 answer
203 views

Is this language regular or non-regular : {ww | w ∈ {a,b}* } ∩ {a}*

I think it's a regular language but I can't find a DFA or a regular expression. Would anyone know how to help me?
Bubino's user avatar
  • 111
0 votes
0 answers
25 views

How ot prove a language is regular using L′ = {ab(^i)c)^i) | i ≥ 0 [duplicate]

I have the following language L = {a(^i)b(^j)c(^k) | i, j, k ≥ 0, and, if i = 1 then j = k} . How do I use the fact that L′ = {ab(^i)c)^i) | i ≥ 0 to prove that is it not regular? I am given a hint ...
sofiatb's user avatar
1 vote
1 answer
107 views

How does $xy^0z = λ$ not contradict $y \ne λ$ in the pumping lemma?

I have just started out theory of automata in my university and we are studying the pumping lemma. From what I have understood, the lemma states that $y \neq \lambda$ (where $\lambda$ is the empty ...
Ali Ahmed's user avatar
0 votes
0 answers
112 views

How do I prove a language is not regular using L′ = {a b^i c^i | i ≥ 0}?

I have just started my masters without any substantial experience in programming and I am struggling to understand certain concepts. I have been given the following language $$L = \{a^i b^j c^k \mid i,...
sofiatb's user avatar
-2 votes
1 answer
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 ?
Connor Kolan's user avatar
5 votes
1 answer
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, ...
Nathaniel's user avatar
  • 15.6k
1 vote
2 answers
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 ...
Tita's user avatar
  • 225
1 vote
1 answer
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 ...
Tita's user avatar
  • 225
-1 votes
1 answer
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. ...
ladhee's user avatar
  • 37
2 votes
2 answers
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 ...
supcem's user avatar
  • 47
0 votes
2 answers
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 ...
supcem's user avatar
  • 47
1 vote
2 answers
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 ...
billiam's user avatar
  • 43
1 vote
1 answer
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 ...
billiam's user avatar
  • 43
2 votes
0 answers
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 ...
billiam's user avatar
  • 43
1 vote
2 answers
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$. ...
askman's user avatar
  • 113
0 votes
3 answers
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 ...
aswangirl's user avatar
0 votes
1 answer
66 views

How to use pumping lemma on languages that do not follow a strict structure?

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\}^*...
Sick McNugget's user avatar
2 votes
1 answer
83 views

Implication of the Pumping lemma

I'm reading Hopcroft and Ullman's '79 edition of "Introduction to Automata theory, Languages, and Computation". In chapter 3, the authors say "The lemma[sic] does not state that every ...
Harikrishnan R's user avatar

1
2
3 4 5
11