Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [pumping-lemma]

The tag has no usage guidance.

0
votes
2answers
116 views

Prove that a language is not context free

I was solving some hard exercises on context free grammer. Consider the language L={w∈{a,b}^{*} :the length of the longest substring of all b’s in w is longer than any of the length of substring of ...
3
votes
1answer
326 views

proving {$a^ib^jc^k |\;j=i\;or\;j=k$} is not regular

{$a^ib^jc^k |\;j=i\;or\;j=k$} what i tried so far was first splitting it into {$a^ib^jc^k |\;j=i$} or {$a^ib^jc^k |\;j=k$} then tried to use the pumping lemma to prove it. However i couldnt get very ...
2
votes
1answer
87 views

General question about pumping lemma statement for regular languages

According to the formal statement of the lemma here: https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages It is written at (3) that for all $i≥0, xy^iz∈L$. Until this ...
1
vote
1answer
27 views

L = { u#w | u != w} context-free

So i am trying to proove that L = { u#w | u != w } (from {a,b}* ) is not a contex-free language. With the pumping lemma i tried a^p # a^r , but how can i pump so they would become equal. Or can I ...
1
vote
1answer
22 views

Proving a Context Free Language

I need to prove whether a Language L = $a^ib^jc^k$ ( with i = j x k ) is context Free. I am using the pumping lemma to prove that this is not a CFL. Currently I have been able to prove in the ...
1
vote
1answer
89 views

Finding string in Pumping Lemma

I'm trying to prove that the Language $L_1$ = $\{1^m :$ m is not a perfect square$\}$ is not regular. I proved before that L = $\{1^m :$ m is a perfect square$\}$ is not regular, I thought that I ...
1
vote
1answer
309 views

Need some explanation of Pumping lemma for CFL

I need some help with the understanding of Pumping Lemma for CFL L = {all words over $\{a,b,c\}$ s.t. $n_a=n_b+2n_c\}$ where $n_a$ stands for number of $a$,$n_b$ - number of $b$ and $n_c$ number of $...
0
votes
1answer
77 views

Proof verification of the language of all palindromes as being context-free

Consider that the language L of all palindromes over $\Sigma = \{0,1\}^*$ is not context-free. The following is my attempt at a proof by contradiction. I am new to proof writing and I am wondering ...
0
votes
1answer
19 views

Prove using the Pumping Lemma

Can I prove that the language of the palindromes in the alphabet consisting of the ASCII symbols is not regular by proving that L = {$1^n21^n$ | n⩾0} is not a regular language?
0
votes
1answer
115 views

Show that $\{a^i b^j c^k \mid i>j>k>0\}$ is not a context free language by using pumping lemma

$\{a^i b^j c^k \mid i>j>k>0\}$ is not a context free language. I attempted to try this, but I keep on getting stuck. I was planning on solving it like a pumping lemma question for grammar, ...
0
votes
1answer
43 views

If $A$ is not a regular language and $B$ is a regular language and $B \neq \varnothing$, does $AB$ is not regular language?

I am trying to proof that $L = \{ 0^11^2...0^{n-1}1^n0^{n-1}...1^20^1\}$ where $n >= 0$ is not a regular language. So my method is to put $S = 0^11^2...0^{n-1}$ $W = S1^nS^R$ And then proof $S^...
0
votes
1answer
136 views

Prove that $L= \{w|$ $w $ ends with a palindrome of length greater than or equal to $4\}$ is nonregular using the pumping lemma.

The alphabet is $\{a, b\}$ Hi, I tried this: Assume to the contrary that $L$ is regular. Let $p$ be the pumping length given by the pumping lemma. Let $s$ be the string $a^{p}ba^{p}$. Because $s$ is ...
0
votes
1answer
36 views

Language that is CFL by Odgen but not by pumping lemma

I recently studied about Odgen's lemma and the pumping lemma. I deduced that Ogden's lemma is a general form and was interested: Is there a CFL language by Odgen's but not by the pumping lemma?
0
votes
1answer
38 views

$A= \{w \in \{a, b\}^∗ \mid \text{length of $a \leqslant 5$ and length of $b \leqslant 20$}\}$

I came across this proof-question to check the regularity of the following language: $A= \{w \in \{a, b\}^∗ \mid \text{length of $a \leqslant 5$ and length of $b \leqslant 20$}\}$ I tried first ...
0
votes
1answer
80 views

Pumping lemma proof and minimum length

What is the minimum pumping length for L=(0+1)1*0 ? I'm guessing it's 2 (since it's shortest word is 00), but how do I then split into word = xyz and pump it so that it still stays in?
0
votes
1answer
397 views

How to calculate the minimum pumping length for some L?

Prove that the following language holds the pumping lemma for context-free languages: (Although it is not context-free) L is a language under alphabet {a,b,c,d} L={$a^ib^ic^j$ : i,j $\ge$ ...
0
votes
1answer
36 views

Given language, say if it is regular, context-free and proove it.

I have the following language: $L = \{a^{2m + k}b^{3n+\ell}c^{m+n} \mid \ell\leq3 \space\text{and}\space k\gt2\space\text{and}\space m,n \in\mathbb{N}\}$ Is it regular? Is it context-free? What I ...
0
votes
1answer
399 views

prove that l={w ∈ {0, 1}*: n0(w) ≠ n1(w)} is a non regular language?

I tried doing this, but kept failing to prove. I know how to prove that the language is nonregular when n0(w) = n1(w). The following is the proof for n0(w) = n1(w) using pumping lemma: ...
0
votes
1answer
29 views

Proving that a certain language is or is not regular using pumping lemma

I have a language defined by $L = \{ a^{m}b^{n}:m,n \in N_{0}\}$ This means I have 3 cases: $1) \ m > n$ $2) \ m < n$ $3) \ m = n$ So I have to prove it in 3 different cases. Taking case 1 ...
0
votes
1answer
266 views

Pumping Lemma problem solved, but explanation appreciated. (Finite automata)

I have a problem that a friend helped solve but I did not entirely follow the explanation. I would hope someone could break it down for me. I understand the gist of the PL, but I do not understand how ...
0
votes
1answer
101 views

Pumping Lemma - non regular

Can everyone help me to show that: the language $$L = \{a,b\}^* \setminus \{a^m b^{2m} a^n\mid m,n \ge 0\}$$ is not regular. I don't know what is the meaning for the proof.
0
votes
1answer
44 views

What exactly is a pumping lemma and how do you do one

So I have a pumping lemma question A{www|w ∈ {a,b}*} I have the correct answer but I'm not fully sure how it works. I'll give the answer just so people know what I'm going with Assume A is REG let p ...
0
votes
1answer
182 views

Pumping lemma for context free. How do I define the string 'w' and define cases?

I am new to the pumping lemma for context free grammars. I have read books and researched online about the pumping lemma, however I am finding it difficult to understand the actual concept and how to ...
3
votes
0answers
114 views

Searching for a proof for a variant of the pumping lemma for context free languages

So I'm trying to understand the pumping lemma for CFL ( context free languages ).I've already used it to show that a language is not contextfree and I have considered the proof of this lemma (see the ...
2
votes
0answers
70 views

prove that your language is not regular by using the Pumping Lemma, $L = \{x \in \{0, 1\}^* | x = x^R \}$

prove that your language is not regular by using the Pumping Lemma, $L = \{x \in \{0, 1\}^* | x = x^R \}$ proof: Let $L = \{x \in \{0, 1\}^* | x = x^R \}$ Suppose L is a regular language let $x = ...
2
votes
0answers
59 views

Pumping lemma: Convert pumped, binary string $xy^iz$to integer

I am trying to use the pumping lemma to prove that the language consisting of the set of $0$'s and $1$'s, beginning with a $1$, such that when interpreted as an integer, that integer is prime, is not ...
1
vote
0answers
32 views

Proving that $L=\{xww^r\mid x,w \in \{0,1\}^+\}$ is not regular

In the alphabet $\Sigma=\{0,1\}$, I need to prove that this language is not regular. I've tried using the pumping lemma, choosing the string $a(ab)^p(ba)^p$ for a given $p$, any possible choose of a ...
1
vote
0answers
50 views

PL to prove a language is not regular

Prove that the following language L over alphabet $\{1\}$ is not regular. $L = \{w \mid |w| = k, \text{ where } k \text{ is a prime number}\}$ Suppose the language is regular for contradiction. Since ...
0
votes
0answers
16 views

Proving language is not context free using pumping lemma

Hi I'm completely stuck on an exercise which is to prove this language is not context free using pumping lemma for context free languages: ...
0
votes
0answers
17 views

Understanding the pumping lemma for CFL

I'm having a hard time with understanding the pumping lemma for CFL. I found this online and can't wrap my head around how it works. ...
0
votes
0answers
36 views

Help with a proof using the pumping lemma

I am confused with even starting the proof. I understand the pumping lemma: Let A be a language over $\Sigma$. If A is regular, then there exists $p > 0$ (pumping length) such that $∀s∈A$, if $|...
0
votes
0answers
40 views

Verification of “Prove/Disprove that the language $L = \{ a^kba^{2k}ba^{3k} | k \geq 0\}$ is context free.”

I attempt to show that the language $L = \{ a^kba^{2k}ba^{3k} | k \geq 0\}$ is not context free by applying the Pumping lemma for context-free languages. This is achieved by a proof by ...
0
votes
0answers
31 views

How to prove that $L=\{a^kb^mc^{m-k}|m\ge k\ge0, m-k\ge k\}$ is not context-free language?

Prove that $L=\{a^kb^mc^{m-k}|m\ge k\ge0, m-k\ge k\}$ is not context-free language. We can suppose by contradiction that $L$ is context-free and choose $Z=a^kb^{2k}c^k$. Using pumping lemma, $vwx$ ...
0
votes
0answers
30 views

Why is this choice of $y$ not permitted in using pumping lemma?

Consider this snippet shown below from, An Introduction to Formal Languages and Automata 6th Edition by Peter Linz. As per the text, choosing a value of $y = a^k$, where $k$ is odd is not permitted ...
0
votes
0answers
26 views

To show that language is not regular using pumping lemma

L = $\left \{ a^{n}b^{n} : n \geq1 \right \}\cup \left\{a^{n}b^{n+2}: n \geq1\right \}$      L = $\left \{ a^{n}b^{n}(\lambda+bb) : n \geq1 \right \}$      Assuming L is a regular language. Let p be ...
0
votes
0answers
32 views

Determining if langauge is regular using pumping lemma

I have language $L =\{ a^{3i} : i \in N_{0}\}$ if we choose sentence $a^{3p}$ We can decompose it such as $x = a^{k}$ where k >= 0 $y = a^{l}$ where l >= 1 $z = a^{m}a^{3p-p}$ where m >= 0 ; k +...
0
votes
0answers
95 views

Prove Prime' does not satisfy the Pumping Lemma

I have these two questions regarding the pumping lemma which, I do not quite fully understand. I was hoping someone can guide me through these questions. $PRIME$ = {$a^i$ where $i$ is a prime number} ...