Skip to main content
Share Your Experience: Take the 2024 Developer Survey
18 votes

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) ...
David Richerby's user avatar
16 votes
Accepted

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

The pumping lemma states a proprety of regular languages: If $L$ is a regular language then there exists an integer $p$ such that if $w \in L$ has length at least $p$ then it can be written as $w = ...
Yuval Filmus's user avatar
13 votes
Accepted

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

Both pumping lemmas have an intuitive explanation in terms of an automaton that can recognize a language. A regular language can be recognized by a finite automaton. All words are recognized through: ...
Gilles 'SO- stop being evil''s user avatar
10 votes
Accepted

Regular language with pumping lemma

Your concatenation idea doesn't work. Although the concatenation of two regular languages is guaranteed to be regular, the concatenation of a regular language and a non-regular language is not ...
David Richerby's user avatar
10 votes
Accepted

Intuition behind the condition |xy| ≤ p in pumping lemma for regular languages

It's not needed for the proof. You can prove the lemma without this condition. Adding this condition makes the statement stronger and so more useful. The intuition here is that if a DFA has $p$ ...
Yuval Filmus's user avatar
9 votes

Regular language with pumping lemma

Raphael is right: you can use a quite standard pumping argument. David Richerby is also right: your argument does not work in this way. However ... If you want to have a result about closure of non-...
Hendrik Jan's user avatar
  • 30.8k
9 votes
Accepted

How can ws with |w| = |s| and w ≠ s be context-free while w#s is not?

Your proof is correct, and I was wrong. It took me a while to nail down where my confusion was, but with Yuval's help I think I got it. Let's consider the three languages $\qquad\begin{align*} &...
Raphael's user avatar
  • 72.5k
8 votes
Accepted

Can there be a context-sensitive pumping lemma?

Here is some evidence that there is no pumping lemma for the context-sensitive languages. Of course, an answer hinges on the question what constitutes a pumping lemma. The weakest reasonable ...
Georg Zetzsche's user avatar
8 votes

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

It's a "trick" question. The language is regular because \begin{align*} \{aba^{\mathrm{R}}\mid a,b\in\{0,1\}^*\} &= \big\{\varepsilon b\varepsilon^{\mathrm{R}}\mid b\in\{0,1\}^*\big\} \...
David Richerby's user avatar
8 votes
Accepted

Existence of a CFL $L$ such that $\sqrt{L}$ is not CFL

There is an example, and $L = \{a^nb^na^{2m}b^ka^k \mid n,m,k \in \mathbb{N}\}$ does the trick. We get that $\sqrt{L} = \{a^nb^na^n \mid n \in \mathbb{N}\}$, which is a standard example of a non-...
Arno's user avatar
  • 3,103
8 votes
Accepted

Is this language a context-free language or not?

No, $L_1$ is not necessarily context-free. For example, let $L=\{0^n1^{3n}\mid n\ge0\}$. If $ uv=0^n1^{3n}$ and $|u|=|v|$, then $u=0^n1^n$ and $v=1^{2n}$. We have $u^Rv^R=1^n0^n1^{2n}$. So, $L_1=\{1^...
John L.'s user avatar
  • 39k
7 votes
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 ...
Rick Decker's user avatar
  • 14.8k
7 votes

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

It's not so evident, but you can also apply the PL directly: let $p$ be the pumping length pick $w = 0^p 1^{p + p!}$ Clearly $w \in L$ The pumping lemma says that $w = xyz$ with $|xy| \leq p, |y| \...
Vor's user avatar
  • 12.5k
7 votes
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 ...
Steven's user avatar
  • 29.5k
6 votes

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 ...
Rick Decker's user avatar
  • 14.8k
6 votes

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 ...
Yuval Filmus's user avatar
6 votes
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$, (...
Yuval Filmus's user avatar
6 votes

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 ...
Hendrik Jan's user avatar
  • 30.8k
6 votes

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$.
Daniel Mroz's user avatar
6 votes
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 ...
user2357112's user avatar
5 votes
Accepted

Misconception in taking Pumping Length of language {a} to be $2$

Informally, the pumping lemma for regular languages state that any sufficient large string may be pumped. Your language is finite, meaning if you pick a pumping length that is larger than any string ...
Auberon's user avatar
  • 1,314
5 votes

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. ...
gnasher729's user avatar
  • 30.4k
5 votes
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 ...
quicksort's user avatar
  • 4,262
5 votes
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$, ...
Yuval Filmus's user avatar
5 votes

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 ...
potestasity's user avatar
5 votes
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 ...
John L.'s user avatar
  • 39k
5 votes
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 ...
David Richerby's user avatar
5 votes

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 ...
Yuval Filmus's user avatar
4 votes
Accepted

Structure of a Pumping Lemma proof: contradiction or counterexample?

this is not context-free/regular because I can come up with a counterexample which fails the pumping lemma You are missing that in order to construct this counterexample you have to assume that $L$ ...
Raphael's user avatar
  • 72.5k
4 votes

How to prove {a^(n^2) | n>0} is not context-free?

[Since (a) this is an instance of a standard problem and (b) I wasn't able to find it in the archives, I'll expand my comment into a hinted solution.] As usual in problems like this, we assume that ...
Rick Decker's user avatar
  • 14.8k

Only top scored, non community-wiki answers of a minimum length are eligible