CODEWITHSUNDEEP
regular-languagecomputation-theory
user6268553
user6268553

Reputation: 1

Will L = {a*b*} be classified as a regular language?

Will L = {a*b*} be classified as a regular language?

I am confused because I know that L = {a^n b^n} is not regular. What difference does the kleene star make?

Upvotes: 0

Views: 263

Answers (2)

Peter Leupold
Peter Leupold

Reputation: 1212

The language described by the regular expression ab is regular by definition. These expressions cannot describe any non-regular language and are indeed one of the ways of defining the regular languages.

{a^n b^n: n>0} (this would be a formally complete way of describing it) on the other hand, cannot be described by a regular expression. Intuitively, when reaching the border between a and b you need to remember n. Since it is not bounded, no finite-memory device can do that. In ab you only need to remember that from now on only b should appear; this is very finite. The two stars in some sense are not related; each expands its block independently of the other.

Upvotes: 0

Joao Saraiva
Joao Saraiva

Reputation: 91

Well it is makes difference when you have a L = {a^n b^n} and a L = {a*b*}.

When you have a a^n b^n language it is a language where you must have the same number of a's and b's example:{aaabbb, ab, aabb, etc}. As you said this is not a regular expression.

But when we talk about L = {a*b*} it is a bit different here you can have any number of a followed by any numbers of b (including 0). Some example are:

{a, b, aaab, aabbb, aabbbb, etc}

As you can see it is different from the {a^n b^n} language where you needed to have the same numbers of a's and b's.

And yes a*b* is regular by its nature. If you want a good explanation why it is regular you can check this How to prove a language is regular they might have a better explanation then me (:

I hope it helped you

Upvotes: 1

Related Questions