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) ...
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 = ...
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: ...
user avatar
10 votes

Show that for any natural number n, there is a regular language that is not recognized by any DFA with at most n final states

$\{\lambda, a, a^2, \dots, a^n\}$. All states in which these words are accepted must be different, in order to avoid loops (and stay finite).
user avatar
  • 27.6k
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$ ...
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 ...
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-...
user avatar
  • 27.6k
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$ ...
user avatar
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 ...
user avatar
8 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*} &...
user avatar
  • 70.9k
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\} \...
user avatar
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^...
user avatar
  • 34.1k
7 votes
Accepted

How does a regular language satisfies the second condition of the pumping lemma

The pumping lemma states that if a language $L$ is regular then there exists $p$ such that every word $w \in L$ that is long enough ($\lvert w \rvert \ge p$) can be split as $w = xyz$ such that $|y| \...
user avatar
7 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 ...
user avatar
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 ...
user avatar
  • 11.3k
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 ...
user avatar
  • 16.2k
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 ...
user avatar
  • 14.6k
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| \...
user avatar
  • 12.2k
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 ...
user avatar
  • 23.4k
7 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-...
user avatar
  • 1,914
6 votes
Accepted

Why does this pumping lemma application "prove" that 0*1* is not regular?

The idea is that there is some partition that fulfills the condition of the pumping lemma - you do not have the choice of the x, y, and z - you have to show that there exists no x, y, and z that ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 14.6k
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$, (...
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 ...
user avatar
  • 27.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$.
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 ...
user avatar
5 votes

Show that for any natural number n, there is a regular language that is not recognized by any DFA with at most n final states

Yes, there is a simple generalization of the Myhill-Nerode theorem that provides the characterization you seem to be looking for. Let $\sim$ be the equivalence relation defined by the Myhill-Nerode ...
user avatar
  • 141k
5 votes

Clearing a Confusion regarding the Proof of equal no of a's and b's not being a regular language

Here is what your teacher meant. Let $M=\{a^nb^n:n\geq0\} $. We know $M$ is not regular. Since the intersection of regular languages is regular, if $L$ were regular then so would $L\cap a^*b^*=M$ be, ...
user avatar
5 votes

How do I show that $a^n w b^n$ is not regular?

It's reasonable to conjecture that $L=\{a^nwb^n\mid w\in (a+b)^*, |w|=m\ge n>0\}$ is not regular, since it looks a lot like the $a^nb^n$ language, which we know isn't regular. However, $L$ is ...
user avatar
  • 14.6k

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