Proving that $L^*$ is regular if $L$ is

35 Views Asked by At

I know that if $L\in REG$ then you can build an automata that accepts $L^*$, but I was wondering if my approach is also good. I thought about showing that $$L^*=\{\epsilon\} \cup \bigcup_{n\in \mathbb{N}}L^n$$ Where $$L^n=\{\omega_1 \ldots \omega_n \colon \omega_1 \in L,\ldots , \omega_n \in L \}$$

And then concluding by induction that $L^n$ is regular for every $n$ (since the set of regular languages is closed under union) and finally that $L^*$ is also regular.

So,

Do I have a mistake here, or is this approach valid? thanks!

1

There are 1 best solutions below

1
On BEST ANSWER

The approach is not valid: the class of regular languages is closed under finite unions but not under arbitrary unions. Thus, your approach could be used to show that $\bigcup_{k\le n}L^k$ is regular for each $n$, but it does not follow that $\bigcup_nL^n$ is regular.

To see why this must be so, let $L$ be any language that is not regular, say $L=\{w_n:n\in\Bbb N\}$. For each $n\in\Bbb N\}$ let $L_n=\{w_n\}$. Each of the languages $L_n$ is finite and therefore regular, but $\bigcup_{n\in\Bbb N}L_n=L$ is not regular.