Skip to main content

Questions tagged [pumping-lemma]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers
26 views

The pumping length for language $(0 \cup 1)^*$ is 1 . T/F

This is a true or false question. True/False: The pumping length for language $(0U1)*$ is 1. The answer is False, but I am quite confused. I thought the pumping length for this language would be 1 ...
Juntao Li's user avatar
-1 votes
1 answer
91 views

Does pumping lemma ever fail? [closed]

Consider the language F = {$a^i$$b^j$$c^k$ | i, j, k ≥ 0 and if i = 1 then j = k}. Show that F is not regular. Show that F acts like a regular language in the pumping lemma. In other words, give a ...
Ahmet Cicek's user avatar
0 votes
1 answer
63 views

Is the Language $L=\{(ab)^{3n}\:|\:n\in\mathbb N\}$ regular?

Is the language regular? My application of the pumping lemma suggests: splitting it in $xyz$: $$ x = \emptyset \mid y= (ab)^{j} \mid z=(ab)^{3n-j} $$ Pumping up $y$: $$ xyyz = (ab)^{3n+j} \mid (ab)^{...
Robert's user avatar
  • 21
1 vote
1 answer
307 views

Proving that a language whose strings have prime length is not context-free

Language is defined as: $L = \{a \space | \space a ∈ \{0,1\}^*\ ∧ \space len(a) \text{ is a prime number}\}$ How to prove that this language is not context-free? By far I was trying to prove it using ...
user avatar
0 votes
0 answers
62 views

$L=\{0^m1^n \mid3m\leq 2n\}$ via pumping lemma

Hi I’m trying to prove that L isn’t regular $L=\{0^m1^n \mid3m\leq2n\}.$ It’s from an exam of CS class, that’s my solution even if at some point I’m stuck. I assume that L is regular Let k > 0 ...
guglielmo's user avatar
-1 votes
1 answer
33 views

Prove a class of regular languages is not closed under a weird concatenation operation [closed]

Let's say we have an operation $L$ and a language $S$. $L(S) = \{s^n ~|~ s \in S, n \geq 0\}$. How can I prove a class of regular languages is not closed under this operation?
user1239142's user avatar
0 votes
0 answers
29 views

I want to prove the pumping lemma for context-free languages but instead of using Chomsky's form using a new form.

I will be grateful for your help. The new form is A-> V1.....Vt where t is between 2 and 5. can you give me a direction for the proof or a proof for this problem? thank you in advance.
Achiya Ben Natan's user avatar
2 votes
1 answer
47 views

Find the mistakes(pumping lemma proof). Can you help me?

There are pumping lemma proof. I have to find one mistake. Please help me [lemma proof][1]
adelorean's user avatar
0 votes
0 answers
82 views

Proof that $L =$ {$a^p : \text{p is prime} $} is not regular

I know that this question has already been answered but the proofs provided do not seem intuitive to me and I propose one using Wilson's theorem. Say $L$ is regular and its pumping length is $p \geq ...
PatelisGM's user avatar
1 vote
1 answer
3k views

Using pumping lemma show that language $L = \{a^{n^2} | n≥ 0\}$ is not regular.

Using pumping lemma show that language $L = \{a^{n^2} | n≥ 0\}$ is not regular. Is this approach correct? Let's assume that $L$ is regular so then the pumping lemma applies. Let $w = a^{n^2} ∈ L$. We ...
RandomGuyOnMath's user avatar
0 votes
0 answers
104 views

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

I was wondering if someone can help explain this question. I've been stuck on it for a while and having a hard time with it. Use the pumping lemma to show that following language is not context-free L=...
Storm Anderson's user avatar
-2 votes
1 answer
64 views

Determining whether a given language is regular

Suppose language $L = \{\,a^{i} b^{k} : k \text{ divides } i\,\}$. Some strings in $L$ include … $\,a^{0} b^{1} = b \in L\,$ since $1 \text{ divides } 0$ $\,a^{1} b^{1} = ab \in L\,$ since $1 \text{ ...
user3134725's user avatar
0 votes
0 answers
53 views

Proving Language is Non Regular With Pumping Lemma [duplicate]

I have the formal language $Z$ over the alphabet $Q \{a, b, c\}$ and it is generated by the context-free grammar whose non-terminals are $S, A$, and $B$, the start symbol is $S$, production rules are ...
Renee Ofadu's user avatar
-1 votes
2 answers
80 views

Proving Language is Non Regular Using Pumping Lemma

I am working on a question where I have the formal language Z over the alphabet Q {a, b, c} and it is generated by the context-free grammar whose non-terminals are S, A, and B, the start symbol is S, ...
Renee Ofadu's user avatar
0 votes
0 answers
65 views

prove $a^nb^{n^2+n}$ is not regular by intersection

I want to prove that this language is not regular $L = a^nb^{n^2+n}; n \geq 0$ It proved a bit challenging to prove it directly, and thus I am looking for the intersection way. I want a regular $L_1$ ...
Papa's user avatar
  • 483
0 votes
1 answer
77 views

Prove $01^m2^{m+j+2}1^j$ is not a regular language. [closed]

I am trying to prove that $01^m2^{m+j+2}1^j$ is not a regular language using the pumping lemma. I am having trouble splitting it into "xyz".
Ferret-2742's user avatar
1 vote
1 answer
86 views

Pumping lemma for 0^f1^g2^g?

I am trying to prove that the language $$\{0^g1^h2^j|h\ne j,g\ge2\}$$ is not regular. So far I have $x=0^m,y=0^f,z=0^{p-m-f}1^p2^{p+1}$. I don't know where to go from here, all of the examples I can ...
Ferret-2742's user avatar
5 votes
2 answers
470 views

What is wrong with my pumping lemma proof?

Here I am going to give a proof that L = {w | w is an element of {0,1}* and w has an even number of 1's} is not regular (even though it is regular) and I would like someone to point out what is wrong ...
James S's user avatar
  • 63
1 vote
0 answers
38 views

When I use the Pumping Lemma from Automata Theory, what are my restrictions for "i"?

The pumping lemma says: Let L be a regular language. Then there exists an integer p ≥ 1 such that every string w in L of length at least p can be written as s = xyz, satisfying the following ...
ManGoose's user avatar
0 votes
1 answer
125 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 ...
aurelia's user avatar
  • 133
0 votes
1 answer
92 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?
Tryer outer's user avatar
0 votes
1 answer
1k 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 ...
Math4Me's user avatar
  • 656
0 votes
0 answers
286 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 ...
EngineWare's user avatar
2 votes
3 answers
336 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 ...
CforLinux 's user avatar
0 votes
1 answer
173 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, ...
gator's user avatar
  • 1,835
1 vote
2 answers
863 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 $|...
Gabriel Kazama's user avatar
0 votes
1 answer
815 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 ...
Andre's user avatar
  • 111
0 votes
0 answers
230 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 ...
ili's user avatar
  • 145
1 vote
1 answer
57 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 ...
Pwaol's user avatar
  • 2,113
0 votes
0 answers
103 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 ...
liz's user avatar
  • 1
2 votes
1 answer
2k 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$ ...
Papa's user avatar
  • 483
0 votes
3 answers
82 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 ...
LegeOne's user avatar
0 votes
1 answer
40 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,...
Donald Jackman's user avatar
-1 votes
1 answer
4k 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 ...
supcem's user avatar
  • 9
0 votes
1 answer
115 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 ...
Teodor Dyakov's user avatar
1 vote
0 answers
74 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 ...
NoCodeNoBlunder's user avatar
0 votes
0 answers
156 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}$ ...
ASD's user avatar
  • 1
0 votes
1 answer
780 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 ...
mxmkrk's user avatar
  • 3
2 votes
1 answer
486 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 ...
kklaw's user avatar
  • 301
0 votes
1 answer
64 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 ...
Danilo's user avatar
  • 63
1 vote
2 answers
279 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 ...
hermi's user avatar
  • 69
0 votes
1 answer
102 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 ...
Nice guy's user avatar
0 votes
2 answers
2k 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 ...
Friendly Fella's user avatar
0 votes
1 answer
29 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 ...
pumping_until_swole's user avatar
0 votes
0 answers
35 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 ...
Bob's user avatar
  • 3
1 vote
1 answer
195 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 $...
JMF9's user avatar
  • 73
0 votes
1 answer
79 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 ...
Arian Ghasemi's user avatar
2 votes
1 answer
802 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: ...
gaming4 mining's user avatar
1 vote
1 answer
909 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 ...
gaming4 mining's user avatar
1 vote
1 answer
858 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 ...
Chris Costa's user avatar

1
2 3 4 5