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:

1. L jest pusty. Wtedy L^∗ jest regularny.
2. 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.
3. 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:
   1. L_k jest pusty. Wtedy oczywiście L_k jest regularny,
   2. 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.