Jeśli

Na przykład, $L \subseteq \{0\}^*$ . Jak więc możemy udowodnić, że $L^*$ jest regularne?

Jeśli $L$ jest regularne, to oczywiście $L^*$ jest również regularne. Jeśli $L$ jest skończone, to jest regularne i znowu $L^*$ jest regularne. Zauważyłem również, że dla $L = \{0^p \mid p \text{ is a prime}\}$ , $L$ nie jest regularne, $L \subseteq \{0\}^*$ i $L^*$ jest regularne.

Jednak, jak pokazują to dla dowolnego podzbioru $L$ o $\{0\}^*$ ?

Załóżmy, że $L$ zawiera dwa słowa $w_1$ i $w_2$ tak że długości tych słów, $|w_1|$i $|w_2|$, nie mają wspólnych cech. Mamy zatem, że najdłuższe słowo, którego nie można utworzyć przez połączenie tych słów, ma długość $(|w_1|-1)(|w_2|-1) - 1$ ( liczba Frobeniusa). To znaczy, jeśli są słowa w języku, których długości nie mają wspólnego czynnika, wówczas wszystkie słowa o pewnej minimalnej długości są w języku $L^*$ . Łatwo zauważyć, że jest to regularne, ponieważ z konieczności istnieje skończona liczba klas równoważności pod relacją nierozróżnialności Myhill-Nerode.

Co jeśli długości wszystkich słów w mają wspólny czynnik? Cóż, nietrudno zauważyć, że w takich przypadkach L ∗ jest również regularne. Po prostu zauważ, że zamiast wszystkich słów, których długości są większe niż jakaś minimalna długość w L ∗ , prawdą jest, że wszystkie słowa, których długości są wielokrotnością GCD długości słów, będą w L ∗ , i żadne słowa, których długości nie są wielokrotnościami tego GCD, a ponieważ ( L k ) ∗ jest regularne dla dowolnej liczby całkowitej k , L ∗ jest również regularne.$L$$L^*$$L^*$$L^*$$(L^k)^*$$k$$L^*$

Jest to dość nieformalne, ale wszystko, czego potrzebujesz, aby to sformalizować, powinno być tutaj.

$w$$L^*$$L$$\mathring{L}$$w$$\mathring{L}$$L^* = \mathring{L}^*$$\mathring{L}$$L^*$

Niech będzie podzbiorem i słowie w . można wyrazić jako konkatenację słów w iffmoże być wyrażona jako suma elementy , gdzie jest zbiorem długości słowa . Problem sprowadza się zatem do wyrażenia liczby całkowitej jako sumy liczb całkowitych w określonym zestawie (z dozwolonymi powtórzeniami): canwyrazić się jako z i ?$M$$L$$w$$L$$w$$L$$|w|$$S \subset \mathbb{N}$$S$$M$$|w|$$k_1 s_1 + \ldots + k_m s_m$$\forall i, s_i \in S$$k_1 \in \mathbb{N}$

Jest to dobrze znany problem arytmetyczny, a odpowiedź jest taka, że ​​jeśli współczynniki mogą być ujemne ( ),jest do ekspresji IFF jest wielokrotnością największy wspólny dzielnik elementów : . Przy wymaganiu nieujemnych współczynników nadal obowiązuje to dla wystarczająco dużych.$(k_i)$$k_i \in \mathbb{Z}$$|w|$$S$$\gcd S$$|w|$

Rozważmy nieskończoną sekwencję zdefiniowaną przez . Jest to malejąca sekwencja liczb całkowitych (zaczynająca się od , więc jest stała po pewnym indeksie ; i Według twierdzenia o reszcie chińskiej każdy element może być wyrażone jako z i . Jeśli i , możesz wybrać wszystkie współczynniki nieujemne.$(g_i)_{i\ge\min S}$$g_i = \gcd (S \cap [0,i])$$g_{\min S} = \min S$$j$$g_j = \gcd S$$S$$k_1 s_1 + \ldots + k_m s_m$$\forall i, k_i \in \mathbb{Z}$$\{s_1, \ldots, s_m\} = S \cup [0,j]$$x \in S$$x \ge s_1 \cdot \ldots \cdot s_m$

Wystarczająca arytmetyka. Niech . Każde słowo w można wyrazić jako połączenie słów w których długość wynosi co najwyżej , tj. . Ponieważ mamy także , mamy , co jest regularne, ponieważ jest skończony, a zatem regularny.$\mathring{L} = \{w \in L \mid |w| \le g_j\}$$L$$L$$g_j$$L \subseteq \mathring{L}^*$$\mathring{L} \subseteq L$$L^* = \mathring{L}^*$$\mathring{L}$

Ewentualnie użyj charakterystyki zwykłych języków w alfabetach jednoliterowych .