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
0 votes
1 answer
69 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$ ...
Aishgadol's user avatar
  • 345
1 vote
3 answers
375 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 ...
Librapulpfiction's user avatar
2 votes
1 answer
261 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 = ...
Juan's user avatar
  • 23
0 votes
1 answer
33 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 ...
Robert's user avatar
  • 57
2 votes
2 answers
358 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 ...
Robert's user avatar
  • 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 $|...
Robert's user avatar
  • 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 ...
user167205's user avatar
0 votes
1 answer
39 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}$?
Robert's user avatar
  • 57
0 votes
0 answers
26 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 ...
Luca 's user avatar
  • 63
2 votes
2 answers
79 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 ...
Luca 's user avatar
  • 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 ...
Luca 's user avatar
  • 63
0 votes
1 answer
38 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 ...
CSStudent's user avatar
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 ...
Grandma Kisses's user avatar
-3 votes
2 answers
57 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 ...
user avatar
0 votes
1 answer
48 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. ...
Addem's user avatar
  • 335
0 votes
1 answer
155 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 ...
Aum Thakkar's user avatar
0 votes
1 answer
97 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 ...
Crypton99's user avatar
1 vote
1 answer
314 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
32 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. ...
Priit's user avatar
  • 1
1 vote
1 answer
58 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
46 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
80 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
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)\; \...
dvox's user avatar
  • 13
1 vote
1 answer
381 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,519
0 votes
1 answer
97 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
41 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
147 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
  • 345
0 votes
1 answer
60 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
50 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
50 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
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-...
Marco Campanella's user avatar
0 votes
1 answer
54 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
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 ...
Marco Campanella's user avatar
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 ...
Marco Campanella's user avatar
1 vote
2 answers
139 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
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?
SmallBrainStudent's user avatar
0 votes
2 answers
150 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
131 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
370 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
66 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
46 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
  • 105
-2 votes
1 answer
52 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
  • 105
0 votes
1 answer
47 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
  • 105
1 vote
2 answers
497 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
  • 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.
emrb99's user avatar
  • 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 ...
emrb99's user avatar
  • 1
-1 votes
1 answer
81 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
889 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
75 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
30 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

1
2 3 4 5
11