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.
484
questions
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 ...
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 ...
- 11
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 ...
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-...
- 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&...
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
...
-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)}
-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 ...
- 115
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 ...
- 11
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^...
- 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 $|...
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 ...
- 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 ...
- 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| <...
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}...
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$.
...
- 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?
- 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 ...
- 1
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 ...
- 25
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,...
- 1
-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 ?
- 27
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, ...
- 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 ...
- 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 ...
- 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 ...
- 13
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 ...
- 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. ...
- 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 ...
- 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 ...
- 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 ...
- 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 ...
- 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 ...
- 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$. ...
- 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 ...
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\}^*...
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 ...
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$...
- 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.
- 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 &...
- 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 ...
- 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 ...
- 11
-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 $ \ ...
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 ...
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 ...
- 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 ...
- 25
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?
- 51
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$ ...
- 67
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 ...
- 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^{...
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 ...
- 159