Questions tagged [pumping-lemma]
Necessary properties of formal langagues in certain classes that rely on closure against repetition of certain subwords. Make sure your question isn't covered by applying the techniques in https://cs.stackexchange.com/q/1031/755.
463
questions
-1
votes
1answer
50 views
Proving language is not context-free with pumping lemma
I'm trying to prove that this language is not context free using pumping lemma. I am having difficulty as to where to even start on this.
$$\{c^{2i} d^j b^{2j} d^k c^{3j} \mid i,j,k \ge 0\}$$
-1
votes
0answers
33 views
$Prove\; that\; L=a^i b^j c^k: i\le j\le k$ i s not context free language
Proof-:
Assume L is CFL.
Let p is pumping constant for L. w exists in L such that |w|$\ge p$
Let w=$a^p b^p c^p$ |w|$\ge$3p so everything is fine.
Now let us see all decompositions of w such that-:
vy$...
-1
votes
1answer
31 views
I can't visualize what happens when we pump v and y in pumping lemma for $a^n b^n c^n$
If you need some context-: https://www.andrew.cmu.edu/user/ko/pdfs/lecture-11.pdf around page 7.
Case 1-: Say vxy contains ab
So when I pump v and y, what will get pumped? And how the result would be. ...
0
votes
1answer
23 views
Understanding about pumping lemma for regular language-confusions of beginner-:
I want to understand how is this proof working.
What I know-:
Pumping lemma for regular language-:
Let $L$ be regular language. Then there exists a constant $n$ which depends on $L$ such that for ...
-3
votes
0answers
33 views
I need a pumping lemma for context free lenguages for this example? [duplicate]
Prove is that a context free lenguage or not
$L= $ { $0^k 1^l 0^k; k\geq l; (k,l) ∈ N ∪ 0$ }
0
votes
2answers
116 views
Can I solve pumping lemma for context free language proofs using examples?
Say I need to prove that
$L=${$a^n b^n c^n; n\geq 1$} is not context free language
I take n=3.
w=aaabbbccc
Here |w|=9.
we know by pumping lemma-:
|vxy| $\leq$n so vxy=abb
|vy| $\geq$1 so vy=ab
Hence I ...
0
votes
2answers
44 views
Check Proof Using Pumping Lemma to Show Language Not Regular
Please check my proof where I use the pumping lemma to show that the language $B=\{0^n1^n | n≥0\}$ is not regular.
I'll state the pumping lemma here for clarity:
Pumping lemma If $A$ is a regular ...
1
vote
1answer
41 views
Dividing a String According to the Pumping Lemma
I have some questions about how a string can be divided into pieces according to the pumping lemma. I am learning from Michael Sipser’s book Introduction to the Theory of Computation, 3rd Edition. He ...
2
votes
0answers
32 views
Summary of Pumping Lemma Application
For my own understanding I would like to summarize how to use the pumping lemma to show that a language is not regular. The pumping lemma is defined as follows.
Pumping lemma If $A$ is a regular ...
1
vote
2answers
39 views
What is the minimum pumping lemma length of $01^*0^*1$?
I've taken the following steps to prove that the minimum pumping length (PL) of the above language, $L= 01^*0^*1$:
Set a PL. I chose $p=2$
Choose a string from $L$ where $|w|\geq p$, I chose $w=011$. ...
0
votes
2answers
63 views
Show that $\{xy : x \in \{a\}^*, y \in \{b\}^*, |x| = |y|\}$ is a not a regular language
I have been asked as an exercise how to prove that this is not a regular language. first I tried to use the pumping lemma, but I got stucked. Th erxercise hust said to prove thata this isn't a regular ...
0
votes
1answer
48 views
How to use pumping lemma on languages that do not follow a strict structure?
Let me preface this by saying, I do NOT want an example of a proof, I would merely like pointers as to how I could approach this problem.
For example, I have a language:
$$L = \{w \mid w \in \{0, 1\}^*...
2
votes
1answer
56 views
Implication of the Pumping lemma
I'm reading Hopcroft and Ullman's '79 edition of "Introduction to Automata theory, Languages, and Computation". In chapter 3, the authors say "The lemma[sic] does not state that every ...
0
votes
0answers
63 views
Proving that $\{ a^i b^j c^{\max(i,j)} \}$ is not context-free
Prove that $L$ is not a Context-free language, where
$$L = \{ a^{i} b^{j}c^{h}\mid i,j,h\in \mathbb{N} \wedge h = \max(i,j)\}.$$
I have an idea: It can be divided into two situations:
When $i < j$...
-1
votes
1answer
34 views
How to prove that $L = \{w\in\{a,b\}^*\mid w = uav \text{ and } |u| = |v|\}$ is not a regular language
$L = \{w\in\{a,b\}^*\mid w = uav \text{ and } |u| = |v|\}$
I know to use the pump lemma, but I don’t know how to use it correctly.
0
votes
0answers
15 views
Check if a language is context free [duplicate]
Check whether the following language is context-free. If yes, a suitable grammar should be given; if no, the pumping lemma should be used as a tool.
$$L=\{a^ib^jc^k \mid i, j, k \in N \text{ and } i &...
0
votes
1answer
74 views
Proof that $\{a^ib^jc^k\mid i,j,k\in\mathbb{N}, i<k<j\}$ is not context-free using the Pumping Lemma
$$
L=\{a^ib^jc^k \;| \;i, j, k \in \mathbb{N} \; \text{and} \; i <k<j\}
$$
I need to show that this language is not context-free with the help of the Pumping Lemma.
My first intuition is, that ...
0
votes
1answer
46 views
Use the CFL pumping lemma to show that this language(0^p where p is prime) is not context free
L = {0^p
|p is a prime}. So was looking at the explanation at the bottom of page 5 of the following website: https://www.ics.uci.edu/~goodrich/teach/cs162/hw/HW5Sols.pdf
I want to make sure that I ...
-1
votes
1answer
35 views
How to choose word for pumping lemma for $a^kb^{2k}a^k$?
I have to show that the language $ \mathcal {L} = \{a ^ k b ^ {2k} a ^ k: k \geq 0 \} $ is not a regular language. So that's what I want to use the pumping motto for. What I could do is this: let $ \ ...
0
votes
1answer
43 views
Pumping Lemma for $\mathcal{L} = \{ \omega \omega^R a^{|\omega|} : \omega \in \{a,b\}^* \} $
I have to show that this language is not context free $\mathcal{L} = \{ \omega \omega^R a^{|\omega|} : \omega \in \{a,b\}^* \} $, where the $R$ corresponds to the reverse. For this I will use the ...
0
votes
1answer
20 views
Show that a language with union is not regular by using pumping lemma
Given the language $L:= { \{ c^{2k} w \ \vert \ k \ge 1, \ w \in \{a,b,c\}^* \ and \ \vert w\vert_a \ = \ \vert w\vert_b \} \ \cup \ \{ a,b \}^* }$
I'm really unsure how to even start because of the ...
0
votes
1answer
49 views
Minimum pumping length of finite language
Background
Let L = {aa}. We know that the minimum pumping length of L is |aa| + 1 = 3. For this length all the three conditions of the pumping lemma vacuously hold true.
Doubt
Let L = {aa, aab}. Is it ...
0
votes
0answers
32 views
Prove $L =\{0^{2^n}\mid n \geqslant 0\}$ is not context free [duplicate]
Here $0^j$ means $0$ repeated $j$ times e.g. $0^2$ is $00$. So to prove this I was asked to use the pumping lemma.
So let $m$ be the pumping length and assume $L$ is a CFL by contradiction. We can ...
5
votes
1answer
81 views
Can a non-regular language $L$ have a non regular $L^*$?
I have been looking around and i cant seem to find an example of such case that a non-regular $L$ has a non regular $L^*$. Is it possible? If so, can you provide an example of such case please?
2
votes
2answers
65 views
Prove $\{xy \mid |x|=|y|, x \neq y\}$ is not a linear language
Show the language
$$L = \{xy \mid |x| = |y|, x\neq y\}$$
is not linear.
I've seen and proved a pumping lemma for linear languages, mentioned here:
If $L$ is linear then there exists a constant $p$ ...
1
vote
1answer
55 views
Proving $\{ a^n b^m \mid n \leq m^2 \}$ is not context-free using pumping lemma
I am working on a pumping lemma question and trying to prove that the following is not context-free, but I can't finish the proof.
The language is
$$L = \{ a^n b^m \mid n \leq m^2 \}$$
Assume Demon ...
0
votes
0answers
48 views
Prove with pumping lemma that the language { $a^n b^n b^m a^m | n ≠ m $ } is not context free
I'm having a trouble proving it to be non-context-free.
For example, if I take w = $a^k b^k b^{k+1} a^{k+1}$, it would be problematic if the partition of $vxy$ with $|v| = |y|$ was in the $ b^{k+1} a^{...
2
votes
4answers
251 views
Proving that $L=\{ w \mid \lvert w \rvert$ is prime $\}$* is a regular language
I'm trying to prove that the following languague is a regular language:
$L=\{ w \mid \lvert w \rvert$ is prime $\}$*
What I have thought is to divide each word $w \in L$ into subwords of length 2 if ...
1
vote
1answer
30 views
Using pumping lemma to prove that $L = \{ a^ib^j \mid \lvert i - j \rvert \le 2 \} $ is irregular
Given the following language:
$L = \{ a^ib^j \mid \lvert i - j \rvert \le 2 \} $
I am trying to prove that it is not regular. On the one hand my intuition tells me that the language is non-regular as ...
1
vote
2answers
27 views
Proving Irregularity of $L = \{ a^mb^nb^n \mid nm \ge 3 \} $
I'm trying to prove the irregularity of the following language:
$$L = \{ a^mb^nb^n \mid nm \ge 3 \} $$
I tried to demonstrate that it doesn't verifies the Pumping Lemma but for all words I tried it ...
3
votes
1answer
79 views
Existence of a CFL $L$ such that $\sqrt{L}$ is not CFL
Does there exist a CFL L such that the language defined as $L' = \sqrt{L} = \{w | ww \in L\}$ is not CFL? I feel that there is no such $L$ but obviously, I am unable to prove it.
I am sorry but I have ...
0
votes
1answer
54 views
Is the language $\{a^n b^m : 1000|nm \}$ regular?
We have a language $$ L = \{a^n b^m \mid 1000|nm \} $$
Is this language regular?
I'm trying to disprove this using the Pumping Lemma, but it didn't work.
assume I say $x=a^{h}$ and $y=a^{t}$ and $z =...
0
votes
1answer
52 views
Is the language $\{a^n b^m \mid 2n + 3m \le 1000 \}$ regular?
We have a language $$ L = \{a^n b^m \mid 2n + 3m \le 1000 \} $$
Is this language regular?
I'm trying to disprove this using the Pumping Lemma, but it didn't work.
assume I say x = $x=a^{h}$ and $y=a^{...
1
vote
2answers
102 views
Proving that the language $\{ w^n\mid w \in \{0,1\}^∗, \, n \ge 2 \}$ is not regular
I'm trying to prove that the following language is not regular:
$$\{ w^n\mid w \in \{0,1\}^∗, \, n \ge 2 \}$$
I'm trying to prove this with the pumping lemma, but I'm kind of confused because $w$ is ...
3
votes
2answers
418 views
Irregularity of $\{ w_1 aa w_2 \mid |w_1| \neq |w_2| \}$
I'm currently struggling to come up with a proof that the following language is irregular:
$$L_2 := \{w_1aaw_2 \in \Sigma^* \mid w_1, w_2\in\Sigma^* \land |w_1| \ne |w_2|\}$$
where $\Sigma = \{a, b\}$....
1
vote
1answer
22 views
Pumping lemma for an involved non context free language
Hi I'm trying to show $C=\{wzzw^R|w,z\in\{0,1\}^+\}$ is not a context-free language.( I have this believe because $C=\{ww|w\in\{0,1\}^+\}$ is not a context free language.) I'm really struggling to ...
1
vote
1answer
106 views
Proving a language with $(ab)^n$ is not regular with pumping lemma?
I have been working to understand the pumping lemma better, but I am quite stuck at proving these two languages is not regular:
\begin{align}
L_1 &= \{(ab)^n c^m \mid n\ge 1, m\ge 2n \} \\
L_2 &...
1
vote
2answers
60 views
Is $\{a^mb^nc^n \mid m,n \geq 0\} \cup \{b,c\}^*$ regular or not?
Show if $L = \{a^mb^nc^n \mid m,n \geq 0\} \cup \{b,c\}^*$ is regular or not.
My attempt:
I think the Pumping lemma won't work in that constellation, so I'm working with "The intersection of ...
0
votes
1answer
64 views
How do I apply the Pumping Lemma to prove that this language is not regular?
I am trying to teach myself Automata theory. I have hard time with the Pumping Lemma, so I am trying to work through examples. I stumbled upon this example, but it doesn't have steps how to solve it.
...
1
vote
2answers
86 views
Pumping lemma for regular languages. Proof
Please help me understand the following
$L = \{ a | a ∈ \{0, 1\}^∗, |a| = k ≥ 4, a = a_1a_2...a_{k−1}a_k, ∃i ∈ N, 1 ≤ i < k : a_i = a_{i+1} \}$
To prove: The language $L$ has regular pumping ...
0
votes
1answer
84 views
Pumping Lemma Proof (Type of wcw language)
I have the language $L = \{ dkd\space \mid d \in \{a,b\}^*, k \in \{a,b\} \}$ and i have to show that it's non-regular using the pumping lemma.
The structure of the language i think can be explained ...
0
votes
2answers
135 views
Cardinality of sets and strings -> confused
I have a question regarding the cardinality of sets and strings.
If $ \Sigma^* $ is empty, the cardinality is 1, because the empty word $ \varepsilon $ is counted.
If $ \Sigma^+ $ is empty, the ...
1
vote
2answers
373 views
What is wrong with this proof that proves that 0*1* is not a regular language?
I know why cases 1 and 2 are wrong because our language can have different numbers of 0's and 1's. But I'm not sure how case 3 can be proved wrong for our language.
Exercise 1.30:
Describe the error ...
1
vote
1answer
71 views
Proving that $ \{u\#v\#w \mid u,v,w \in {a,b,c}*, |u|_a = |v|_b = |w|_c\}$ isn't context-free
I have a question about the pumping lemma for context-free languages.
I understand the conditions of the pumping lemma.
Assume $L$ is context-free. Let $n>0$ be the pumping length given by the ...
1
vote
1answer
73 views
Why does the Pumping Lemma Constraint |xy| ≤ p mean that y can't be 1 in the string 0p1p
I am trying to get my head around the Pumping Lemma to prove a language is non-regular.
I am reading the Sipser text book and he gives the following example.
Let B be the language $\{0^n 1^n | n \ge 0\...
1
vote
1answer
64 views
How to prove a language isn't necessarily regular? [duplicate]
Assuming we have a regular language $L$, how can we prove that $L'= \{ xz \mid \exists y : xyz \in L \text{ and } |x|=|y|=|z|\}$ isn't necessarily regular.
So far I can't come up with much for how to ...
3
votes
0answers
34 views
Subexponential size of string to prove $\{xy : x,y \in \{0,1\}^\star, |x| = |y|, x \ne y\}$ is not regular?
In the standard proof of this language not being regular using the Pumping Lemma for Regular languages, one picks $0^p 1^p 0^{p+p!} 1^p$ where $p$ is the pumping constant and using that can derive the ...
2
votes
2answers
99 views
Is $L:=\{a^k \mid k \text{ is prime}\}$ regular?
For this exercise the pumping lemma should be used. My instructor gave me a tip it should start with $w:= a^{prime(n)}$ where prime is a while program returning the nth prime number. This does make ...
1
vote
3answers
326 views
Pumping lemma: why x in ∣xy∣ ≤ p?
Looking at the pumping lemma, I've noticed that in the string $xy^pz$, there seems to be no rule explicitly stated for $x$ and $z$. If I understand correctly, $x$ and $z$ are basically anything on the ...
1
vote
1answer
75 views
Is there a human-friendly version of the Pumping-Lemma?
I found this on Wikipedia and I'm confused by the parenthesis in the notation not that it doesn't make sense to me but is there a more natural human version? And im generally confused about all the ...