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.

4
votes
2answers
918 views

Pumping Lemma for $L= \{a^{m}b^{n}| m,n > 0 , \gcd(m,n) > 1 \}$

Let language $L= \{a^mb^n \mid m,n > 0 , \gcd(m,n) > 1\} $ above the alphabet $\Sigma = \{a,b\} $ . I need to prove by the pumping lemma that $L$ is not a regular language but I am having ...
3
votes
2answers
165 views

Prove that the language is not regular using pumping lemma

Could anyone explain me how to prove that this language is not regular using pumping lemma? I can prove easier examples but with this one I do not even know with which word i should start proving it. ...
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: ...
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 ...
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 ...
2
votes
1answer
491 views

Proving a language is not context-free (pumping lemma)

below is my attempt at applying the pumping lemma to a language to prove that it is not context-free. I am new to using the pumping lemma, especially for context-free languages. My question is, is ...
2
votes
3answers
620 views

Can I prove, using Pumping Lemma, that $L=\{ a^i b^j a^j b^k | i,j,k \ge 1 \}$ is not a regular language?

By pumping lemma, we have that for each sufficiently large $z \in L$, there exists $u, v$ and $w$ such as $z=uvw$, whith $|uv| \leq p$, $|v| \ge 1$ and $uv^iw \in L$, for each $i \ge 0.$ ($p$ is the ...
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 ...
2
votes
1answer
102 views

Prove that a language is not regular

I want to prove that $L$ is not regular: $$L = \{ww^Rv \mid |w|\ge1 , |v|\ge 0\},$$ where the alphabet contains at least two symbols. Can someone prove it? I prefer to use "Pumping Lemma for Regular ...
2
votes
2answers
333 views

Prove that $\{w \mid \text{ w has even length and the first half of w has more 0s than the second half of w} \}$ is not regular?

I have had some difficulties understanding proofs that a language is not regular using the Pumping Lemma, and now I need to prove that the following language $$A = \{w \mid \text{ w has even length ...
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 ...
2
votes
1answer
103 views

Prove that this language is regular or not

I have a language as follows: $L = \{ ww^Rw \mid w \in \{a,b\}^*\} $ I believe that the language is not regular, since designing a DFSM for it is not possible. To prove that the language is not ...
2
votes
1answer
436 views

disprove $L = \{ a^nb^n\mid n \geq 0 \}$ is not a context-free using Pumping Lemma for Context-Free Languages

I am writing something about Pumping Lemma. I know that the language $L = \{ a^nb^n\mid n \geq 0 \}$ is context-free. But I don't understand how this language satisfies the conditions of Pumping Lemma ...
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 = ...
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 ...
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 ...
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 ...
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
469 views

A regular language that isn't pumpable?

I have moderate understanding of the lemma's use in prototypical examples like $0^n1^n$ and $WW$ (for any string $W$). I have some confusion about the lemma's application to regular languages that ...
1
vote
2answers
469 views

Is $L_1 = \{w ∈ {0,1}∗ | \text{w has at least as many occurrences of (110)’s as (011)’s}\}$ regular?

Let $L_1 = \{w ∈ \{0,1\}^∗ | \text{w has at least as many occurrences of (110)’s as (011)’s}\}$. Let $L_2=\{w ∈ \{0,1\}^∗ | \text{ w has at least as many ...
1
vote
1answer
60 views

Is $L=\{o^{i}1^{i}o^{j}1^{i} | i,j>0\}$ a context free language?

I need to find and to prove (by the pumping lemma or by building a grammar) if $L=\{o^{i}1^{i}o^{j}1^{i} | i,j>0\}$ is a context free language. I would like to get some help. thanks!
1
vote
3answers
168 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
51 views

How to show that the language containing the words which number of $b$ divides the number of $a$ isn't regular using pumping lemma?

How to show that the language containing the words which number of $b$ divides the number of $a$ isn't regular using pumping lemma ? The pumping lemma says that Let be $M$ a regular language. ...
1
vote
1answer
2k views

Use Pumping Lemma to prove that the language with strings of the same number of 0 and 1 is not regular

Use the Pumping Lemma to prove that the following language on $\Sigma = \left \{ 0,1 \right \}$ is not regular. $L = \left \{ w \, | \, w \mbox{ has the same numbers of 0 and 1} \right \}$ not in any ...
1
vote
1answer
26 views

Is it possible to build a context-free grammar for the following language?

I'm trying to solve a computational problem for which I need to build pushdown automata that accepts language: $0^n1^n2^i$, where $n \leq i \leq 2n$. Is it possible?
1
vote
1answer
99 views

Is $L=\{o^{i}1^{j}o^{j}1^{k}o^{k}1^{i} | i,j,k>0\}$ a context free language?

I need some help in finding and proving (by the pumping lemma or by building a grammar) if $L=\{o^{i}1^{j}o^{j}1^{k}o^{k}1^{i} | i,j,k>0\}$ is a context free language. thanks!
1
vote
1answer
35 views

Proving this language is non context-free

How can I prove that the language $\{ab^kab^kab^k\subset \{a,b\}^* | k \geq 0\}$ is non context-free? I've tried applying the pumping lemma but can't write a proof without considering multiple ...
1
vote
1answer
126 views

Proving that $\mathscr L=\{0^n \big|\text{n is the square of a natural number }\}$ is non regular using the pumping lemma

I need to prove that the language $\mathscr L=\{0^n \big|\text{n is the square of a natural number}\}$ is non regular using the pumping lemma My try: $\mathscr L=\{\overbrace{\epsilon}^{0^2},\...
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
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 ...
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 ...
1
vote
1answer
81 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 ...
1
vote
1answer
767 views

The language L = { $a^nb^mc^n$ | $m \ge n$ } is not context-free. Pumping Lemma through 6 cases.

This is the Pumping Lemma for Context Free Languages I refer: For all context free languages $L$ there exists some $k \in \mathbb{N} \mid \forall z \in L$ with $\left | z \right | \ge k$, there ...
1
vote
1answer
213 views

The Language {xx}, of any string followed by another copy of the same string, is not Context Free. Using Pumping Lemma, through 13 cases.

I write here the Pumping Lemma for Context Free Languages I refer: For all context free languages $L$ there exists some $k \in \mathbb{N} \mid \forall z \in L$ with $\left | z \right | \ge k$, ...
1
vote
2answers
4k views

Union of two non-regular languages.

Can the union of two non-regular languages be regular?? I have $L_1 = \{a^i b^j \mid i > j\}$ and $L_2 = \{a^i b^j \mid i < j\}$. I am using Pumping lemma with $s = a^{p+1} b^p$ for $L_1$ and $s ...
1
vote
1answer
156 views

Prove that language is not context free

Could you give me any tip (not a solution) how to prove that the language of even length words over the alphabet $\{ 0, 1 \}$ such that the number of $1$ in the first half is equal or greater than the ...
1
vote
1answer
151 views

Show a language is not regular by using the pumping lemma

Show the following language is not regular by using the pumping lemma $A_1=\{0^n1^n2^n|n \geq 0\}$ Proof by Contradiction: Assume $A_1$ is Regular. Let M be the pumping length and let S be a ...
1
vote
1answer
122 views

Proving regularity with pumping lemma

I have to prove , that language is not regular using pumping lemma. $L = \{ ccc a^k b^l , k > 2 , l >= k \}$ the language i choose is $ccca^{p+2}b^{p+3}$ So i should have multiple ...
1
vote
1answer
47 views

Using pumping lemma to prove a set of substrings cannot be expressed as a regular expression…

I'm trying to use the Pumping Lemma of regular expressions to prove the set of all finite substrings in the infinite string 012001122000111222000011112222... is not regular. E.g. 0120 and 20001 are ...
1
vote
1answer
39 views

Pumping lemma to prove the set of all words such that the sum of the number of 0s and 1s occurring in it is an even number is not regular

In the alphabet {0, 1, 2}, how can I prove using the pumping lemma that there is not a regular expression that can describe the set of all words such that the sum of the number of 0s and 1s occurring ...
1
vote
1answer
121 views

negating propositional formula with quantifiers

In order to solve an exercise in computer sciences (proving a language $L$ to not be context-free) I need to negate the Pumping-Lemma. I was provided with the definition in the following form: If $L$ ...
1
vote
1answer
269 views

Pumping Lemma clarification, and regularity of language of equal number of zeros and ones.

All explanations and proofs I find about the Pumping Lemma are ambiguous. So if I understand this correctly, if we can find some $p>0$, then for any string $|w| \ge p$, we should be able to split ...
1
vote
1answer
36 views

How to proof using only pumping lemma that something is not regular?

In formal languages I need to proof using the pumping lemma that the following is not regular: $A_1=\{1^m0^n10^n|n,m\in \mathbb{N}\}$ How to achieve that? Any help is upvotet
1
vote
1answer
69 views

Regular Pumping Lemma

$$\begin{align*} L&=\left\{b^5w:w\in\{a,b\}^*,\big(2n_a(w)+5n_b(w)\big)\bmod 3=0\right\}\\ L&=\left\{(ab)^na^k:n>k,k\ge 0\right\} \end{align*}$$ Determine if each language is regular or ...
1
vote
1answer
47 views

Proving that the language $\{w\in \{a,b\}^* \big|\#_a(w)< \#_b (w)\}$ is non regular using the pumping lemma

I need to prove that the language $\mathscr L=\{w\in \{a,b\}^* \big|\#_a(w)< \#_b (w)\}$ is non regular using the pumping lemma My try: $\{a,b\}^*=\{\epsilon,a,b,aa,ab,ba,bb,aaa,aab,\dots\}$ ...
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
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 ...
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 ...
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 ...