What's the deal with Deno? We talk with a major contributor to find out. Listen now.

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.

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

How to show $L = \{0^{i}1^{i^{2}}| i \ge 0\}$ is not context-free using pumping lemma

I've been struggling with this problem for quite a while now and don't really understand what to do for the pumping lemma here. We have the language $L = \{0^{i}1^{i^{2}}| i \ge 0\}$ and we need to ...
0
votes
1answer
27 views

If one of the case obeys all rules of Pumping Lemma, can we conclude there is no contradiction?

I am studying Pumping Lemma for Context Free Languages, wherein, I am slightly confused in a question where one of the case doesnt obey all rules but another case does. What's the conclusion? Do we ...
0
votes
2answers
81 views

How to understand and apply pumping lemma to prove $a^{i+1} b^{4i+2}$ is not regular?

I am having trouble understanding how to apply Pumping Lemma to show a Language is not regular. If the alphabet is $\Sigma = \{a, b\}$ and the language is $L = \{a^{i + 1} b^{4i + 2} \mid i \in \...
1
vote
1answer
56 views

Correct application of the CFL Pumping Lemma

I came across this question about showing that the language $L = \{w \epsilon \{a, b, c\}^*: n_a(w) + n_b(w) = n_c(w)\}$ is context-free but not linear in the book by Peter Linz. That is easily doable ...
0
votes
1answer
25 views

Use of pumping lemma for not regular languages. (Proof Verification)

$L=\{w \in \{0,1,a\}^* | \#_0(w) = \#_1(w) \}$ We show that L is not regular by pumping lemma. We choose w=$0^p 1^p a$ |w| = 2p+1 Now |xy| has to be $\leq p$ So x and y could only contain zeros. And $...
0
votes
1answer
37 views

Why is this language *not* pumpable? (language = arbitrary word followed by exact same arbitrary word)(pumping lemma for context-free-languages)

language = arbitrary word followed by exact same arbitrary word = u * u (with u being out of non-empty words of alphabet {0, 1} ) (sorry for the formatting, see screenshot-link for conventional/clear ...
0
votes
1answer
47 views

How do I use the pumping lemma for a^n b^m a^(n+m) ? How can I choose the pumping length?

$L = {a^n + b^m + a^{n+m}}$ This is the language I want to show is not regular. Now my problem is to choose p correctly. Can I just set it as p=2*(n+m) ? That's the problem I am facing now. Thanks for ...
0
votes
0answers
25 views

Why is there no contradiction when using pumping lemma on a^N b^N a^2N, when k=2?

I have question where it asks: Using the pumping lemma on a^N b^N a^2N, why can you not reach a contradiction when k=2? Here's what I've done, but I do reach a contradiction... u=a^r v=a^s x=a^t b^N a^...
1
vote
1answer
26 views

Prove that the language is not regular through Myhill-Nerode Equivalence

The language is given by: $$L=\{a^nb^m|n<m\}$$ I have proven that the language is not regular using the pumping lemma but I need help with proving it through Myhill-Nerode Equivalence. Any help ...
0
votes
2answers
63 views

Proof that $L=\{a^ncb^n| n \in \mathbb{N}\}$ is not regular

Prove that $L=\{a^ncb^n| n \in \mathbb{N}\}$ is not regular. Here is my try, I would really appreciate if someone could tell me if this is a correct proof. Proof: Lets assume L is regular. Then we ...
1
vote
2answers
61 views

Does a regular expression exist for any number that contains no more than two 5s and no 6 twice in a row?

For example, a valid number would be 6165156 and an invalid number would be 1566515. I have tried many times to construct a finite state machine for this with no success, which leads me to believe the ...
2
votes
1answer
42 views

Pumping Lemma,regular languages

Lets say that we have the language L = { $a^n$$b^m$$c^{m+n}$ $|$ $m$,$n$ $>=0$ } What is the way that i should follow to prove that the language is not regular? Assume that the language is ...
0
votes
1answer
32 views

validation of a pumping lemma proof for regular languages

I have the following regular expression: Of course I could think of a word like $w=a^{m+2}b^{m+2}c^{2m+3}$ and continue with the proof BUT I was just wondering, because $L$ is made up of a union of ...
0
votes
1answer
32 views

Prove $\{a^ib^i\mid i\ge0\}$ is not regular using the pumping lemma

I do not understand the last sentence of the proof provided. It says that the fact that xz does not belong to L contradicts the hypothesis, but isn't it that xyz not belonging to L what we are trying ...
1
vote
1answer
43 views

Pumping Lemma for CFL - $ \{ 0^{i} 1^{j} 0^{k} 1^{l} \hspace{0.2cm}| \hspace{0.2cm} i = l \hspace{0.2cm} \land j = k \} $

I was making exercices about the Pumping Lemma for CFL, and I stumbled up on this language: $$ \{ 0^{i} 1^{j} 0^{k} 1^{l} \hspace{0.2cm}| \hspace{0.2cm} i = l \hspace{0.2cm} \land j = k \} $$ I ...
0
votes
1answer
26 views

What is Pumping length for Union of Regular languages?

This is an exam question. For E = {a,b}. let us consider the regular language $L= \{x|x = a^{2+3k} or x=b^{10+12k}, k >= 0\}$ Which one of the following can be a pumping length (the constant ...
0
votes
1answer
87 views

Minimum pumping length of (01)* [duplicate]

Michael Sipser offers the definition: The pumping lemma says that every regular language has a pumping length p, such that every string in the language can be pumped if it has length p or more. If p ...
0
votes
1answer
30 views

Pumping lemma for regular languages vs. Pumping lemma for context-free languages

How can I prove the next claim: If a language $L$ meets the pumping lemma for regular languages then $L$ meets the pumping lemma for context-free languages? (Without any pre-condition about the ...
0
votes
1answer
53 views

Is this language with prefix regular?

Is this language regular? ${w ∈ (a + b)∗ : |u_{a}|>= 2009 · |u_{b}|}$ for every non empty prefix $u$ of string $w$} I think it's non-regular. I tried concatenation of $L_{prefix} $={${ u : |u_{a}|&...
1
vote
2answers
42 views

Regular of language of all words of length 3

Consider the language $$L = \{ x \in \{0,1\}^* \mid |x| = 3 \}.$$ I think the above language is regular. A DFA can be used to determine the above language. Am I correct? Is the above language regular?...
2
votes
1answer
33 views

Language of lists of words, not all of which are different, is not context-free

How do I prove that the following language isn't context-free using the pumping lemma? $$ L=\{w_1\#w_2\#\dots\#w_k \colon k ≥ 2, w_i \in \{0,1\}^*, w_i = w_j \text{ for some } i \ne j\} $$ I am having ...
1
vote
1answer
42 views

necessary and sufficient pumping lemma - bounded pumping variant

There exists a variation of the pumping lemma with necessary and sufficient conditions for a language to be Regular. According to that lemma: A language $L$ is regular iff $\exists k$, $\forall x\in ...
3
votes
1answer
41 views

Minimum pumping length of concatenation of two languages

there's this small part of my homework that I just can't figure out. Let us denote $p(L)$ as the minimum pumping length of some language $L$. I'm supposed to find two regular languages $A,B$ so that ...
0
votes
2answers
26 views

Is the language of rectangular matrices in MATLAB-style syntax context free?

Consider the language $L$ of rectangular matrices written down as a comma separated list of integers where each list represents a row of the matrix and rows are separated by a semicolon. There may be ...
0
votes
1answer
22 views

When proving a set is not regular is it enough to prove a subset of it regular?

E.g. when proving L = {w in {a,b}^*: the first, the middle, and the last characters of w are identical}, can i just prove ab^pab^pa is not regular? Where p is the pumping length?
0
votes
1answer
15 views

Can we specify the pumping length while applying pumping lemma

In all the examples I have seen, the pumping length $p$ is not specified. The string is a pattern that somehow has the $p$. E.g. when proving $L=\{a^n b^n c^n | n \geq 0\}$ is not context free, we ...
1
vote
3answers
306 views

$a^*b^*c^* \setminus \{a^n b^n c^n | n ≥ 0\}$ is not regular using pumping lemma?

$L=a^*b^*c^* \setminus \{a^n b^n c^n \mid n \geq 0\}$ can be proved as context-free by partitioning it as $L = \{a^nb^mc^* \mid n \neq m\} \cup \{a^*b^nc^m \mid n \neq m\}$ and further dividing each $\...
1
vote
1answer
75 views

How to prove language $L=\{a^{i}b^{j} : i \leq j^{2}\}$ is not CFL using Pumping lemma?

I'm trying to found a way how to prove this language is not context free. Using pumping lemma I'm halfway done. Consider word $a^{n^2}b^n$. If you divide it into $uvwxy$ and have only $a$'s in $v$ and ...
1
vote
0answers
24 views

$L = \{\alpha^i \beta^j \gamma^k \vert i,j,k \in \mathbb{N}_0, (i=1) \Rightarrow (j=k)\}$

I am asking this question here, because I am not allowed to comment on the thread that I am actually interested in, but maybe someone can still help me? I alredy found an anwser to the Problem above (...
1
vote
2answers
45 views

How to show that Language is not Context Free?

There is a question to show that $L=\{a^{n!} \mid n \geq 0 \}$ is not regular using Pumping Lemma. However, I have the answer in the book which is found to be somewhere wrong. I am sharing the ...
0
votes
1answer
26 views

Language of words whose run lengths are all distinct

Assume $ \Sigma=\{0,1\}$, is $L$ a regular language? If it is not, how should we prove it with pumping lemma? $$L = \{1^{a_1} 0^{a_2}\ldots 01^{a_k} \mid k \in \mathbb N , a_i \geq 0 , \text{ the $...
2
votes
2answers
38 views

Proving non-regular language using the pumping lemma

I would like to verify that the following language is not regular. I know that if the pumping lemma is not valid then the language is not regular. (but its not enough to prove that the language is in ...
2
votes
3answers
117 views

An approach to determine whether language is regular or not?

I have the following problem. I need to determine whether this language is regular or not: $L:= \{ w \in \Sigma^*: \forall \alpha ∈ \Sigma, |w|_\alpha \text{ is even or divisible by 3}\}$ $|w|_\...
-2
votes
2answers
205 views

Is the set of strings with equal number of 010’s and 101’s regular?

Let the language be defined over alphabet{0,1}. Can you prove this by pumping down?
1
vote
1answer
48 views

Distinction between 2 languages.One is regular the other is not

whenever it needs to be determined if langage is regular or not, I use the notion that it is impossible for a machine to "remember" an infinte states. given 2 languages:$L_1=\{(01)^{n}(10)^{n}|n \in \...
1
vote
2answers
107 views

Prove that the language $\{a^ib^i | i\geq 0\}$ is not regular? (Do we just consider $a^nb^n$, where $n$ is the pumping length?

I think to prove that $\{a^ib^i | i\geq 0\}$ is not regular, we just have to consider the string $a^nb^n$ (which is in the language) and apply the pumping lemma. But I'm not sure how to proceed using ...
0
votes
0answers
43 views

Is this proof for pumping lemma legit?

Prove that $L=\{a^{n}b^{m}c^{k}\mid n\leq(m+k)\}$ is not regular. I used the pumping lemma as follow: there exists $n\in \mathbb{N}$ $z=uvw$ $|uv|\leq n , |v|\geq1$ $uv^iw$ is a string in L, so ...
1
vote
1answer
167 views

Use the pumping lemma to show it's not regular

I just learned pumping lemma this week and got confused on this question. B={$a^{fn}$ | $f_n$ is a Fibonacci number} for $a \in Σ$. Hint: the sequence of Fibonacci numbers get increasingly further ...
1
vote
1answer
40 views

When does $p$ break the pumping lemma

I want to prove that $\{A^iB^jC^k \mid i=j \text{ or } j=k\}$ is a not a regular language using the pumping lemma. I've found that the only way to obtain a contradiction is when $x \in A^*$, $y \in B^...
1
vote
1answer
54 views

Proof that language is not regular. $L=\{w\bar{w}|w\in \{0,1\}^* and\ \bar{w}\ is\ one's\ complement\ of\ w\}$

I'm trying to proof that the following language is not regular using pumping lemma. $L=\{w\bar{w}|w\in \{0,1\}^* and\ \bar{w}\ is\ one's\ complement\ of\ w\}$ I started by stating that: $|w\bar{w}| =...
1
vote
3answers
142 views

Proving that $ L = \{ 0^{{2n}\choose{n}} : n\in\mathbb{N} \}$ is not regular

I was asked to prove that $ L = \{ 0^{{2n}\choose{n}} : n\in\mathbb{N} \}$ is not regular. I can't solve this, could anyone help me? This was an exam question from previous year. I looked your answers,...
2
votes
0answers
75 views

Which of these languages is regular? The Pumping Lemma seems to show none are

I've been reviewing past paper questions for an automaton course, and came across a question which effectively asks, which of these languages is regular? $$ \{\ 0^m1^{(m \times n)}0^n\ \colon\ m,n\ge ...
0
votes
0answers
16 views

Regularity of language of words of prime length [duplicate]

Is the following language regular? $$ L_{\mathit{prime}} = \{ w \in \{0,1\}^* : |w| \text{ is prime} \}. $$ I have to either provide a DFA (if the language is regular), or prove that it is not ...
0
votes
1answer
63 views

Using the pumping theorem to show that this language is not context-free

Let $\sigma = \{a,b,c\}$ and let $L = \{s | s = a^jb^jc^k\}$ where $k=i\cdot j$ and $i,j \geq 0\}$. Using the pumping theorem, prove that $L$ is not context-free. I really don't know where to start, ...
4
votes
1answer
202 views

How to prove the set of powers of 2 in ternary representation to be non-regular using pumping lemma?

Given the set of natural numbers, $S = \{2^i|i\in\mathbb{N}\}$ let $L$ be the language defined as the ternary representation of all numbers in $S$. How can you prove that this is not a regular ...
1
vote
2answers
79 views

Pumping Lemma with Prime Number [closed]

$\text {Could someone please help me with this proof: }$ $L:=\left\{a^{n} d^{m} b^{k} | n, m, k \in \mathbb{N} \wedge m \text { is a prime number}\right\}$ $\text {Maybe we can say, that } w=a^{n}d^{...
0
votes
0answers
30 views

Use the pumping lemma for context free languages to prove L = {w#w | w \in {a,b}*} is not context free

I know the basics of using the pumping lemma for CFG to prove a language L is not context-free, however, the # symbol seems to be throwing me off or my understanding is not complete.
1
vote
1answer
98 views

Are number of states in a NFA same as Pumping length?

So i was reading a post on Minimum pumping length of regular language where Yuval Filmus has proved that a pumping lemma might have lesser number of states than a minimal DFA. But What about NFA's? ...
1
vote
1answer
234 views

How can I prove the minimum pumping length of finite language?

Let L be the set of all strings over {0, 1} whose lengths are at most three. Since L is regular, the pumping lemma holds for L, and thus there is a pumping length p associated with L. What is the ...
0
votes
0answers
46 views

If L is a regular language, how to show that cut(L) is not necessarily regular? [duplicate]

Given that L is a regular language. How do I show that cut(L) = {ac | abc ∈ L and |a| = |b| = |c|} is not necessarily regular? My thought process is that this problem can be re-written as: cut(L) = {...

1
2 3 4 5
9