Questions tagged [pumping-lemma]
The pumping-lemma tag has no usage guidance.
197
questions
0
votes
1
answer
38
views
Is $L_2=\{w^*\,:\,w\in L_1\}$ where $L_1$ is regular, a regular language?
Is language $L_2=\{w^*\,:\,w\in L_1\}$, where $L_1$ is regular, regular?
Intuitively it seems that it's not: the automaton accepting $L_2$ would most probably just be a loop made from an automaton ...
- 33
0
votes
1
answer
31
views
How to prove that a language is not context-free using pumping lemma?
How could I realize this using the pumping lemma?
What if the pumping part is between b and c or between a and b so that after pumping the word is still in L?
- 47
0
votes
1
answer
57
views
My proof of $\{a^p|p~~\mathbb{is~~prime}\}$ is not a CFL.
I want to show that the language $L=\{a^p~|~p~~\mathbb{is~~prime}\}$ is not a CFL.
Assuming towards a contradiction that $L$ is a CFL.
Let $p$ be the number from the Pumping lemma for context-free ...
- 656
0
votes
0
answers
78
views
How can I prove that L = {w ∈ {a, b, c, d} ∗ | #a(w) = #b(w) = #c(w) = #d(w)} is not context-free without using the pumping lemma?
I am stuck on this problem, I can prove it using the pumping lemma, but I'm wondering if I can also prove it using closure properties
0
votes
0
answers
28
views
Prove non regularity of the language a^n where n is an even or a prime number, with the pumping lemma
How to prove that the language that is the union of the language where $n$ is an even number and the language where $n$ is a prime number is non-regular with the pumping lemma?
I know how to prove ...
2
votes
3
answers
144
views
Proving a language is not regular using the pumping lemma
Let
$$
L
=\Big\{ \
ba^{2^k}b^{i_1}ab^{i_2}a\dots b^{i_k}a
\ \Big|\
k\ge 1,\ i_j\ge1 \ ,\ 1\le j \le k\
\Big\}\ .
$$
Using the pumping lemma prove that $L$ isn't regular.
The answer given to this ...
- 373
0
votes
1
answer
39
views
Pumping lemma: if you pump to $uv^0wx^0y$, wouldn't $|vx| \ngeq 1$?
For pumping lemma for CFLs, for strings $s$ in $L$, they follow the form $s = uvwxy$ and $|vwx| \leq n$, $|vx| \geq 1$, and $uv^iwx^iy \in L$ for $i \geq 0$.
If I want to prove a language is not CFL, ...
- 1,713
1
vote
2
answers
74
views
Failure of 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 $|...
0
votes
1
answer
51
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
0
votes
0
answers
18
views
Pumping lemma on a regular language with different variables
I have this language
$L = \{a^i b^j c^k ∣ i,j,k \geq 0 \text{ and } i+j=k \}$
I dont know how to replace $i,j,k $ with the pumping length p, usually when I make a string s with the pumping length p I ...
- 143
1
vote
1
answer
37
views
Solution verification: Proving that this language is irregular using the pumping lemma.
Prove that the following language with $\Sigma=\{a,b\}$, is not regular using the pumping lemma:
$L=\{ba^{2^{k}}b^{i_1}ab^{i_2}...b^{i_k}a : k\ge 1, \forall j\space\space (1\le j \le k)\space\space ...
- 2,051
0
votes
0
answers
38
views
Proof of Pumping Lemma: Why can we set the pumping constant to the number of states?
I'm learning the proof of the Pumping Lemma for regular languages. The proof is carried out using an arbitrary string having length of at least the number of states in the DFA.
As such:
The language ...
- 1
1
vote
1
answer
198
views
a^m b^n c^n prove it's not regular/pumping lemma
How to prove that $L = \{a^mb^nc^n \mid n, m \geq 0\}$ is not regular by the pumping lemma
My attempt:
Let's suppose $L$ is regular.
There exists a pumping constant p, and we choose $w = a^pb^pc^p$
...
- 77
0
votes
0
answers
13
views
Pumping Lemma-prove a language is not regular
The question is to prove that the Language below is not regular, and I have used the pumping lemma technique I wanted to know if this is the correct solution
so the CFG for it is
let the grammer be ...
- 29
0
votes
3
answers
55
views
How can the following language be regular?
Lets assume the language $L=\{a^n b^m\}$
When we try proofing $L$ is regular using the Pumping lemma and say $w=xyz$
and thus for every $w=xy^iz $ , $w$ has to be $ \in L $.
now if we say $y$ only ...
- 1
0
votes
1
answer
28
views
Proof of context free Language
$$L:=\{w\in\{a, b, c\}^*| ∃ i, j ∈ N :w = a^i⋅b^i⋅c^j ∧ i < j\}$$
I am trying to prove/disprove that this is context free.
I was sure this was not context free, since there are 3 pumping operations,...
0
votes
1
answer
280
views
Prove that L={$a^p$: p is prime } is not regular using pumping lemma
https://cs.stackexchange.com/questions/145675/understanding-about-pumping-lemma-for-regular-language-confusions-of-beginner
This the reference idea I have used in this proof. But I am very clear that ...
- 11
0
votes
1
answer
51
views
Is it true that for every regular language $L \subseteq \{0, 1\}^{*}$ the language $\{w^{|w|} |w \in L \}$ is also regular?
Is it true that for every regular language $L \subseteq \{0, 1\}^{*}$ the language $\{w^{|w|} |w \in L \}$ is also regular?
I think the language is not regular because for a finite w we can easily ...
- 703
1
vote
0
answers
52
views
Pumping Lemma for regular languages
Given is the the following language.
$L= \{ wa^{\vert w \vert} \mid w \in \{a,b\}^* \cup L(b^*a^*)\} $
Task: Prove that $L$ is not regular using pumping lemma.
I am not sure wether I did this ...
0
votes
0
answers
37
views
Proving $\{0^m1^{2m}2^i | m > i \geq 0\}$ is not context-free using the pumping lemma
I want to prove that the language $\{0^m1^{2m}2^i\;|\;m > i \geq 0\}$ is not context-free using the pumping lemma.
I know there are at least 3 contradictions that exist, all of which are when $v$ ...
- 53
0
votes
0
answers
42
views
Pumping Lemma proof for this language: $L= \{a^ib^jc^{ij} \mid i, j \geqslant 0\}$
i have troubles to show that this language is not context free with the pumping lemma.
As a word I chose: $a^mb^mc^{m^2}$
I solved all the cases but one, which is:
"$vy$ contains $b$'s and $c$'s&...
- 1
0
votes
0
answers
55
views
Use pumping-lemma to prove that L is not a context-free language
Show using the pumping lemma that L = { $w$$w^{R}$$w$ | $w\in$ {a,b}* $w\notin$ context-free language where $w^{R}$ denotes the reversed word $w$.
(if $w$ = $w_{1}$$w_{2}$$w_{3}$ ... $w_{n}$ ,$w^{R}$ ...
- 1
0
votes
1
answer
337
views
Is $\{a^nb^mc^{n+m} \mid n, m \geqslant 0\}$ a context-free language (CFL)??
Considering this language $L = \{a^n b^m c^{n+m} \mid n, m \geqslant 0 \}$ is it a CFL? If I can make a PDA for it can I still prove with the pumping lemma that the language is not CFL?
I mean if try ...
- 3
2
votes
1
answer
83
views
Check if the Language is context-free using the Pumping Lemma
$$
L=\{a^ib^jc^k \mid i, j, k \in N \text{ and } i <k<j\}
$$
I want to check if this language is context-free. The part that confuses me is that if I choose
$$
w=a^nb^{n+2}c^{n+1}
$$
then one ...
- 167
0
votes
1
answer
58
views
Regularity of $w^{|w|}$
Is it true that for every regular language $L \subseteq \{0,1\}^*$, the language $\{ w^{|w|} \mid w \in L \}$ is also regular?
It seems to me that it is not regular , so I will try to prove it with ...
- 63
1
vote
2
answers
126
views
Prove the following languages are irregular.
Prove the following language is irregular.
$$ \{w^n \mid w \in \{0,1\}^*,\ n ≥ 2 \}$$
I'm trying to prove this with the Pumping Lemma, but I'm kind of confused because $w$ is a language not an ...
- 69
0
votes
1
answer
66
views
Can number of states of minimum accepting automaton be equal to a constan from the pumping lemma?
Let $L$ be a regular language. Prove that the number of states of the minimum accepting automata $L$ can be equal to a constant from the pumping lemma, but any smaller number can't.
From what I ...
- 43
0
votes
2
answers
752
views
Proof that the language $a^nb^ma^nb^m$ is not context free using the pumping lemma.
I need a proof that the language L = {$a^nb^ma^nb^m,\:n,m\geq0$} is context free using the pumping lemma. My problem is that I can actually show the conditions of the lemma hold for this language and ...
0
votes
1
answer
27
views
Pumping Lemma to prove language not regular, formatting $x$
I need help with a question/verification I'm even thinking about it correctly.
I'm trying to use the PL to prove $L$ is not regular. $L = \{\{a,b,c\}^* \mid |a| < |b| \wedge |a| < |c|\}$. This ...
0
votes
0
answers
30
views
Why doesn't $|uv|\le k$ break the pumping lemma?
Let $N = \{ab^x | x \in\mathbb{N}\}$.
Let the pumping length be $k$. So $ab^k$ belongs to $N$.
Let $u = a, v = b^k, w = \operatorname{empty}$.
Then $|uv|\le k$ does not hold. No other splitting I can ...
- 3
1
vote
1
answer
72
views
questions about the pumping lemma
Below is the Pumping lemma as stated in Automata and Computability by (Dexter C. Kozen)
Let $A$ be a regular set. Then the following property holds of $A$:
There exist $k≥0$ such that for any string $...
- 63
0
votes
1
answer
51
views
Pumping lemma definition!
I was studing Pumping lemma and I saw wondering and confusing definition,"Pumping length".
Here is my problems:
Question 1:
Is pumping length = number of states in DFA?
Question 2:
If any ...
- 307
2
votes
1
answer
142
views
Prove $\left\{u \# v | u,v \in \{0,1\}^{*} \text{ and } u \text{ is a substring of } v \right\}$ is not context free
I'm practising for my CS exam and got stuck on this problem
$\left\{u \# v | u,v \in \{0,1\}^{*} \text{ and } u \text{ is a substring of } v \right\}$
So I've tried using following pumping lemma:
...
- 125
1
vote
1
answer
486
views
Prove $\{0^k10^k10^k1 \in \{0,1\}^* \mid k \geq 0 \}$ is not context free
I'm practising for my CS exam and got stuck on this problem
$$ \{0^k10^k10^k1 \in \{0,1\}^*\mid k ≥ 0\}. $$
I think I have good start however I don't know how to proceed. I assume the L is context ...
- 125
1
vote
1
answer
72
views
Pumping Lemma works on language, but language is not regular
So i am given this language:
L = { $c^ma^nb^n $ | $m≥ 1 $ and $n≥ 0$ } U { $a^mb^n$ | $m,n≥ 0$ }
And i have to prove that the pumping lemma property works on L.
Although pumping lemma can work, i then ...
- 125
2
votes
2
answers
158
views
Irregularity of $a^ib^jc^k∣\text{ if }i=1\text{ then }j=k$ using pumping lemma
This question has been asked here several times. However none of the examples I saw actually tried to prove it's irregularity using the standard pumping lemma.
I know how to prove irregularity using ...
- 125
0
votes
1
answer
96
views
Prove that \{a^{3^n} is not regular \n>=1 using pumping lemma
I'm practicing for my CS exam and I got stuck on following language $L:= \{ a^{k} b u a^{k} | k \geq 1, u \in \Sigma^{*}\}$
$\Sigma = \{a,b\}$
I've tried to prove this language using a pumping lemma, ...
- 125
2
votes
1
answer
145
views
Is the Pumping Lemma properly applied to prove $L = \{ 0^i1^{i+j}0^i \mid i, j > 0 \}$
The problem is to prove whether $L = \{0^i1^{i+j}0^i \mid i, j > 0\}$ is regular or not.
I've used the Pumping Lemma with a string $s = 0^p1^{2p}0^p$, however I do not know I can choose such string ...
- 123
2
votes
2
answers
285
views
Pumping Lemma proof $L= \{a^nb^m2^{n*m} \mid m,n \ge 0 \} $ not regular
I'm trying to proof that the following language is not a regular language using the pumping lemma:
$L= \{a^nb^m2^{n*m} \mid m,n \ge 0 \} $
I tried to build the string by assuming that m,n are the same ...
- 25
0
votes
0
answers
29
views
Pumping lemma for context-free languages theorical question.
I have seen the demostration that $a^nb^nc^n$ is not a context-free languaje like a million times.
My question is: If a languaje can produce a word of the form $a^nb^nc^n$ it is instantanley not ...
- 33
1
vote
1
answer
118
views
Pumping lemma (context-free) of $L = \{a^nb^{\max\{n,m\}}a^m\ |\ n, m ≥ 0\}$
I want to show that $L = \{a^nb^{\max\{n,m\}}a^m\ |\ n, m ≥ 0\}$ is not context-free.
I tried with things like take $w=a^pb^pa^p$ and got that $vwz$ is $a^qb^{p-q}$ but... I don't know, it doesn't ...
- 33
0
votes
1
answer
61
views
Show these affirmations using the context-free pumping lemma properties
The question :
Given $G$ a context-free grammar of Chomsky normal form with $k$ symbols. We know that the language $L(G)$ satisfy the pumping lemma for $ p = 2^k + 1$
I have those two questions to ...
- 335
1
vote
1
answer
134
views
Proving the language $\{w \in \{0, 1\}^{\ast} : w = w^{R}$, $|w|_{0} = |w|_{1} \}$ is not Context Free using Pumping Lemma
$\textit{Proof}$. Let $A$ be the language $\{w \in \{0, 1\}^{\ast} : w = w^{R}$, $|w|_{0} = |w|_{1} \}$. We will use the Pumping Lemma to prove that $A$ is not Context Free Language (CFL). The proof ...
- 59
1
vote
0
answers
1k
views
Proving that the language $\{a^{i} b^{j} c^{k} : i < j < k\}$ is not Context Free using Pumping Lemma
$\textit{Proof}$. Let $A$ be the language $\{a^{i} b^{j} c^{k} : i < j < k\}$. We will use
the Pumping Lemma to prove that $A$ is not Context Free Language (CFL). The proof is by contradiction.
...
- 59
1
vote
2
answers
416
views
Use the pumping lemma to show that the language is not context-free
I want to show that this language is not context-free:
I struggle with the pumping lemma for CFL and i would like to know how to solve this problem. Thank you
(skipping the classic introductory text ...
- 335
0
votes
0
answers
89
views
Pumping Lemma proof, need help with splitting xyz word, choosing pumping length and proving its not regular
I have the following language i want to prove is not regular by using the pumping lemma but not sure on what to use as the xyz and the pumping length. can i get a point in the right direction for how ...
- 11
0
votes
1
answer
231
views
pumping lemma division cases
If I got a language that I want to classify as "nonregular" using pumping lemma
the problem that I'm facing with this algorithm is the following:
when you divide the string S that you choose(...
- 39
1
vote
0
answers
130
views
Pumping Lemma: context free squared number proof
I'm just doing a Pumping Lemma proof for showing a language is not Context Free by contradiction and would just like to know if it's valid. Note that for reasons, I'm only allowing $i = 0$ in the last ...
0
votes
1
answer
336
views
Can the pumping length ever be equal to $0$ ? (Pumping lemma for regular languages)
I have seen some very conflicting information regarding the minimum pumping length.
(part of the) Pumping lemma states :
$\forall$ words $s\in L$ where $|s| > p$
Is it possible to use this ...
- 27
0
votes
0
answers
46
views
How can I use the pumping lemma for context-free language in a language with two alphabets?
$G =\{aba\mid a\in \{x,y,z\}{^+}\text{ and } b \in \{0,1\}\}$
I have watched many videos but I never saw an example of someone solving a pumping lemma in a language with two alphabets, can someone ...
