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) ...
- 82.1k
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 = ...
- 278k
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:
...
11
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$ ...
- 278k
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 ...
- 82.1k
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-...
- 30.9k
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*}
&...
- 72.8k
8
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.6k
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\}
\...
- 82.1k
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-...
- 3,213
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^...
- 39.1k
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.9k
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 ...
- 29.6k
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.9k
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 ...
- 278k
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$, (...
- 278k
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 ...
- 30.9k
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 ...
- 312
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. ...
- 31.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 ...
- 4,272
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$, ...
- 278k
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 ...
- 333
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 ...
- 39.1k
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 ...
- 82.1k
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 ...
- 278k
4
votes
Why does this Pumping Lemma example show irregularity?
$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$ ...
- 82.1k
4
votes
Why does this Pumping Lemma example show irregularity?
You cannot proceed in this way. The Pumping Lemma for regular languages tells us that if a language $L$ is regular, then there exists a $p \geq 0$ such that every $s \in L$ such that $\lvert s \rvert \...
- 2,516
4
votes
Accepted
Why does this pumping lemma proof not cover every division of xyz?
For reference, the pumping lemma is (from Introduction to the Theory of Computation by Michael Sipser)
If $A$ is a regular language, then there is a number $p$ (the
pumping length) where if $s$ ...
- 851
Only top scored, non community-wiki answers of a minimum length are eligible