====== JFiZO - Zadanie 09.004 ======
Niech $L$ będzie dowolnym podzbiorem $0^∗$ . Udowodnij, że $L^∗$ jest językiem regularnym.

**Rozwiązanie.** Rozpatrzmy dowolny język $L \subseteq 0^∗$ . Rozważmy trzy przypadki:
  - $L$ jest pusty. Wtedy $L^∗$ jest regularny.
  - $L$ jest niepusty i zawiera wyłącznie słowo puste. Wtedy $L^∗$ również składa się wyłącznie ze słowa pustego – jest więc regularny.
  - $L$ jest niepusty i istnieje najkrótsze niepuste słowo $v$. Niech $n = |v|$ i niech $L_k = \lbrace w : w \in L^∗$ oraz $|w| \mbox{ mod } n = k \rbrace$. Pokażemy, że dla każdego $k$ język $L_k$ jest regularny, co znaczy, że $L^∗$ jest regularny (jako suma skończenie wielu języków regularnych). Weźmy dowolne $k$. Rozważmy przypadki:
       - $L_k$ jest pusty. Wtedy oczywiście $L_k$ jest regularny,
       - $L_k$ nie jest pusty – wtedy istnieje najkrótsze słowo $v'$, które należy do języka $L_k$. Do języka $L_k$ należą więc wszystkie wyrazy długości $|v'| + ln$, gdzie $l \in \mathbb{N}$ (do każdego wyrazu możemy „dokleić” dowolną ilość razy wyraz $v$ o długości $n$). Co oznacza, że $L_k$ jest regularny, ponieważ opisuje go wyrażenie $v'(0^n)^∗$.

**Przykład.**
  * $L = \{aaa, aaaaa, aaaaaaa\}$
  * $n = 3$
  * $L^* = \{a^3, a^5, a^6, a^7, a^8, a^9, a^{10}, a^{11}, ...\}$
  * $L_k = \{w : w \in L^* |w| mod 3 = k\}$
  * $L_0 = \{a^3, a^6, a^9, ...\}$
  * $L_1 = \{a^7, a^{10}, a^{13}, ...\}$
  * $L_2 = \{a^5, a^8, a^{11}, ...\}$
  * Każde $L_k$ ma kolejne elementy o długości $|v'| + ln$, ponieważ do $v'$ możemy doklejać wyraz $n$ z języka $L$.
{{tag>[listy_zadan]}}