snippetModerate
How to prove using pumping lemma that language generated by a(b*)c(d*)e is regular?
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
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?
a(b*)c(d*)ecan 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
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.
- 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.