HiveBrain v1.2.0
Get Started
← Back to all entries
snippetModerate

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
generatedregularlanguageprovepumpingthatusinglemmahow

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#96551, answer score: 18

Revisions (0)

No revisions yet.