# 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) ...
• 80.3k
Accepted

• 70.9k

### 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\} \...
• 80.3k
Accepted

• 270k

### 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 ...
• 80.3k
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.3k

### 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 ...
• 16.2k
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.6k