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
0answers
6 views

Prove L = a^n b^m c^(max(n,m)) is not regular with pumping lemma

I have the language L = a^n b^m c^(max(n,m)) and I have to prove it is not regular by using the pumping lemma. I don't understand how to do it. If I have m>n, c should be ^m. Now I take the v string ...
0
votes
0answers
17 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
18 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. ...
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
27 views

(Pumping Lemma for Regular Languages) Is this proof that L is not regular?

I have a language $L$: $$L = \{w : a^ib^j; i > j \}$$ I need to prove this language is not regular using Pumping Lemma. I need to find a suitable $w$, where $|w| \ge $ some $p$ $w = a^{p+1}b^{...
1
vote
1answer
25 views

Is this enough to prove that the language L is not context-free? (Pumping lemma for CFL's)

The language $L = a^nb^nc^n | n>=1$ We assume that the language $L$ is context-free. Then it must satisfy these conditions: We can break any string $Z$, where $|Z| >= p $ into 5 substrings: $...
1
vote
1answer
23 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 ...
0
votes
3answers
62 views

Prove that the language L is not a regular language, using pumping lemma

I have a language $L$: $$L = \{w : a^ib^j; i > j \}$$ I need to prove this language is not regular using Pumping Lemma. I'm wondering if I'm doing it correctly: I need to find a suitable $w$, ...
0
votes
1answer
28 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
62 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
52 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
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
1answer
33 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
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
1answer
78 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
116 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
39 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
18 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
71 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
123 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
116 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
72 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
124 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
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
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
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?
1
vote
1answer
51 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
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 ...
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 ...
2
votes
2answers
63 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
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
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
47 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
84 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
407 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
37 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
91 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
287 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
161 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
111 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
327 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
2answers
117 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 ...