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
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 ...
Max Azatian's user avatar
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 ...
Priit's user avatar
  • 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 ...
Priit's user avatar
  • 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 ...
Keroten's user avatar
  • 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 ...
user69507's user avatar
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\...
user8718165's user avatar
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)\; \...
dvox's user avatar
  • 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| ...
M a m a D's user avatar
  • 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 ...
user1701057's user avatar
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 ...
user1701057's user avatar
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\}...
Aishgadol's user avatar
  • 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 ...
Axo's user avatar
  • 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 ...
totti00's user avatar
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 ...
GuestPersonOnThisShow's user avatar
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-...
Marco Campanella's user avatar
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 ...
Pratik Hadawale's user avatar
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 ...
Marco Campanella's user avatar
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 ...
Marco Campanella's user avatar
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 ...
Pratik Hadawale's user avatar
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 ...
Pratik Hadawale's user avatar
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?
SmallBrainStudent's user avatar
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$) ...
Marco Campanella's user avatar
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. ...
Pratik Hadawale's user avatar
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 ...
Marco Campanella's user avatar
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 ...
David Krell's user avatar
-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, ...
Pratik Hadawale's user avatar
-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}...
Papa's user avatar
  • 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. ...
Papa's user avatar
  • 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 ...
Papa's user avatar
  • 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^{...
Papa's user avatar
  • 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.
emrb99's user avatar
  • 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 ...
emrb99's user avatar
  • 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 ...
Sahar Ramezani's user avatar
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 |...
mathsdepression's user avatar
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 ...
80s's user avatar
  • 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 ...
S.web's user avatar
  • 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 ...
kk1997's user avatar
  • 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$...
cs_student's user avatar
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 ...
apex's user avatar
  • 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 ...
Ronald's user avatar
  • 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: ...
tomato's user avatar
  • 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 ...
Clair Goodman's user avatar
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 ...
Clair Goodman's user avatar
-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.
ZisIzHell's user avatar
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, ...
Math4me's user avatar
  • 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 ...
Tryer outer's user avatar
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 ...
Math4me's user avatar
  • 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 ...
Emma Carter's user avatar
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$. ...
Andrei Hodoroaga's user avatar
-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|\...
Dolev Dublon's user avatar

1
2 3 4 5
11