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.
533
questions
1
vote
1
answer
58
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
21
views
Confused about decomposition in Context Free Pumping lemma
Okay so here's my current solution for the question that asks whether the language is context free:
$$L = { a^nb^{3n}c^n | \, n \geq 0 } $$
Assume by contradiction that L is context-free.
Let p be ...
- 1
-1
votes
0
answers
15
views
Pumping Lemma to prove non regularity of a CFL
Okay so I am given the language:
$$ L=\{ 0^n1^{4n} \,\,\,\, | \,\,\,n \geq 0 \} $$
The question is to find out if the language is regular or not.
I immediately think of using the pumping lemma to ...
- 1
1
vote
1
answer
47
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
44
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
77
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
50
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
86
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,509
0
votes
1
answer
72
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 ...
- 27
0
votes
1
answer
36
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 ...
- 27
0
votes
2
answers
73
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\}...
- 315
0
votes
1
answer
55
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
46
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
34
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
34
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
38
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 ...
- 305
0
votes
1
answer
31
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
26
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
99
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 ...
- 305
0
votes
0
answers
29
views
In Pumpin Lemma, let's say we have a decomposition of the string s = xyz, is it necessary for x to take the automaton through distinct states?
I understand what Pumping Lemma is, how it works and also understand it's proof. The gist is that it uses "Pigeon Hole" principle to guarentee us a repeatation in the sequence of states and ...
- 305
1
vote
0
answers
35
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
0
answers
30
views
Are $L' = \{uu| u \in P \} $ and $L" = \{uuu| u \in P \}$ context-free languages?
$P$ is the set of all palindrome words.
I tried using pumping lemma for context-free languages on $L'$. I've distinguished two possible cases:
(Factors = $uvwxyz$)
(Iterating factors = $v$ and $x$)
...
0
votes
2
answers
99
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.
...
- 305
0
votes
1
answer
51
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
175
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
54
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, ...
- 305
-3
votes
1
answer
44
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}...
- 1
-2
votes
1
answer
33
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. ...
- 1
0
votes
1
answer
41
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 ...
- 1
1
vote
2
answers
254
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^{...
- 1
-3
votes
1
answer
38
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
32
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
31
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
486
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 |...
0
votes
1
answer
69
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 ...
- 1
0
votes
1
answer
28
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 ...
- 3
0
votes
0
answers
28
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 ...
- 1
0
votes
1
answer
51
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$...
- 25
0
votes
2
answers
49
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 ...
- 1
1
vote
1
answer
172
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 ...
- 89
0
votes
2
answers
108
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:
...
- 7
0
votes
1
answer
33
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 ...
0
votes
1
answer
69
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 ...
-2
votes
1
answer
55
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.
1
vote
3
answers
369
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, ...
- 239
1
vote
1
answer
118
views
variable repetitions in pumping lemma for context-free languages
Above is the proof of the pumping lemma for context-free languages, coming from the book 'Formal Languages and automata' by Peter Linz.
The picture below is in support of the proof.
I do not ...
- 47
0
votes
0
answers
35
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 ...
- 239
-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 ...
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$.
...
-3
votes
1
answer
237
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|\...
- 121