Questions tagged [pumping-lemma]
The pumping-lemma tag has no usage guidance.
168
questions
0
votes
1answer
33 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 ...
1
vote
1answer
23 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
1answer
43 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 ...
1
vote
1answer
37 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 ...
2
votes
2answers
40 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 ...
0
votes
1answer
36 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, ...
2
votes
1answer
28 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 ...
2
votes
2answers
46 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 ...
0
votes
0answers
23 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 ...
1
vote
1answer
28 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 ...
0
votes
1answer
51 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 ...
1
vote
1answer
42 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 ...
1
vote
0answers
30 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.
...
1
vote
2answers
58 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 ...
0
votes
0answers
19 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 ...
0
votes
1answer
25 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(...
0
votes
0answers
33 views
Prove, by application of Pumping Lemma, that the language $L = \{ a^nb^{2^n} \}$ is not context free
I am preparing for the exam and have this question:
Prove that the language $$ L = \{ a^nb^{2^n} | n >= 0 \}$$ is not context free.
I want to prove it with case distinction, but can't seem to work ...
1
vote
0answers
36 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 ...
0
votes
1answer
60 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 ...
0
votes
0answers
26 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 ...
0
votes
0answers
20 views
pumping lemma for context free languages
As part of the homework we were asked a question about context free languages, and the proof is done using the pumping lemma for CFL. (Prove that it is not a CFL, proof by negation.)
The question is ...
0
votes
2answers
139 views
Pumping Lemma for CF language exercise
I have this language
$$ B=\{x\in \{a,b,c\}^*:(x\text{ not contains } aabb \text{ or } bbcc \text{ or } aaaa) \land \#(a,x)=\#(b,x)=\#(c,x)\} $$
The notation $ \#(s,x) $ indicates the number of ...
1
vote
2answers
70 views
What does w ∈ a, b* mean?
What does $w ∈ a, b^*$ mean?
The context is the language of an automation, which is $L=\{w∈ a, b^*|:|w|$ is even and the central symbols of $w$ are $aa\}$
I really don't understand what $w ∈ a, b^*$ ...
-1
votes
1answer
57 views
Formally proving that $\{ L = { {a^i}{b^j}{c^k}, j = \min(i,k), i, k > 0\} } $ is context-free
Please no hints.
I need to formally prove that $\{ L = { {a^i}{b^j}{c^k}\mid j = \min(i,k),\: i, k > 0\} } $:
At first my idea was to use pumping lemma, so I tried to study where $\\|vwx|\ $falls ...
1
vote
1answer
41 views
Using the pumping lemma to deduce that the language consisting of palindromes is not regular [duplicate]
Given an alphabet $\Sigma$ (of size at least $2$) let $L$ be the language consisting of words of the form $a^kb^k$ with $k\in \mathbb{N}$ and $a,b\in \Sigma$.
Then for any $p\in \mathbb{N}$ pick $a\...
0
votes
1answer
43 views
How to use the pumping lemma to prove that $a^{m}b^{n}a^{m}c^n$ is not context free?
How to use the pumping lemma to prove that $ Y = a^{m}b^{n}a^{m}c^n$ is not context free? Note that $m,n \ge 0$.
I tried by finding the case where it would be impossible for a word $w$ to be in $Y$. ...
0
votes
1answer
170 views
How to prove that the language L={w1#w2#. . .#wk: k ≥ 2, each wi ∈ {0,1}^* , and wi = wj for some i !=j} is not context free using the pumping lemma?
I am having trouble choosing the string to use for the proof. I know that I have to choose a string such that at least two substrings separated by the # are equal to each other but am unsure of how to ...
0
votes
1answer
44 views
Proof for pumping lemma for new kind of CFL
I have a context-free grammar $(V,\Sigma,R,S)$ that is defined by the condition that every production in $R$ has to be on one of the following two forms:
$A\to uBv$ where $A,B\in V$ and $u,v\in\Sigma^...
-1
votes
1answer
42 views
How to prove that a language is non-regular by using Pumping lemma with length?
I was given the following question:
Use the Pumping Lemma with length to prove that the following language is non-regular:
$L = \{b^na^{100}b^{2n}, \text{where n} = 1, 2, 3,...\}$
Use the ...
0
votes
1answer
65 views
Prove language of $0^n1^m$ is irregular for coprime $n,m$. [duplicate]
I need to prove that the language of $0^n1^m$ is irregular if $n$ and $m$ are coprime. (Or to disprove that)
My attempt at this was to use the pumping lemma, and I've gotten $0^{n+(k-1)i}1^m$ after ...
1
vote
1answer
189 views
pumping lemma - union of regular languages
In the question, we have regular languages L1, L2 with the constant of the pumping lemma - n1,n2.
Also, we have the language L = L1 + L2 with the constant n of the pumping lemma.
I need to prove that ...
2
votes
1answer
34 views
Which part of the string $00011112222$ can be pumped?
Let us observe the language $\newcommand{\lang}{\mathcal L} \lang = \newcommand{\set}[1]{\left\{ #1 \right\}}\set{ 0^i 1^n 2^n \mid i \geq 1, n \in \mathbb{N}}$. Can any of the substrings indicated ...
0
votes
1answer
151 views
Why is the minimal pumping length for $(01)^*$ equal to 1?
I see why the minimum pumping length is at most 2 (since 01 can be pumped). But why is this counterexample not valid?
Let $A=(01)^*$ and assume it has pumping lenght $p=1$. Then lets consider the ...
0
votes
1answer
33 views
How to prove that a language is not regular without the use of the Pumping Lemma?
I have an exercise to prove.
Prove that $\{a ^ i b ^ j c ^ k \mid i, j, k \geqslant 0, \text{if $i = 1$ then $j = k$}\}$ is not a regular language but that respects the conditions of the Pumping ...
0
votes
0answers
64 views
What is the difference between pumping Lemma for regualar languages and pumping lemma for context free languages?
Is there a difference between the pumping lemma for regular languages and the context-free languages?
I know that pumping lemma for context-free languages is a generalization of pumping lemma for ...
0
votes
1answer
288 views
How to prove that an even palindrome is not regular using pumping lemma?
As a follow up to this question
Given an alphabet $\{a, b\}$.
Why are palindromes not regular? Could you not select $x=z=(a|b)$ and $y=$ the remaining characters in the word.
For example given $...
1
vote
1answer
34 views
pumping lemma $a^{n} (b a^{n-1})n$ times where $n$ decrements each time
Hi I am stuck trying to prove that the following language
$K = \{a, a^2ba, a^3ba^2ba,...\}$ is not a regular language.
Actually I simply can't find a word w that has a length of at least p and is in ...
0
votes
1answer
38 views
Show that the language $L$ is not regular
I want to show that the below language is not regular:
$$L=\{\text{words that contain exactly } k \text{"a" }, m \text{"b" and } n \text{"c" , where }k,m,n\geq 1 \text{ and } m=k\cdot n\}$$
For ...
-1
votes
2answers
930 views
Proving that $L = \left\{a^{n^2} | n \ge 0\right\}$ is not context free with Pumping Lemma for CFG?
$$L = \left\{\left. a^{n^2} \right| n \ge 0\right\}$$
I don't quite understand this problem.
3
votes
1answer
58 views
Using Pumping Lemma for Context Free Languages
Pumming Lemma Question -Not Context Free
I understand the general concept of pumping lemma but I don't quite understand how to write proofs formally. In this particular case (see image attached),I ...
1
vote
1answer
33 views
Show, that $L$ is not regular but satisfies the pumping-property.
Show, that $L_{1}:=L\left((a \cup b)^{*} \cdot(a a \cup b b) \cdot(a \cup b)^{*}\right) \cup\left\{w \in\{a, b\}^{*}\mid \lvert w \rvert \text { is prime number}\right\}$ is not regular but satisfies ...
1
vote
0answers
32 views
Context-free languages are not closed under SWAP$(L) = \{ yxz \mid x, y, z \in \Sigma^{*} $ and $ xyz \in L \}$
Currently I am preparing myself for an exam. I was able to show that some languages are closed under certain stuctures. But I'm stucked at the topic, where I have to show that languages are not closed ...
1
vote
1answer
17 views
Prove, that $L:=\{w\cdot d\cdot \overleftarrow{w}\mid w\in \{a,b\}^+\}$ is not regular using the pumping-lemma
Let $\Sigma =\{a,b,d\}$. Prove, that $L:=\{w\cdot d\cdot \overleftarrow{w}\mid w\in \{a,b\}^+\}$ is not regular over $\Sigma$.
Definition: $\overleftarrow{w}$ is defined inductively:$\overleftarrow{\...
0
votes
1answer
51 views
Pumping Lemma - Grammar - Regular language
I'm having a bit of trouble understanding this exercise:
Indicate whether the following grammar describes a regular language. Prove your answer.
G4: $S \to aS|aSbS|ε$
My answer is using this ...
5
votes
1answer
60 views
How can I prove that this language is not context free?
The language is $A = \{a^{n}b^{n}a^{m} : n \geq 0, m \geq 0, n \neq m\}$.
I tried to use the pumping lemma. I chose the string s = $a^p b^pa^{p + p!}$ that is split in $uvxyz$ and must respect
$|...
1
vote
2answers
61 views
The correctness of a statement related to the Pumping Lemma and regular language
I was studying Automata theory and came across the Pumping Lemma, which I understand as:
Let $\mathcal{A}=\langle\Sigma, Q, q_0, F, \delta\rangle$ be an NFA. Suppose $x \in L(\mathcal{A})$ s.t. $|x| \...
0
votes
1answer
24 views
Showing language is irregular with pumping lemma
We define the language $L = \{cw_1cw_2c| w_1,w_2 \in \{a,b\}^*, \text{num of a's in }w_1 = 2|w_2|\}$
We are asked to show this language is irregular using pumping lemma.
I know we gotta look at the ...
2
votes
2answers
563 views
Using Pumping Lemma prove that the language $L = \{a^ib^j \mid i,j \in N \}$ is Not Regular.
Using Pumping Lemma prove that the language $L = \{a^ib^j \mid i,j \in N \}$ is Not Regular.
Proof:
Assume that $L$ is Regular.
Pumping Length = $P$.
We choose $w = a^{P-2}b^{P+2} \in L$
We divide ...
2
votes
1answer
41 views
Proving with the pumping lemma that the following language is not regular
I want to prove that
$A$ = {ww: w $\in \sum^{*}$}
is not regular. This is what I have done so far:
Suppose A is regular. Let $p$ be the constant that must exist if $A$ is regular. Then, we can ...
0
votes
0answers
39 views
$L = \{ 0^p | \, p \,\text{ is prime} \}$ is not regular [duplicate]
We assume the regularity of $L$ for the sake of contradiction.
Pumping Lemma: $ \exists n \in \mathbb{N}$ for which $ \forall z \in L$ with $|z| \geq n$, $\exists u,v,w$ with $|uv| \leq n$, $|v|
\...
