Questions tagged [pumping-lemma]
The pumping-lemma tag has no usage guidance.
0
votes
0answers
27 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
48 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
47 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
33 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
30 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
21 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
39 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
28 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
17 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
43 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
30 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
12 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
39 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
62 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
56 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
65 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
66 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
40 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
95 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
29 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
45 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
33 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
36 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
52 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
33 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
25 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
39 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
72 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
349 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
80 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
234 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
145 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
55 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
42 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
95 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
286 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
107 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
83 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
272 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
342 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
166 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
138 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
275 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
74 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)?
0
votes
1answer
565 views
Pumping Lemma for Regular Languages confusion: do I need to prove the case for a single $y^i$, or a set of them?
I am misunderstanding if one requires, for the pumping lemma proof by contradiction to apply, to prove only a single case of $y^i$, or a specific set. Namely, if I show that, at some point, provided $...
