patternMajor
Will $L = \{a^* b^*\}$ be classified as a regular language?
Viewed 0 times
classifiedwilllanguageregular
Problem
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?
I am confused because I know that $L = \{a^n b^n\}$ is not regular. What difference does the kleene star make?
Solution
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.
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.
Context
StackExchange Computer Science Q#56745, answer score: 20
Revisions (0)
No revisions yet.