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) ...
- 81.4k
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 = ...
- 274k
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:
...
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$ ...
- 274k
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 ...
- 81.4k
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-...
- 29.6k
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*}
&...
- 71.9k
8
votes
What's wrong with my pumping lemma proof?
The problem is in the quantifiers. The pumping lemma says that any string $s$ with $|s|\geq p$ can be written as $xyz$ such that the three properties hold. It doesn't say that every way of writing it ...
- 81.4k
8
votes
Accepted
Pumping Lemma for $L = \left \{ a^{c}\mid \text{c is a composite number} \right \}$
Let $p$ be the pumping length, and choose a prime $q > p$. The word $a^{q^2}$ is in $L$, and so it can be written as $a^{q^2} = uvwxy$ so that $|vwx| \leq p$, $|vx| \geq 1$, and $uv^iwx^iy \in L$ ...
- 274k
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 ...
- 361
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\}
\...
- 81.4k
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-...
- 2,649
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^...
- 38.5k
7
votes
Accepted
Is {ww^r ww^r} a context-free language?
It's not context free for the same reason that $L' = \{w w \mid w \in \Sigma^*\}$ is not context free, and the proof below is a simple adaption of the standard proof for the language $L'$, using the ...
- 11.8k
7
votes
Is no language with the non-primes property context-free?
You can use Parikh's theorem to prove this claim.
Indeed, if such a language was context-free, then its Parikh image would be regular. But the Parikh image would also satisfy the condition (as it ...
- 17k
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 ...
- 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| \...
- 12.4k
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 ...
- 27.4k
6
votes
Pumping lemma: if you can keep pumping, what does this tell you?
If you are not sure, it is probably because you want to know why. This question is frequent among students in computer science that are learning the pumping lemma for the first time and it is the ...
- 1,335
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 ...
- 14.8k
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$, (...
- 274k
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 ...
- 29.6k
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$.
- 376
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 ...
- 310
5
votes
Accepted
Showing that the pumping lemma cannot prove that some language is not regular
The idea of this exercise is to show that the pumping lemma is not a sure-fire method to prove that a language isn't regular. To show that, we need to come up with a language that (i) isn't regular, ...
- 274k
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. ...
- 27.8k
5
votes
Accepted
Pumping lemma regular language can't be pumped
Have a look at the exact wording of the pumping lemma: It has a precondition that only words exceeding a certain size need to be pumpable. This is exactly so that only words with repetitions have to ...
- 607
5
votes
Proving non-regularity of $u u^R v$?
When you are stuck in a place like this, it pays to check if the method can work at all. That is, try to prove the opposite. Since the Pumping lemma does not characterise REG, this is actually ...
- 71.9k
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 ...
- 1,304
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 ...
- 4,202
Only top scored, non community-wiki answers of a minimum length are eligible