7
$\begingroup$

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?

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

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.

$\endgroup$
  • 1
    $\begingroup$ Real world regular expression are far from regular. nikic.github.io/2012/06/15/… $\endgroup$ – Guilherme Bernal Apr 29 '16 at 10:14
  • 7
    $\begingroup$ @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. $\endgroup$ – Yuval Filmus Apr 29 '16 at 10:20
  • $\begingroup$ @GuilhermeBernal: POSIX ERE is regular. It's only BRE, PCRE, and other wacky stuff that's not. $\endgroup$ – R.. Apr 29 '16 at 19:42
14
$\begingroup$

$\{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.

$\endgroup$
  • $\begingroup$ Thank you so much. That really explained the difference to me! $\endgroup$ – user6268553 Apr 29 '16 at 17:57
  • $\begingroup$ "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. $\endgroup$ – R.. Apr 29 '16 at 19:43
0
$\begingroup$

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, ..

enter image description here

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.