# 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. Commented Apr 29, 2016 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/… Commented Apr 29, 2016 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. Commented Apr 29, 2016 at 10:20
• @GuilhermeBernal: POSIX ERE is regular. It's only BRE, PCRE, and other wacky stuff that's not. Commented Apr 29, 2016 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! Commented Apr 29, 2016 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. Commented Apr 29, 2016 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.
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}