Questions tagged [pumping-lemma]
The pumping-lemma 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 ...
