# Questions tagged [pumping-lemma]

The tag has no usage guidance.

213 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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)^{... • 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 ... 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 ... -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? 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. 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] 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 ... 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 ... 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=... -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{ ... • 203 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 ... -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, ... 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 ... • 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". 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 ... 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 ... • 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 ... • 11 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 ... • 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? 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 ... • 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 ... 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 ... • 393 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, ... • 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 |... 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 ... • 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 ... • 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 ... • 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 ... • 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 ... • 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 ... 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,... -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 ... 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 ... 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 ... 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} ... • 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 ... 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 ... • 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 ... • 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 ... • 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 ... • 43 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 ... 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 ... 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 ... • 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 ... • 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 ... 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: ... 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 ...
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 ...