Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I'm doing my homework, but there's one task that I didn't get the idea.
Task:
Recall the alternative definition for the star of a language A that we gave just before Theorem 2.3.1. In Theorems 2.3.1 and 2.6.2 (which is about closure under union operation), we have shown that the class of regular languages is closed under the union and concatenation operations. Since $A^* = \cup_{𝑘=0}^\infty 𝐴^𝑘$, why doesn’t this imply that the class of regular languages is closed under the star operation?
One must be careful about what the closure properties actually state.
If $A,B$ are regular languages, then $AB$ and $A \cup B$ are regular languages as well.
By induction, one can obtain that the concatenation / union of finitely many regular languages $A_1,\ldots,A_n$ is regular.
This however does not extend to infinite unions!
To understand why the extension would be wrong, consider a simpler case, first. Take the class of finite languages: sets containing finitely many words. Clearly this class is closed under union: if $A,B$ are finite languages, then $A\cup B$ is a finite language. However, taking the union of the infinitely many finite languages $\{1\},\{11\},\{111\},\ldots$ one gets an infinite language $\{1,11,111,\ldots\}$.
In the realm of regular languages, we met the same problem. Take any non-regular language $L$: it has to be infinite, since otherwise it would be regular. We can write $L=\{w_1,w_2,\ldots\}$ for some $w_1,w_2,\ldots$. But we also have $L=\{w_1\}\cup\{w_2\}\cup\ldots = \bigcup_{i\geq 1}\{w_i\}$, which is an infinite union of singleton-languages, which are regular. So, any non regular $L$ can be written as an infinite union of regular languages.
We conclude that the union of infinitely many regular languages is not necessarily a regular language.
$A^* = \cup_{𝑘=0}^\infty 𝐴^𝑘$ is just the definition of $star$-closure and this do not imply at all that if you take a regular language $L$ then $L^*$ is regular. For that you need to prove the theorem you mention.
