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.

404 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
81 views

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 ...
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 ...
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^...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
53 views

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 ...
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 ...
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?
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 ...
306 views

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.
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? ...