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
1
vote
0
answers
42
views
A proof that $a^n b^m $ for $n\neq m$ is not regular by using the pumping lemma
I am looking at $L=\{a^nb^m |n\neq m \}$. I would like to prove that $L$ is not regular.
This can easily done by assuming it is regular and looking at $\overline L$, or by using other theorems.
...
- 445
1
vote
1
answer
33
views
Parse tree choices for proving the pumping lemma for CFL
I was studying pumping lemma for CFL and in the proof it says that, we choose the shortest parse tree if there are multiple parse trees and we also choose $R$ the repeating variable such that it's the ...
- 69
0
votes
1
answer
73
views
Deciding if a language is CFL or in $P$
I'm trying to decide whether $L_c=${$w=uxu, | \ u,x\in \Sigma ^* \ and \ |u|=c $} for some constant $c\in \mathbb{N}$ is context free or not.
initialliy, I've thought about choosing $x=\epsilon$ ...
- 355
1
vote
3
answers
388
views
Proving that L = {x ∈ {a, b}∗ | na(x) < nb(x) < 2na(x)} is not a context free language
I've been working on proving that this language
L = {x ∈ {a, b}∗ | na(x) < nb(x) < 2na(x)}
is not Context Free. "na(x)" stands for "number of ...
2
votes
1
answer
267
views
Pumping Lemma Applied to 3 Variables
Prove That the Language
$L_1 = \{0^i1^j0^k | i < j\ or\ i > k\}$
is not regular using the pumping lemma.
I am not sure how to begin with this I ended up using the string:
$0^p1^{p+1}0^{p+1}$
S = ...
- 23
0
votes
1
answer
34
views
How to handle odd word
Given the language $L = \{ a^n | \text{n is odd} \}$
I'm looking for a word $w$ using $p \in \mathbb(N)$. For example, if it would be even, instead of odd I'd choose $w = a^{2p}$.
But with odd, I'm ...
- 57
2
votes
2
answers
364
views
How to handle multiple exponents (Pumping-Lemma)
Example $L = {(ab)^na^k|n\ge k}$
When searching for a word $w$, using $p \in \mathbb{N}$, for instance $(ab)^pa^p$, but wanting to pump $a$ (which is not possible because $|xy| \le p$ holds), how do I ...
- 57
0
votes
1
answer
44
views
Can we say $|xy^iz| = a^{p+i|y|}b^p$?
Using the Pumping-Lemma for $ \{L = a^nb^n | n \in \mathbb{N}\} $.
We define $p \in \mathbb{N}$
It exists a word $w = a^pb^p$
For every $|w| \ge p$: $w=xyz$, $y > 0$, $|xy| \le p$
Because of $|...
- 57
0
votes
1
answer
31
views
Pumping Lemma Contrapositive, why is this proof wrong?
I have this proof trying to show L={0}^* {1}^* is not a regular language, I know that L is regular but I don't know what in this proof is wrong. If y contains a 0 and 1 and is pumped wouldn't that ...
- 29
0
votes
1
answer
40
views
How is $|xy^{2}z| < 2^{p+1}$ (Pumping Lemma application)
In the Question here it is said that
$|xy^2z|<2^{p+1}$
Considering that $|x| = 0$ and $|z| = 0$, y consists of $2^{p}$. It's probably trivial, but how do I see, that $|xy^2z| < 2^{p+1}$?
- 57
0
votes
0
answers
29
views
Why in the pumping lemma of a context free grammar $|vy| > 0$ and $|vxy| ≤ p$?
Let us consider the case where $p > 0$ exists and a string $|w| ≥ p$ can be divided into $uv^{i}xy^{i}z$ for each $i ≥ 0$.
When we say that
$|vy| > 0$ do we mean that at least one of the two ...
- 63
2
votes
2
answers
80
views
Does the pumping lemma for context-free languages really require accepting a string with zero levels of nesting?
In the pumping lemma conditions for context-free grammar we have that the string can be divided into $uv^{i}xy^{i}z$, but in the case of $i = 0$, why does it still belong to the language?, is it ...
- 63
1
vote
1
answer
62
views
How to prove that $L = \{{a^{n} b^{n} c^{j} | n,j \geq 0}\}$ is a CFL?
In the text of my book it says that this language is context-free so I tried to prove that the conditions of the Pumping Lemma are fulfilled.
If, for example, I take the word
$aaabbbc$
I can divide it ...
- 63
0
votes
1
answer
41
views
Proving a language is not regular using Pumping Lemma
So I am given the language qr where q is any combination of a's and b's. r is then the reverse of whatever q is. For example, abba is in the language because we can make a q = ab and r = ba
I have to ...
0
votes
0
answers
22
views
CFG PL for L=\{a^ib^j \mid j = i^2\}
where i got it from. This was weird so I wanted to try it myself because they way he did it seemed wrong. So this is my attempt is it correct?
I did not add the basic parts of the pumping lemma proof ...
-3
votes
2
answers
58
views
Contradiction via pumping lemma
So this is the language that I need to prove is irregular via pumping lemma, however I am completely stuck with this and seeking some advice. The other ones I have done during my tutorial are much ...
user164540
0
votes
1
answer
56
views
Proof that $\{0^m 1^n : 0\le m\le n^2\}$ is not a CFL
I am trying to prove by the pumping lemma that $L=\{0^m1^n:0\le m\le n^2\}$ is not a CFL. Here is what I have so far.
Suppose for contradiction that it is a CFL and let $N$ be the pumping length. ...
- 335
0
votes
1
answer
233
views
Is L={0^n 1^n ∣n≥0} context free language?
I looked through many sources which give this as an example for cfl. It also makes sense according to this:
But it fails the pumping lemma test.
Let's take n=5.
According to the Pumping Lemma, we can ...
0
votes
1
answer
109
views
Is the language regular A2 = {w1w2w3 | w1, w2, w3 ϵ {0, 1}* }? How to prove?
So I think the above language is regular. I tried using pumping lemma but pumping up or down, changes the value of w1 but has no relation with w2 or w3. The resulting string after pumping will also be ...
1
vote
1
answer
467
views
How to prove L := { a^n b^n c^m | n,m >= 0 & n != m } is not context-free?
I have following language $L:= \{a^n b^n c^m \mid n \neq m; n,m \ge 0 \}$ and would like to use proof by contradiction by applying Pumping Lemma for CFLs to show that $L$ is not a CFL.
In any case, i ...
- 13
0
votes
0
answers
34
views
Confused about decomposition in Context Free Pumping lemma
I am trying to decide whether the following language is context free:
$$L = \{ a^nb^{3n}c^n \, | \, n \geq 0 \} $$
Assume $L$ is context-free.
Let $p$ be the pumping length given by the Pumping Lemma.
...
- 1
1
vote
1
answer
63
views
Does this really define a 0L-system?
Looking through old exams I found a problem stated as the following:
Define a 0L-system as a 3-tuple $S = (\Sigma, w, h)$ where $\Sigma$ is an alphabet, $h:\Sigma^* \to \Sigma^*$ is a homomorphism ...
- 13
0
votes
1
answer
47
views
Doubt in pumping lema for context-free language
I have a doubt related to pumping lemma in CFL for which I dont find an answer, so I think is very easy because no one wonder about. The lemma says:
My doubt is: Is there any restriction related to ...
1
vote
1
answer
81
views
Minimum pumping length of a context-free language
I was studying about the minimum pumping length of the language $L$ containing all palindromes over $\{a,b\}$ from this material about the pumping Lemma for CFLs.
The productions are as follows:
$$S\...
- 113
1
vote
1
answer
52
views
What happens if we remove the length condition on the pumpable part in the pumping lemma for context free languages?
Let $G$ be any CFG Grammar. There exists number $K$ dependent to $G$ so that for each $w\in L(G)$ with length bigger or equal than $K$, we can be write $w=uvxyz$ such that $uv^nxy^nz \in L(G)\; \...
- 13
1
vote
1
answer
509
views
Pumpiing Lemma for $0^n1^m0^n$ and $0^{3n}$
To understand the Pumping Lemma, I'm going to prove that the language $L = \{0^n1^m0^n | n,m \geq0\}$ is not regular. I choose string $w = 0^{p/2}1^{p/2}0^{p/2}$, for any even number $p$. Clearly $|w| ...
- 1,529
0
votes
1
answer
105
views
Example of L not regular language that suff(L) is regular
I can't find example of L not regular language that suff(L) is regular
I tried something like this:
{0^n1^n|n>= 0}, but i can't prove that it's suffix is regular
Suff(L) = {x ∈ Σ ∗ | ∃u ∈ Σ ∗ such ...
- 37
0
votes
1
answer
42
views
pumping lemma misunderstanding
given this information of a language I need to determine if the language is regular or not:
I thought to Assume by way of contradiction that L6 satisfies the conditions of the pumping lemma. Let p be ...
- 37
0
votes
2
answers
186
views
Proving $L=\{wvw|v\in \{0,1\}^*, w\in \{0,1\}^+\}$ is not regular using the myhill-nerode and pumping lemma [duplicate]
Firstly, I've tried assuming $L$ is regular and find a contradiction with help of the pumping lemma's 3 conditions, I was not able to get to a contradiction.
I've tried thinking of a word $z\in \{0,1\}...
- 355
0
votes
1
answer
61
views
Is pumping lemma not applicable for every 'long enough' string in the language?
I recently learnt that a subset of a regular set may not be regular. This is causing me confusion as I imagined if a set is regular then every string longer than $p$ can be pumped in the language. So ...
- 115
0
votes
0
answers
59
views
Proving that $L = \{a^n b^m |\: m \:\%\: n = 0 \ \}$ is not context-free
For language $L = \{a^n\, b^m\: |\: m \:\%\: n = 0 \}$, that is, 𝑚 is a multiple of 𝑛.
I'm trying to find a proof that it isn't a context free. I know it isn't regular, but it also doesn't seem to ...
- 1
0
votes
0
answers
52
views
Pumping length of (a+b)(a+b)*
I'm trying to figure out the pumping length of (a+b)(a+b)*
From what I understand, this means that there is some A or B followed by any number of either A's or B's e.g
ABBBB
or
AAAAA
but AAAABA ...
0
votes
1
answer
43
views
Question about $L$ = { $ww$ | $w$ ∊ $ca^*c$}
I found a grammar for this language.
$S->caZac |cccc $.
$Z->aZa | cc$
But if I try to use pumping lemma for context-free languages on $L$ with the word: $ca^ncca^nc$ I obtain it's not context-...
0
votes
1
answer
56
views
When applying pumping lemma for regular languages to prove that a given language is non regular, do we show that pumping fails for all $i$ or one $i$?
Pumping Lemma for Regular Languages
Pumping Lemma for Regular Languages: If $A$ is a regular language, then there is a number $p$ ( the pumping length ) where if $s$ is any string in $A$ of length ...
- 315
0
votes
1
answer
33
views
Why $L$ = { $uc^nu$ | $u$ ∈ $P$, $n > 0$ } isn't context-free?
$P$ is the set of all words of even length on {0,1}.
Hi, i tried using pumping lemma to see why $L$ isn't a context-free language, but there's a decomposition where none of all three properties is ...
1
vote
1
answer
31
views
$|v|$ and $|x|$ factorizations (in Pumping lemma for context-free) have the same length?
When i iterate $v$ and $x$ factorizations to see if a word is still in a language $L$, do i have to assume that $|v| = |x|$ always or could happen theirs lengths are different?.
I'm asking because i ...
1
vote
2
answers
145
views
Why does Michael Sipser state that $0^p0^p$ is a bad choice for proving $L=\{ww|w \in \{0,1\}^*\}$ is non-regular a bad choice?
I feel that choice should work great for proving non - regularity of the mentioned language.
If $L=\{ww|w \in \{0,1\}^*\}$ and we choose $s=0^p0^p$, meaning s is atleast as long as 'p'. Then we can ...
- 315
1
vote
0
answers
37
views
Which non regular language meets the requirements for pumping lemma for regular languages?
I heard in my lecture that there are non regular languages which meet the requirements for the pumping lemma for regular languages but I never actually saw one. Does anybody have an example?
0
votes
2
answers
166
views
When applying pumping lemma to prove that a language is not regular, do we need to apply it to all decompositions of a string or just one?
We know according to the pumping lemma if a language is regular, then a string already exists and it can be separated into 3 parts ( called decompositions ), 1 string can have multiple decompositions.
...
- 315
0
votes
1
answer
148
views
Is $L = \{w w^r w | w \in a(b+c)^*a \}$ a context-free language?
Can't understand how to apply pumping lemma to see if a language is context-free or not.
I tried to verify the context-free's pumping lemma, and the language seems to be not context-free but I can't ...
0
votes
1
answer
431
views
How to use the Pumping Lemma to show that a language is not context free?
I have the following alphabet $\Sigma = \{0,\dots,9\}$ and the following language over $\Sigma \cup \{\#\}$:
$$L=\{\#w \ |\ w \in\Sigma^*,\sum_{i\geq1}w_i\ \text{is prime}\}\\\\$$
This language ...
- 105
-1
votes
3
answers
72
views
Is it possible to divide a string, according to pumping lemma, from a language in a way that pumping a section would render the language -non regular
I understand that pumping lemma can only be used to prove that a certain language is "non-regular", it cannot be used for proving regularity
But since, it's a property of regular language, ...
- 315
-3
votes
1
answer
47
views
prove $a^nb^m; n<3m + 2$ is not regular by the pumping lemma
I want to prove this language $a^nb^m; 0 \leq n< 3m+2$ to be not regular by the pumping lemma. This is my attempt, is this a correct way of doing it?
Let's suppose $L$ is regular. Let $s = a^{3k+1}...
- 105
-2
votes
1
answer
54
views
regular languages under intersection and union, a bit of confusion to clarify
Let's assume that $L_1 = a^nb^{2n}$ and $L_2 = a^na^{2n}$, knowing that $L_1$ is not regular, and $L_2$ is. We also know that regular languages are closed under intersection and union, and complement. ...
- 105
0
votes
1
answer
48
views
prove $a^nb^nc^m; n,m \geq 0$
I proved this language $L = a^nb^nc^m; n,m \geq 0$ is not regular the following way:
Let $L \cap a^*b^* = a^nb^n$
We know that $a^nb^n$ is not regular, and $a^*b^*$ is regular. Thus, if $L$ is ...
- 105
1
vote
2
answers
572
views
Prove $a^nb^{n^2+n}$ is not regular by the pumping lemma
I want to prove this language $L=\{a^nb^{n^2+n}:n\in\Bbb N\}$ to be nonregular by the pumping lemma. This is my attempt, is this a correct way of doing it?
Let's suppose $L$ is regular. Let $s = a^kb^{...
- 105
-3
votes
1
answer
41
views
Is a^n , n = 3j+4k , n>=0, a context-free language?
I have no idea how to approach this question... How would I go about proving or disproving this? any explanation is appreciated.
- 1
0
votes
0
answers
41
views
Is a^n b^k , 0 <= n <= k^2, a context-free language?
I don't think it's a CFL, but I'm having a hard time using the pumping lemma to prove this. Is there any way I can use homomorphism? Maybe h(a)= a, h(b) = lambda...
If the pumping lemma is more ...
- 1
-1
votes
1
answer
96
views
How do I show language consisting prime number of 0s or prime number of 1s is not context-free?
The language is: L1 = {w | n0(w) or n1(w) is prime}
n0 means number of 0s and n1 means number of 1s I can show a^n (n is prime) is not context-free. But I can't ...
0
votes
1
answer
1k
views
Using the pumping lemma, show that L = {a b^n c^n | n ≥ 0} is not regular
I've encountered many examples which its format is like: a^n b^n. For this I understand that w = 2n and is pretty straightforward, but what happens in my case? Is w = 1 + 2n? And in this case would |...
