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?
$\begingroup$
$\endgroup$
1
-
3$\begingroup$ You need to specify that n is a free variable; it looks like a constant in your expression which confused me. $\endgroup$– user541686Commented Apr 29, 2016 at 4:34
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
3
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.
answered Apr 28, 2016 at 21:22
-
1$\begingroup$ Real world regular expression are far from regular. nikic.github.io/2012/06/15/… $\endgroup$ Commented Apr 29, 2016 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$ Commented Apr 29, 2016 at 10:20
-
$\begingroup$ @GuilhermeBernal: POSIX ERE is regular. It's only BRE, PCRE, and other wacky stuff that's not. $\endgroup$ Commented Apr 29, 2016 at 19:42
$\begingroup$
$\endgroup$
2
$\{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.
answered Apr 28, 2016 at 21:25
Gilles 'SO- stop being evil'Gilles 'SO- stop being evil'
43.9k8 gold badges118 silver badges184 bronze badges
-
$\begingroup$ Thank you so much. That really explained the difference to me! $\endgroup$ Commented Apr 29, 2016 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$ Commented Apr 29, 2016 at 19:43
$\begingroup$
$\endgroup$
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.
