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.
