Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

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
5 votes
1 answer
162 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 ...
user avatar
1 vote
1 answer
71 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 ...
user avatar
0 votes
1 answer
55 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 ...
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-...
user avatar
  • 55
1 vote
1 answer
35 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&...
user avatar
2 votes
4 answers
243 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 ...
user avatar
-3 votes
0 answers
29 views

Using the pumping lemma, show that the following languages are not regular

L1 = {c^ia^jcb^i+j|i,j∈N0} L2 = {w∈{a,b,c}∗|w=uvmit#c(v)=0und#a(u)=#a(v)}
user avatar
-2 votes
2 answers
82 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 ...
user avatar
1 vote
2 answers
67 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 ...
user avatar
3 votes
3 answers
57 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^...
user avatar
  • 41
0 votes
1 answer
41 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 $|...
user avatar
1 vote
1 answer
33 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 ...
user avatar
  • 111
1 vote
1 answer
71 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 ...
user avatar
  • 13
0 votes
1 answer
51 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| <...
user avatar
0 votes
2 answers
96 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}...
user avatar
1 vote
1 answer
32 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$. ...
user avatar
  • 55
-2 votes
1 answer
92 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?
user avatar
  • 15
0 votes
0 answers
19 views

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

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 ...
user avatar
1 vote
1 answer
52 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 ...
user avatar
0 votes
0 answers
45 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,...
user avatar
-2 votes
1 answer
22 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 ?
user avatar
4 votes
1 answer
79 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, ...
user avatar
  • 7,154
0 votes
0 answers
17 views

Could I have used PL directly on this language instead of proving it the way I did? [duplicate]

In an exercise I'm trying to solve I have to say whether a language is regular or not. One of the languages is $L_1=\{0^i1^j \mid i,j \geq 1\text{ and } i\neq j\}$. I have already solved this by ...
user avatar
  • 205
1 vote
2 answers
43 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 ...
user avatar
  • 205
0 votes
0 answers
30 views

Pumping Lemma for CFG $S \to c|aSdSb$

I've given the grammar $G=(\{S\}, \{a,b,c,d\}, \{S\to c \mid aSdSb\}, S)$ and I wanted to make an expression out of it. I tried bringing it into ChomskyNF, but as someone commented below the approach ...
user avatar
1 vote
1 answer
37 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 ...
user avatar
  • 205
-1 votes
1 answer
39 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. ...
user avatar
  • 39
2 votes
2 answers
77 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 ...
user avatar
  • 47
0 votes
2 answers
138 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 ...
user avatar
  • 47
0 votes
2 answers
82 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 ...
user avatar
  • 33
1 vote
1 answer
56 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 ...
user avatar
  • 33
2 votes
0 answers
39 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 ...
user avatar
  • 33
1 vote
2 answers
68 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$. ...
user avatar
  • 113
0 votes
2 answers
88 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 ...
user avatar
0 votes
1 answer
58 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\}^*...
user avatar
2 votes
1 answer
61 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 ...
user avatar
0 votes
0 answers
68 views

Proving that $\{ a^i b^j c^{\max(i,j)} \}$ is not context-free

Prove that $L$ is not a Context-free language, where $$L = \{ a^{i} b^{j}c^{h}\mid i,j,h\in \mathbb{N} \wedge h = \max(i,j)\}.$$ I have an idea: It can be divided into two situations: When $i < j$...
user avatar
  • 13
-1 votes
1 answer
38 views

How to prove that $L = \{w\in\{a,b\}^*\mid w = uav \text{ and } |u| = |v|\}$ is not a regular language

$L = \{w\in\{a,b\}^*\mid w = uav \text{ and } |u| = |v|\}$ I know to use the pump lemma, but I don’t know how to use it correctly.
user avatar
  • 13
0 votes
0 answers
16 views

Check if a language is context free [duplicate]

Check whether the following language is context-free. If yes, a suitable grammar should be given; if no, the pumping lemma should be used as a tool. $$L=\{a^ib^jc^k \mid i, j, k \in N \text{ and } i &...
user avatar
  • 13
0 votes
1 answer
85 views

Proof that $\{a^ib^jc^k\mid i,j,k\in\mathbb{N}, i<k<j\}$ is not context-free using the Pumping Lemma

$$ L=\{a^ib^jc^k \;| \;i, j, k \in \mathbb{N} \; \text{and} \; i <k<j\} $$ I need to show that this language is not context-free with the help of the Pumping Lemma. My first intuition is, that ...
user avatar
  • 1
1 vote
1 answer
82 views

Use the CFL pumping lemma to show that this language(0^p where p is prime) is not context free

L = {0^p |p is a prime}. So was looking at the explanation at the bottom of page 5 of the following website: https://www.ics.uci.edu/~goodrich/teach/cs162/hw/HW5Sols.pdf I want to make sure that I ...
user avatar
-1 votes
1 answer
39 views

How to choose word for pumping lemma for $a^kb^{2k}a^k$?

I have to show that the language $ \mathcal {L} = \{a ^ k b ^ {2k} a ^ k: k \geq 0 \} $ is not a regular language. So that's what I want to use the pumping motto for. What I could do is this: let $ \ ...
user avatar
0 votes
1 answer
51 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 ...
user avatar
0 votes
1 answer
23 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 ...
user avatar
  • 3
0 votes
1 answer
70 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 ...
user avatar
5 votes
1 answer
91 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?
user avatar
2 votes
2 answers
80 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$ ...
user avatar
1 vote
1 answer
98 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 ...
user avatar
  • 75
0 votes
0 answers
66 views

Prove with pumping lemma that the language { $a^n b^n b^m a^m | n ≠ m $ } is not context free

I'm having a trouble proving it to be non-context-free. For example, if I take w = $a^k b^k b^{k+1} a^{k+1}$, it would be problematic if the partition of $vxy$ with $|v| = |y|$ was in the $ b^{k+1} a^{...
user avatar
2 votes
4 answers
413 views

Proving that $L=\{ w \mid \lvert w \rvert$ is prime $\}$* is a regular language

I'm trying to prove that the following languague is a regular language: $L=\{ w \mid \lvert w \rvert$ is prime $\}$* What I have thought is to divide each word $w \in L$ into subwords of length 2 if ...
user avatar

1
2 3 4 5
10