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

Question

I am studying pumping lemma from Introduction to theory of computation by Michael Sipser. I wanted to check if the language generated by regular expression

 a(b*)c(d*)e

can be proved to be regular using pumping lemma. The string generated by this expression are of the form.

abcde

abbcdde...

We can not write these string in the form of $xy^iz$. We can only write it in the form $vx_1^iyx_2^jz$.

So, how can I prove using pumping lemma that the language generated by the expression is regular?

Answer 1

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 = xyz$, where $|xy| \leq p$, $y \neq \epsilon$, and $xy^iz \in L$ for all $i \geq 0$.

Unfortunately, this property doesn't characterize regular languages. That is, there exist non-regular languages which also satisfy the property stated in the lemma. An example is $\{a^i b^{j^2} : i,j \geq 0 \} \cup \{ b^k : k \geq 0 \}$.

Your language satisfies the pumping lemma with $p = 4$. If $w \in ab^*cd^*e$ has length at least 4, then it must contain $b$s or $d$s. You can check that if it contains $b$s then you can take $y = b$, and if it contains no $b$s then you can take $y = d$.

As stated above, this doesn't prove that the language is regular. The simplest way to show that $ab^*cd^*e$ is regular is to use the fact that all languages given by regular expressions are regular. It is also not hard to construct a DFA that accepts your language.

Answer 2

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) might have defined them as any of

• languages described by regular expressions;
• languages accepted by deterministic finite automata (DFAs);
• languages accepted by nondeterministic finite automata (NFAs).

If, additionally, you've proven that some or all of these definitions are equivalent, you can use any of the appropriate ones.

In this case, your language is defined by a regular expression. If that's your definition of regular languages, you're already done.

Our reference question has more information.

Answer 3

You already got your answer, this is just to make it clear that the problem you are facing is actually a logical one.

The pumping lemma is an implication: „If $L$ is regular then XYZ“. It states a necessary condition for a language to be regular (not a sufficient one). Note how the implication does not say anything about what happens if XYZ is true.

BUT you can use the contraposition of the implication, i.e. „if XYZ is not true“ to prove that a language is not regular (because we know that all regular languages do satisfy XYZ)

As already noted by the others you can show that $L$ is regular by showing that you can generate $L$ while adhering to whatever rules you have defined as being valid for regular languages (e.g. can be generated by a DFA, regular grammar, etc.). Note how OTOH you can‘t use this to show that some language is not regular, since you would need to show that no such DFA exists - but how can you know that it really doesn‘t exist and it is not simply your disability to find it? Well, here is where you can use the pumping lemma.