Se é um subconjunto de , como podemos mostrar que é regular?

Diga . Então, como podemos provar que é regular?L $L \subseteq \{0\}^*$$L^*$

Se é regular, é claro que também é regular. Se é finito, então é regular e novamente é regular. Também notei que, para , não é regular, e é regular.L ∗ L L ∗ L = { 0 p ∣ p  é primo } L L ⊆ { 0 } ∗ L $L$$L^*$$L$$L^*$$L = \{0^p \mid p \text{ is a prime}\}$$L$$L \subseteq \{0\}^*$$L^*$

Mas como mostrar isso para qualquer subconjunto de ?{ 0 } $L$$\{0\}^*$

Suponha que contenha duas palavras e , de forma que os comprimentos dessas palavrase, não tem fatores em comum. Então, temos que a palavra mais longa que não pode ser formada concatenando essas palavras tem comprimento ( número Frobenius ). Ou seja, se houver palavras no idioma cujos comprimentos não tenham um fator comum, todas as palavras de um determinado comprimento mínimo estarão no idioma . É fácil perceber que isso é regular, pois, necessariamente, há um número finito de classes de equivalência sob a relação de indistinguibilidade de Myhill-Nerode.w 1 w 2 | w 1 | | w 2 | ( | w 1 | - 1 ) ( | w 2 | - 1 ) - 1 L $L$$w_1$$w_2$$|w_1|$$|w_2|$$(|w_1|-1)(|w_2|-1) - 1$$L^*$

E se o comprimento de todas as palavras em compartilhar um fator comum? Bem, não é difícil ver que, nesses casos, também é regular. Simplesmente observe que, em vez de todas as palavras cujos comprimentos são maiores que algum comprimento mínimo em , será verdade que todas as palavras cujos comprimentos são múltiplos do GCD dos comprimentos de palavras estarão em , e nenhuma palavra cujos comprimentos não são múltiplos desse GCD, e como é regular para qualquer número inteiro , também é regular.L ∗ L ∗ L ∗ ( L k ) ∗ k L $L$$L^*$$L^*$$L^*$$(L^k)^*$$k$$L^*$

Isso é bastante informal, mas tudo o que você precisa para formalizar isso deve estar aqui.

A idéia básica é que, em um idioma construído em um alfabeto de uma letra, cada palavra suficientemente longa seja uma concatenação de palavras mais curtas. Portanto, quando você pega uma palavra em , ou seja, uma concatenação de palavras em , existe um central, tal que é uma concatenação de palavras em . Assim, . Acontece que é finito, portanto, e são regulares.L ∗ L ˚ L w ˚ L L ∗ = ˚ L ∗ ˚ L L $w$$L^*$$L$$\mathring{L}$$w$$\mathring{L}$$L^* = \mathring{L}^*$$\mathring{L}$$L^*$

Deixe- ser um subconjunto de e uma palavra em . pode ser expresso como uma concatenação de palavras em iffpode ser expresso como uma soma de elementos de , onde é o conjunto de comprimentos de palavras . Assim, o problema se reduz à expressão de um número inteiro como uma soma de números inteiros em um conjunto específico (com repetições permitidas): canser expresso como com e ?L w L w L | w | S ⊂ N S M | w | k 1 s 1 + … + k m s m ∀ i , s i ∈ S k 1 ∈ $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}$

Esse é um problema bem conhecido em aritmética, e a resposta é que, se os coeficientes puderem ser negativos ( ),é exprimível sse é um múltiplo do máximo divisor comum dos elementos de : . Com a exigência de coeficientes não negativos, isso ainda é válido para suficientemente grandes .k i ∈ Z | w | S gcd S | w $(k_i)$$k_i \in \mathbb{Z}$$|w|$$S$$\gcd S$$|w|$

Considere a sequência infinita definida por . Essa é uma sequência decrescente de números inteiros (iniciando com , portanto é constante após um certo índice ; e No teorema chinês restante, todo elemento de pode ser expresso como com e . Se e , você pode selecionar todos os coeficientes não negativos. g i = gcd ( S ∩ [ 0 , i ] ) g min S = min S j g j = gcd S S k 1 s 1 + … + k m s m ∀ i , k i ∈ Z { s 1 , … , s $(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$

Aritmética suficiente. Vamos . Cada palavra em pode ser expressa como uma concatenação de palavras em cujo comprimento é no máximo , ou seja, . Como também temos , temos , que é regular, pois é finito e, portanto, regular.$\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}$

Como alternativa, use a caracterização de idiomas regulares em alfabetos de uma letra .