Questions tagged [pumping-lemma]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
38 views

Is $L_2=\{w^*\,:\,w\in L_1\}$ where $L_1$ is regular, a regular language?

Is language $L_2=\{w^*\,:\,w\in L_1\}$, where $L_1$ is regular, regular? Intuitively it seems that it's not: the automaton accepting $L_2$ would most probably just be a loop made from an automaton ...
user avatar
  • 33
0 votes
1 answer
31 views

How to prove that a language is not context-free using pumping lemma?

How could I realize this using the pumping lemma? What if the pumping part is between b and c or between a and b so that after pumping the word is still in L?
user avatar
0 votes
1 answer
57 views

My proof of $\{a^p|p~~\mathbb{is~~prime}\}$ is not a CFL.

I want to show that the language $L=\{a^p~|~p~~\mathbb{is~~prime}\}$ is not a CFL. Assuming towards a contradiction that $L$ is a CFL. Let $p$ be the number from the Pumping lemma for context-free ...
user avatar
  • 656
0 votes
0 answers
78 views

How can I prove that L = {w ∈ {a, b, c, d} ∗ | #a(w) = #b(w) = #c(w) = #d(w)} is not context-free without using the pumping lemma?

I am stuck on this problem, I can prove it using the pumping lemma, but I'm wondering if I can also prove it using closure properties
user avatar
0 votes
0 answers
28 views

Prove non regularity of the language a^n where n is an even or a prime number, with the pumping lemma

How to prove that the language that is the union of the language where $n$ is an even number and the language where $n$ is a prime number is non-regular with the pumping lemma? I know how to prove ...
user avatar
2 votes
3 answers
144 views

Proving a language is not regular using the pumping lemma

Let $$ L =\Big\{ \ ba^{2^k}b^{i_1}ab^{i_2}a\dots b^{i_k}a \ \Big|\ k\ge 1,\ i_j\ge1 \ ,\ 1\le j \le k\ \Big\}\ . $$ Using the pumping lemma prove that $L$ isn't regular. The answer given to this ...
user avatar
0 votes
1 answer
39 views

Pumping lemma: if you pump to $uv^0wx^0y$, wouldn't $|vx| \ngeq 1$?

For pumping lemma for CFLs, for strings $s$ in $L$, they follow the form $s = uvwxy$ and $|vwx| \leq n$, $|vx| \geq 1$, and $uv^iwx^iy \in L$ for $i \geq 0$. If I want to prove a language is not CFL, ...
user avatar
  • 1,713
1 vote
2 answers
74 views

Failure of context-free pumping lemma of $a^nb^n$

I know $a^nb^n$ with $n\geq0$ is considered a context-free language, but if I try: Using pumping length $p = 3$ $n = p$, thus we have $aaabbb$ $u =aa$ and $y = bb$ $v = a$, $w = b$ and $x=λ$, then $|...
user avatar
0 votes
1 answer
51 views

Prove that $L=\{a^n b^l : n \leq l\}$ is not regular by pumping lemma

I'm currently trying to prove that $L=\{a^n b^l : n \leq l\}$ is not regular by pumping lemma My proof: If we choose $w$ such that $w=a^P b^P$, then since $|xy| \leq p$, $y$ must be $a^P$, meaning it ...
user avatar
  • 111
0 votes
0 answers
18 views

Pumping lemma on a regular language with different variables

I have this language $L = \{a^i b^j c^k ∣ i,j,k \geq 0 \text{ and } i+j=k \}$ I dont know how to replace $i,j,k $ with the pumping length p, usually when I make a string s with the pumping length p I ...
user avatar
  • 143
1 vote
1 answer
37 views

Solution verification: Proving that this language is irregular using the pumping lemma.

Prove that the following language with $\Sigma=\{a,b\}$, is not regular using the pumping lemma: $L=\{ba^{2^{k}}b^{i_1}ab^{i_2}...b^{i_k}a : k\ge 1, \forall j\space\space (1\le j \le k)\space\space ...
user avatar
  • 2,051
0 votes
0 answers
38 views

Proof of Pumping Lemma: Why can we set the pumping constant to the number of states?

I'm learning the proof of the Pumping Lemma for regular languages. The proof is carried out using an arbitrary string having length of at least the number of states in the DFA. As such: The language ...
user avatar
  • 1
1 vote
1 answer
198 views

a^m b^n c^n prove it's not regular/pumping lemma

How to prove that $L = \{a^mb^nc^n \mid n, m \geq 0\}$ is not regular by the pumping lemma My attempt: Let's suppose $L$ is regular. There exists a pumping constant p, and we choose $w = a^pb^pc^p$ ...
user avatar
0 votes
0 answers
13 views

Pumping Lemma-prove a language is not regular

The question is to prove that the Language below is not regular, and I have used the pumping lemma technique I wanted to know if this is the correct solution so the CFG for it is let the grammer be ...
user avatar
0 votes
3 answers
55 views

How can the following language be regular?

Lets assume the language $L=\{a^n b^m\}$ When we try proofing $L$ is regular using the Pumping lemma and say $w=xyz$ and thus for every $w=xy^iz $ , $w$ has to be $ \in L $. now if we say $y$ only ...
user avatar
0 votes
1 answer
28 views

Proof of context free Language

$$L:=\{w\in\{a, b, c\}^*| ∃ i, j ∈ N :w = a^i⋅b^i⋅c^j ∧ i < j\}$$ I am trying to prove/disprove that this is context free. I was sure this was not context free, since there are 3 pumping operations,...
user avatar
0 votes
1 answer
280 views

Prove that L={$a^p$: p is prime } is not regular using pumping lemma

https://cs.stackexchange.com/questions/145675/understanding-about-pumping-lemma-for-regular-language-confusions-of-beginner This the reference idea I have used in this proof. But I am very clear that ...
user avatar
  • 11
0 votes
1 answer
51 views

Is it true that for every regular language $L \subseteq \{0, 1\}^{*}$ the language $\{w^{|w|} |w \in L \}$ is also regular?

Is it true that for every regular language $L \subseteq \{0, 1\}^{*}$ the language $\{w^{|w|} |w \in L \}$ is also regular? I think the language is not regular because for a finite w we can easily ...
user avatar
1 vote
0 answers
52 views

Pumping Lemma for regular languages

Given is the the following language. $L= \{ wa^{\vert w \vert} \mid w \in \{a,b\}^* \cup L(b^*a^*)\} $ Task: Prove that $L$ is not regular using pumping lemma. I am not sure wether I did this ...
user avatar
0 votes
0 answers
37 views

Proving $\{0^m1^{2m}2^i | m > i \geq 0\}$ is not context-free using the pumping lemma

I want to prove that the language $\{0^m1^{2m}2^i\;|\;m > i \geq 0\}$ is not context-free using the pumping lemma. I know there are at least 3 contradictions that exist, all of which are when $v$ ...
user avatar
0 votes
0 answers
42 views

Pumping Lemma proof for this language: $L= \{a^ib^jc^{ij} \mid i, j \geqslant 0\}$

i have troubles to show that this language is not context free with the pumping lemma. As a word I chose: $a^mb^mc^{m^2}$ I solved all the cases but one, which is: "$vy$ contains $b$'s and $c$'s&...
user avatar
0 votes
0 answers
55 views

Use pumping-lemma to prove that L is not a context-free language

Show using the pumping lemma that L = { $w$$w^{R}$$w$ | $w\in$ {a,b}* $w\notin$ context-free language where $w^{R}$ denotes the reversed word $w$. (if $w$ = $w_{1}$$w_{2}$$w_{3}$ ... $w_{n}$ ,$w^{R}$ ...
user avatar
  • 1
0 votes
1 answer
337 views

Is $\{a^nb^mc^{n+m} \mid n, m \geqslant 0\}$ a context-free language (CFL)??

Considering this language $L = \{a^n b^m c^{n+m} \mid n, m \geqslant 0 \}$ is it a CFL? If I can make a PDA for it can I still prove with the pumping lemma that the language is not CFL? I mean if try ...
user avatar
  • 3
2 votes
1 answer
83 views

Check if the Language is context-free using the Pumping Lemma

$$ L=\{a^ib^jc^k \mid i, j, k \in N \text{ and } i <k<j\} $$ I want to check if this language is context-free. The part that confuses me is that if I choose $$ w=a^nb^{n+2}c^{n+1} $$ then one ...
user avatar
  • 167
0 votes
1 answer
58 views

Regularity of $w^{|w|}$

Is it true that for every regular language $L \subseteq \{0,1\}^*$, the language $\{ w^{|w|} \mid w \in L \}$ is also regular? It seems to me that it is not regular , so I will try to prove it with ...
user avatar
  • 63
1 vote
2 answers
126 views

Prove the following languages are irregular.

Prove the following language is irregular. $$ \{w^n \mid w \in \{0,1\}^*,\ n ≥ 2 \}$$ I'm trying to prove this with the Pumping Lemma, but I'm kind of confused because $w$ is a language not an ...
user avatar
  • 69
0 votes
1 answer
66 views

Can number of states of minimum accepting automaton be equal to a constan from the pumping lemma?

Let $L$ be a regular language. Prove that the number of states of the minimum accepting automata $L$ can be equal to a constant from the pumping lemma, but any smaller number can't. From what I ...
user avatar
0 votes
2 answers
752 views

Proof that the language $a^nb^ma^nb^m$ is not context free using the pumping lemma.

I need a proof that the language L = {$a^nb^ma^nb^m,\:n,m\geq0$} is context free using the pumping lemma. My problem is that I can actually show the conditions of the lemma hold for this language and ...
user avatar
0 votes
1 answer
27 views

Pumping Lemma to prove language not regular, formatting $x$

I need help with a question/verification I'm even thinking about it correctly. I'm trying to use the PL to prove $L$ is not regular. $L = \{\{a,b,c\}^* \mid |a| < |b| \wedge |a| < |c|\}$. This ...
user avatar
0 votes
0 answers
30 views

Why doesn't $|uv|\le k$ break the pumping lemma?

Let $N = \{ab^x | x \in\mathbb{N}\}$. Let the pumping length be $k$. So $ab^k$ belongs to $N$. Let $u = a, v = b^k, w = \operatorname{empty}$. Then $|uv|\le k$ does not hold. No other splitting I can ...
user avatar
  • 3
1 vote
1 answer
72 views

questions about the pumping lemma

Below is the Pumping lemma as stated in Automata and Computability by (Dexter C. Kozen) Let $A$ be a regular set. Then the following property holds of $A$: There exist $k≥0$ such that for any string $...
user avatar
  • 63
0 votes
1 answer
51 views

Pumping lemma definition!

I was studing Pumping lemma and I saw wondering and confusing definition,"Pumping length". Here is my problems: Question 1: Is pumping length = number of states in DFA? Question 2: If any ...
user avatar
2 votes
1 answer
142 views

Prove $\left\{u \# v | u,v \in \{0,1\}^{*} \text{ and } u \text{ is a substring of } v \right\}$ is not context free

I'm practising for my CS exam and got stuck on this problem $\left\{u \# v | u,v \in \{0,1\}^{*} \text{ and } u \text{ is a substring of } v \right\}$ So I've tried using following pumping lemma: ...
user avatar
1 vote
1 answer
486 views

Prove $\{0^k10^k10^k1 \in \{0,1\}^* \mid k \geq 0 \}$ is not context free

I'm practising for my CS exam and got stuck on this problem $$ \{0^k10^k10^k1 \in \{0,1\}^*\mid k ≥ 0\}. $$ I think I have good start however I don't know how to proceed. I assume the L is context ...
user avatar
1 vote
1 answer
72 views

Pumping Lemma works on language, but language is not regular

So i am given this language: L = { $c^ma^nb^n $ | $m≥ 1 $ and $n≥ 0$ } U { $a^mb^n$ | $m,n≥ 0$ } And i have to prove that the pumping lemma property works on L. Although pumping lemma can work, i then ...
user avatar
2 votes
2 answers
158 views

Irregularity of $a^ib^jc^k∣\text{ if }i=1\text{ then }j=k$ using pumping lemma

This question has been asked here several times. However none of the examples I saw actually tried to prove it's irregularity using the standard pumping lemma. I know how to prove irregularity using ...
user avatar
0 votes
1 answer
96 views

Prove that \{a^{3^n} is not regular \n>=1 using pumping lemma

I'm practicing for my CS exam and I got stuck on following language $L:= \{ a^{k} b u a^{k} | k \geq 1, u \in \Sigma^{*}\}$ $\Sigma = \{a,b\}$ I've tried to prove this language using a pumping lemma, ...
user avatar
2 votes
1 answer
145 views

Is the Pumping Lemma properly applied to prove $L = \{ 0^i1^{i+j}0^i \mid i, j > 0 \}$

The problem is to prove whether $L = \{0^i1^{i+j}0^i \mid i, j > 0\}$ is regular or not. I've used the Pumping Lemma with a string $s = 0^p1^{2p}0^p$, however I do not know I can choose such string ...
user avatar
  • 123
2 votes
2 answers
285 views

Pumping Lemma proof $L= \{a^nb^m2^{n*m} \mid m,n \ge 0 \} $ not regular

I'm trying to proof that the following language is not a regular language using the pumping lemma: $L= \{a^nb^m2^{n*m} \mid m,n \ge 0 \} $ I tried to build the string by assuming that m,n are the same ...
user avatar
0 votes
0 answers
29 views

Pumping lemma for context-free languages theorical question.

I have seen the demostration that $a^nb^nc^n$ is not a context-free languaje like a million times. My question is: If a languaje can produce a word of the form $a^nb^nc^n$ it is instantanley not ...
user avatar
1 vote
1 answer
118 views

Pumping lemma (context-free) of $L = \{a^nb^{\max\{n,m\}}a^m\ |\ n, m ≥ 0\}$

I want to show that $L = \{a^nb^{\max\{n,m\}}a^m\ |\ n, m ≥ 0\}$ is not context-free. I tried with things like take $w=a^pb^pa^p$ and got that $vwz$ is $a^qb^{p-q}$ but... I don't know, it doesn't ...
user avatar
0 votes
1 answer
61 views

Show these affirmations using the context-free pumping lemma properties

The question : Given $G$ a context-free grammar of Chomsky normal form with $k$ symbols. We know that the language $L(G)$ satisfy the pumping lemma for $ p = 2^k + 1$ I have those two questions to ...
user avatar
  • 335
1 vote
1 answer
134 views

Proving the language $\{w \in \{0, 1\}^{\ast} : w = w^{R}$, $|w|_{0} = |w|_{1} \}$ is not Context Free using Pumping Lemma

$\textit{Proof}$. Let $A$ be the language $\{w \in \{0, 1\}^{\ast} : w = w^{R}$, $|w|_{0} = |w|_{1} \}$. We will use the Pumping Lemma to prove that $A$ is not Context Free Language (CFL). The proof ...
user avatar
  • 59
1 vote
0 answers
1k views

Proving that the language $\{a^{i} b^{j} c^{k} : i < j < k\}$ is not Context Free using Pumping Lemma

$\textit{Proof}$. Let $A$ be the language $\{a^{i} b^{j} c^{k} : i < j < k\}$. We will use the Pumping Lemma to prove that $A$ is not Context Free Language (CFL). The proof is by contradiction. ...
user avatar
  • 59
1 vote
2 answers
416 views

Use the pumping lemma to show that the language is not context-free

I want to show that this language is not context-free: I struggle with the pumping lemma for CFL and i would like to know how to solve this problem. Thank you (skipping the classic introductory text ...
user avatar
  • 335
0 votes
0 answers
89 views

Pumping Lemma proof, need help with splitting xyz word, choosing pumping length and proving its not regular

I have the following language i want to prove is not regular by using the pumping lemma but not sure on what to use as the xyz and the pumping length. can i get a point in the right direction for how ...
user avatar
  • 11
0 votes
1 answer
231 views

pumping lemma division cases

If I got a language that I want to classify as "nonregular" using pumping lemma the problem that I'm facing with this algorithm is the following: when you divide the string S that you choose(...
user avatar
1 vote
0 answers
130 views

Pumping Lemma: context free squared number proof

I'm just doing a Pumping Lemma proof for showing a language is not Context Free by contradiction and would just like to know if it's valid. Note that for reasons, I'm only allowing $i = 0$ in the last ...
user avatar
0 votes
1 answer
336 views

Can the pumping length ever be equal to $0$ ? (Pumping lemma for regular languages)

I have seen some very conflicting information regarding the minimum pumping length. (part of the) Pumping lemma states : $\forall$ words $s\in L$ where $|s| > p$ Is it possible to use this ...
user avatar
  • 27
0 votes
0 answers
46 views

How can I use the pumping lemma for context-free language in a language with two alphabets?

$G =\{aba\mid a\in \{x,y,z\}{^+}\text{ and } b \in \{0,1\}\}$ I have watched many videos but I never saw an example of someone solving a pumping lemma in a language with two alphabets, can someone ...
user avatar