# Tag Info

### How to prove using pumping lemma that language generated by a(b*)c(d*)e is regular?

You can't. The pumping lemma can only be used to prove that a language is non-regular. How to prove that it is regular depends on how you've defined regular languages. You (or your course or textbook) ...
• 82.1k
Accepted

• 72.8k

• 39.1k
Accepted

### Prove if $L = \{0^m1^n \mid m \neq n\}$ is regular or not

You don't need to invoke the PL directly here. Instead, we'll do a proof by contradiction. Suppose $L$ was regular, then, since regular languages are closed under complement, $\overline{L}$ is regular ...
• 14.9k
Accepted

### Irregularity of $\{ w_1 aa w_2 \mid |w_1| \neq |w_2| \}$

For $i \ge 0$ define $w_i = b^i aa$. For any $i,j \ge 0$ with $i \neq j$ you have that $b^i$ is a distinguishing extension for $w_i$ and $w_j$. Indeed, $w_i b^i \not\in L_2$ but $w_jb^i \in L_2$. Then ...
• 29.6k

### Proving the Language is not regular for $(a^n)^n$

You're on the right track. Here are a few missing details. First, note that $(a^n)^n=a^{n^2}$, so you want to prove that $L=\{a^{n^2}\mid n\ge 0\}$ isn't regular. Assume $L$ is regular. Since $L$ is ...
• 14.9k

### Show that a language consisting of strings of a prime number of 1s is irregular using pumping lemma

Your attempt doesn't work, since you need the word you pick to belong to the language. Therefore I suggest picking $w = 1^p$, where $p$ is a prime which is larger than the pumping constant. The ...
• 278k
Accepted

### What is the minimal pumping length of this string $(01)^*$

The pumping length of a regular language $L$ is the minimal $p$ such that every word $w \in L$ of length at least $p$ can be split as $w = xyz$ such that (i) $|xy| \leq p$, (ii) $y \neq \epsilon$, (...
• 278k

### Why does the Pumping-lemma for context-free languages use uvwxy, but the one for regular ones uvw?

That is because of the "structure" of the languages that is observed by the respective pumping lemma's. Have a look at the proofs of the respective pumping results. For regular languages the ...
• 30.9k

### is this language regular and why pumping lemma doesn't work?

Write the word $s'$ as $$s' = 0^{(p-\beta)} \left(1^p01^p0^{\beta} \right)0^{(p -\beta)}$$ to see that it is in fact in $L$.
• 376
Accepted

### is this language regular and why pumping lemma doesn't work?

Your use of the pumping lemma is incorrect. First, to show that the pumping lemma fails to hold in the case of your string $S$ (and thereby prove $L$ non-regular), you would have to show that every ...
• 312

### Is the language of words containing equal number of 001 and 100 regular?

It's a trick question. Try constructing a string that contains two 001 and doesn't contain a 100, and see why you can't do it. If X = "number of 001", and Y = "number of 100", then X = Y or X = Y ± 1. ...
• 31.4k
Accepted

### Proving $a^{2+n}a^{n}$ is regular using the Pumping Lemma

Noooooo! Usage of the pumping lemma to prove regularity is remarkably rare, and certainly won't happen with a direct application. Let's review the formal statement, with particular emphasis on the ...
• 4,272
Accepted

### Proving that language $L = \{ a^{2n}: n \geq 1\}$ is regular

The pumping lemma states that if a language $L$ is regular then there exists an integer $p$ such that every word $w \in L$ of length at least $p$ has a decomposition $w = xyz$ such that $|xy| \leq p$, ...
• 278k

### Prove this language is non-regular

Your language could be rewritten more clearly as: $\{ a^m \mid m \text{ is a perfect cube} \}$ Now you'd have to find a word from this language, longer than the pumping length $p$, that can not be ...
• 333
Accepted

### Can the pumping lemma for context free languages be extended to any subword?

The extended form of pumping lemma for regular languages you mentioned is called "the general version of pumping lemma for regular languages". It is indeed natural to suspect that a similar general ...
• 39.1k
Accepted

### What is the importance of the condition "| xy | < p" in pumping lemma?

$p$ is the number of states in the automaton. As you say, the pumping lemma is about the pigeonhole principle. Suppose that $q$ is the first state that's repeated when you read input $w$. Then ...
• 82.1k

### Is the set of languages satisfying the pumping lemma closed under concatenation?

Suppose that $L_1$ satisfies the pumping lemma: there exists $p_1$ such that every word $w \in L_1$ of length at least $p$ can be decomposed as $w = xyz$, where $|xy| \leq p_1$, $y \neq \epsilon$, and ...
• 278k
$s$ consists of $p$ zeroes followed by, well, it doesn't matter what. $xy$ is the start of $s$ and consists of at most the first $p$ characters of $s$. All of those $p$ ...