Questions tagged [pumping-lemma]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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| \...