Problem Detail: 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?
Asked By : user6268553
Answered By : Yuval Filmus
A language is regular, by definition, if it is accepted by some DFA. (This is at least one common definition.) Can you think of a DFA accepting the language? A well-known result (that is proved in many textbooks) states that the language of a regular expression is regular. Since $a^* b^*$ is a regular expression, its language must be regular (if you believe this result). Finally, to answer your question (what difference does the Kleene star make): in the language ${a^n b^n : n geq 0}$, we need to count the number of $a$s and $b$s; in the language $a^*b^*$ we don’t.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/56745