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
1answer
25 views

Pumping lemma L={$a^i$ $b^j$, / 0<j<i<infinity}?

How to prove that above language is not regular. I tried using pumping lemma but am not able to prove and what to select as initial string. I also searched for other answers but this question is not ...
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 $|...
2
votes
2answers
54 views

context free language prove or disprove

I have to prove or disprove that for every language $L$ which has the properties: for every non-prime length there is at least one word in L. for every prime length none of the words are in L. is ...
0
votes
1answer
50 views

Pumping Lemma - unregular expression

How do prove that this expression is unregular, I know firstly you have to try prove that it is regular and work from there. I also know that $w=xuz$ and the three rules are needed Let $M$ be the ...
0
votes
0answers
38 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
1answer
31 views

Is $L_4$ a CFL?

Consider the following language: $$L_4 = \{a^ib^jc^kd^l : i,j,k,l \ge0 \wedge i=1 \Rightarrow j=k=l\}.$$ Prove or disprove: $L_4$ is a context-free language. To me, it looks like $L_4$ can be ...
0
votes
0answers
24 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
1answer
65 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
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
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?
3
votes
0answers
111 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 ...
0
votes
1answer
36 views

Pumping Lemma for CFL

So I solved some exercises where I have to use the pumping lemma for contextfree languages but this one is a problem for me: Consider: $ L = $ { $w_1£w_2£w_3 \in$ { $0,1,£$}$^*$ | $w_1, w_2, w_3 \...
0
votes
1answer
15 views

How to determine the beginning of $uv^iw$ in the pumping lemma for regular languages?

Let $\sum=\{a,b,c,d\}$, $L=\{a^ib^jcd^k \big| i\ge0; k>j>0\}$. Prove that $L$ is not regular using pumping lemma. We can choose the word $Z=a^0b^{n}cd^{n+1}=b^{n}cd^{n+1}\in L$. Let $uvw$ be ...
2
votes
0answers
63 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 = ...
0
votes
2answers
105 views

Use Pumping Lemma to show that $L_7$ is not context-free

I was studying an old test and struggled to answer this question: Let $L_7$ be the language $\{ w@y \mid y \text{ is a substring of } w\}$, where $w, y \in \{c,d\}^*$. Use the Pumping Lemma for ...
0
votes
1answer
101 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
68 views

Prove that Language is not regular using pumping lemma

Let's have this language: $ L= \{ w_1 @ w_2 | w_1,w_2 \in \Sigma^*, \#_1(w_1)+(2*\#_2(w_1))=\#_1(w_2) + (2*\#_2(w_2)) \}$ $\Sigma = \{0,1,2\} \cup \{@\} $ I need to prove that this language is not ...
1
vote
1answer
116 views

How to proof language which consists of concatenation of strings in palindrome is not a regular language?

How to proof $L = \{ x \in \Sigma^* | x=y_1\cdot y_2 \cdot \dots y_m, \exists m \ge 1 \,\land \forall y_i \in \text{Palindrome over } \Sigma^*\}$ is not a regular language? My attempted is $\text{Let ...
0
votes
1answer
41 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
176 views

Simply starred language. $\left\{(ab)^n:n\in\mathbb{N}\right\}$ it is regular?

I have many doubts with this. First: In the definition, let $A=\left\{x\right\}$ one-letter alphabet. Then $A^{\ast}$ is simply starred? Second: In the definition, I know that $\left\{a^nb^n: n \in \...
0
votes
1answer
129 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
34 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?
1
vote
1answer
48 views

i really don't know how to get $s = xyz$ for pumping lemma for this language

Let $L=\{a^i b^j c^k d^l : i, j, k, l > 0, 3(i+j) \geq 2(k+l)\}$. Proof that this language is not a regular language. I have no clue, cause i can't find any example for $3(i+j) \geq 2(k+l)$ or ...
0
votes
1answer
36 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 ...
2
votes
0answers
53 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
29 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 ...
2
votes
2answers
57 views

is a fractional i allowed in pumping lemma??

I checked the pumping lemma in many books(introduction to the theory of computation Michael Sipser) and website(wikipedia). they all give the same explanation:(definition from introduction to the ...
0
votes
1answer
64 views

Proving language is not regular using pumping lemma

Show that the language                     $L =$$\left \{ a^{n!} : n\geq 1 \right \}$ is not regular using pumping lemma My solution is : Suppose L is regular There exist some pumping length for L,...
1
vote
0answers
44 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
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
1answer
44 views

Pumping lemma for $L=\{a^{p}b^{q} ∣ 0 ≤ p ≤ q\}$

Using the pumping lemma for $L=\{a^{p}b^{q} ∣ 0 ≤ p ≤ q\}$ I need to prove that $L$ is irregular. I already have proven the irregularity for $L=\{a^{p}b^{q} ∣ 0 ≤ p < q\}$. I have a gut feeling ...
0
votes
1answer
78 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
389 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 ...
-3
votes
1answer
88 views

Is $0^m1^n$ a regular language? [closed]

A language is defined as $w = \{ 0^m1^n \mid m, n \in \Bbb N \}$. Is this a regular language? I have seen people proving for both the sides. Thread saying it is regular Proof for it being non-...
3
votes
1answer
277 views

Pumping lemma for regular language

On an exam we got this question: Let $B = \{w \in \{a,b\}^* : w \neq w^{rev}\}$ Prove $B$ is not regular. I only got 1 of 4 pts on this question and the teachers comments are below. My solution: ...
1
vote
2answers
155 views

How to prove this language is not context free?

$$L=\{a^{nm} \mid \text{$n$ and $m$ are prime numbers}\}$$ How can i prove $L$ is not context free? I tried pumping lemma but couldn't find an i that $uv^ixy^iz \notin L$. Any idea or hint on how ...
2
votes
1answer
66 views

a version of pumping lemma

I need some assistence with h.w: Given $L\in L _{reg}$. Prove that there exists an instance $N\in\mathbb{N}$ such that $\forall w \in L$ such that $N\leq |w|$ there exists a division of $w$ for 4 ...
0
votes
1answer
43 views

What strings can be used in pumping lemma?

I just got my homework back after correction and I can't figure out why this questions was wrong. I need to say if I can prove that the language ${L=\{w\in \{0,1\}|w}$ has more 0's than 1's} is not ...
2
votes
1answer
107 views

Choosing $x$, $y$, $z$ parts in a pumping lemma $w$ string

I want to proof that $L = \left\{u0v \mid u, v \in \{0, 1\}^* \land \#_1(u) = \#_0(v) \right\} $ is not regular. But my understanding of the pumping lemma is somehow not bulletproof, so I'm not sure ...
3
votes
1answer
310 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 ...
0
votes
1answer
113 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 ...
1
vote
1answer
88 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 ...
0
votes
1answer
303 views

Prove that $L = \{ a^nb^m : m = n^3 \}$ is not Context Free using Pumping Lemma

I have the following language: $L = \left \{ a^nb^m : m = n^3, i,j > 0 \right \}$ Show that it is not Context Free using Pumping Lemma for Context Free Languages. This is what I have done. I ...
0
votes
1answer
387 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
193 views

Pumping Lemma does not hold for the regular expression $101$, or similar?

So I am reading a book about Computational Theory, and I came across the Pumping Lemma. This is the formal definition of the lemma as stated in the book: Let $A$ be a regular language. Then ...
1
vote
3answers
165 views

Trouble with Pumping Lemma

I need to know if this language $$ L = \{ \ (a^2b^2c^2)^n \mid n > 0\ \} $$ is regular or not. Since it is trivial to design an FSA with a loop that accepts that language, it is regular. For ...
1
vote
1answer
297 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 $...
1
vote
1answer
77 views

Show that the language $\{w \in \{a,b\}^* : \#w_b = \#w_a + 2 \}$ is not regular using the Pumping Lemma

I have got a question. I have to proof that the given language is not regular and I am not sure I am doing it correct. The language is: $ L = \{w \in \{a,b\}^* : \#w_b = \#w_a + 2 \}$ So using ...
0
votes
1answer
45 views

Does$\{w\in\Sigma^*=\{a,b\}^*: \nexists u\in \Sigma^*, w=uu\}$ uphold the pumping lemma

I have the $L=\{w\in\Sigma^*=\{a,b\}^*: \nexists u\in \Sigma^*, w=uu\}$. Does it uphold the pumping lemma (regardless of it being regular or otherwise)?