# 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?

• You need to specify that n is a free variable; it looks like a constant in your expression which confused me. – user541686 Apr 29 '16 at 4:34

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.

• Real world regular expression are far from regular. nikic.github.io/2012/06/15/… – Guilherme Bernal Apr 29 '16 at 10:14
• @GuilhermeBernal That's true. Unfortunately, the expression "regular expression" is used to denote both kinds. In my answer, a regular expression is the concept defined in formal language theory. – Yuval Filmus Apr 29 '16 at 10:20
• @GuilhermeBernal: POSIX ERE is regular. It's only BRE, PCRE, and other wacky stuff that's not. – R.. GitHub STOP HELPING ICE Apr 29 '16 at 19:42

$\{a^* b^*\}$ is a regular language, since it's generated by a regular expression.

The key difference between $L_* = \{a^* b^*\}$ and $L_= = \{a^n b^n\}$ is that $L_=$ requires counting the $a$'s and $b$'s to check whether there's the same number of them, whereas $L_*$ doesn't require any counting. Counting requires unbounded memory as the number grows larger, but finite automata only have a finite amount of memory, so a finite automaton cannot recognize $L_=$. On the other hand, a finite automaton can recognize $L_*$ since that merely requires checking that the $a$'s (any number) come before the $b$'s (any number).

That's why the Kleene star doesn't define languages that require unbounded memory to recognize — it means “any number”, and each time the star is encountered, the number can be different.

• Thank you so much. That really explained the difference to me! – user6268553 Apr 29 '16 at 17:57
• "Requires unbounded memory" is a good intuitive way to think about it, but the pumping lemma is how you'd actually go about proving that it's not regular. – R.. GitHub STOP HELPING ICE Apr 29 '16 at 19:43

Any language for which you can develop a DFA.

Just check if you can draw a DFA for both of those languages.

$L_1={a^∗b^∗}$

$x^*$ denote all occurance of the alphabet $x$

Strings: $\epsilon$, a, b, aa, ab, bb, ..

To generate set of string belonging to $L_1$, machine need not to keep track of the number of a's and b's. As FA can remember only the last alphabet processed, DFA can be developed.

DFA exist.

Therefore regular.

$L_2={a^nb^n}$

Strings: $\epsilon$, aa, bb, aaa, bbb, ..

To generate set of string belonging to $L_2$, machine needs to keep track of the number of a's printed so as to print same number of b's. But FA can remember only the last alphabet processed.

To construct a machine that accept $L_2$ we need to add one more memory such a machine is called PDA (Push Down Automate).

No DFA exist.

Therefore not regular.