6
$\begingroup$

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?

$\endgroup$
  • 15
    $\begingroup$ You cannot use the pumping lemma to prove that a language is regular, since some non-regular languages also satisfy it. $\endgroup$ – Yuval Filmus Aug 23 '18 at 14:33
  • 1
    $\begingroup$ Similar to Is a*b* regular? $\endgroup$ – Grijesh Chauhan Aug 24 '18 at 7:44
  • $\begingroup$ The language described by a regular expression is, by definition, a regular language. Either that, or you want to prove that your regular expression is equivalent to some (non)deterministic finite automata. $\endgroup$ – chepner Aug 24 '18 at 19:29
16
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The language you gave as an example of a non-regular language is regular with regex: (a*(bb)*)|b* $\endgroup$ – ratchet freak Aug 24 '18 at 12:26
  • 5
    $\begingroup$ @ratchetfreak That example contained $b^{j^2}$, the regex you supplied replaces that with $b^{2j}$ $\endgroup$ – Robin Aug 24 '18 at 14:04
18
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.