Linguagem dos valores de uma função afim

Escreva para a expansão decimal de (sem avanço ). Deixe e ser inteiros, com . Considere o idioma das expansões decimais dos múltiplos de mais uma constante:$\bar n$$n$0$a$$b$$a > 0$$a$

é regular? sem contexto?$M$

(Contraste com o idioma do gráfico de uma função afim )

_{Eu acho que isso seria uma boa pergunta para a lição de casa; portanto, as respostas que começam com uma ou duas dicas e explicam não apenas como resolver a questão, mas também como decidir quais técnicas usar serão apreciadas.}

Muito simples: suponha que os números sejam escritos em decimal (outras bases são tratadas por uma modificação trivial). Construir um DFA, com estados 0, 1, ..., . O estado inicial é 0 e, do estado na entrada, o dígito passa para o estado . O estado de aceitação é (pode ser necessário um ajuste se ).$a$$a - 1$$q$$d$b mod a b > $(10 q + d) \bmod a$$b \bmod a$$b > a$

Isso é regular. Vamos primeiro trabalhar em binário, que generalizará para qualquer base> 1. Seja o idioma em questão. Para a = 1, b = 0, obtemos$M_{a,b}$

$M_{1,0} = \{1, 10, 11, 100, 101, ...\}$

que é todas as strings acima de sem zeros à esquerda, o que é regular (construa uma expressão regular para ela).$\{0,1\}$

Agora, para qualquer , com b ainda 0, obtemos de multiplicando numericamente por a, ou seja, executando a transformação em cada sequência de . Isso pode ser feito bit a bit por uma sequência de turnos e adições de que dependem dos bits da cadeia fixa . As duas transformações que precisamos são:H um , 0 M 1 , 0 ˉ x → ¯ um x M um , 0 x ˉ $a$$M_{a,0}$$M_{1,0}$$\bar x \rightarrow \overline {ax}$$M_{a,0}$$x$$\bar a$

ˉ x → ˉ x$\bar x \rightarrow \overline {2x}$ que é$\bar x \rightarrow \bar x0$

e

$\bar x \rightarrow \overline {2x+x}$

Concatenar um 0 à direita preserva claramente a regularidade. Portanto, temos apenas que provar que a segunda operação preserva a regularidade. A maneira de fazer isso é com um transdutor de estado finito trabalhando em da direita para a esquerda. Esse é o passo mais difícil. Sugiro fazê-lo com um programa de pseudo-código e alguma memória auxiliar finita (como algumas variáveis ​​de bit) em vez de usar estados. Contanto que a memória tenha um tamanho fixo em todas as entradas e você digitalize estritamente da direita para a esquerda, é uma transdução de estado finito e preserva a regularidade.$\bar x$

Finalmente, para obter de , precisamos adicionar numericamente a cada string, mas isso é feito com um transdutor semelhante que depende do número fixo b. M a , 0 b T $M_{a,b}$$M_{a,0}$$b$$T_b$

Para fazer o mesmo em qualquer base, mostre adicionalmente como realizar a multiplicação com um único dígito nessa base, usando um transdutor que depende de d. Com isso, podemos multiplicar por números de vários dígitos e ainda permanecer nos idiomas regulares. Ou, podemos refiná-lo dizendo que a multiplicação por é apenas uma adição repetida.S d$d$$S_d$$d$

Você queria apenas dicas. Cada uma dessas etapas depende de um teorema / técnica bastante complexo, portanto, provar que essas provas são completas será o trabalho extra.

Dica 1 : primeiro resolva o problema mais popular "escreva um autômato que reconheça as representações decimais / binárias dos números divisíveis por 3" quando o bit menos significativo aparecer primeiro.

Pergunta intermediária: prove que é regular.$\{ \overline{a\,x+b}\mid a\,x+b≥0 \quad x\in\mathbb{Z}\}$

Dica 2 : O gráfico da função "módulo " é finito. Você pode calculá-lo para cada em que é o conjunto de dígitos e o idioma do seu autômato.a d { 0 , … , 9 $(n \mapsto 10n+d)$$a$$d$$\{0, \dots, 9\}$

Dica # 3 : agora, substitua com . O que isso muda? Tente usar o fato de que linguagens regulares são estáveis ​​por interseção em vez de criar um autômato ad-hoc . x ∈ $x∈\mathbb Z$$x∈\mathbb N$

Dica # 4 : agora supor que é um número primo (de modo que é um campo) e que ainda estamos no caso em que . Agora usamos uma representação em que o primeiro bit é o bit mais significativo . Você pode construir o autômato da mesma maneira?Z / a Z x ∈ $a$$\mathbb Z/a\mathbb Z$$x∈\mathbb Z$

Dica 5 : você nem sempre precisa criar um autômato para provar que uma linguagem é regular. Como você pode usar os resultados anteriores para provar que é regular? (com o bit mais significativo primeiro)$M$

Estou seguindo a ideia de @vonbrand:

Dica 1:

Resolva primeiro para . Você pode usar o teorema de Myhill-Nerode .$b=0$

Definimos a seguinte relação . Esta é obviamente uma relação de equivalência. Além disso, é congruente à direita, pois, se anexarmos um dígito , obteremos . Finalmente, satura , pois é a classe de equivalência . Como possui um número finito de classes, temos pelo Teorema de Myhill-Nerode que ele é regular. A FSA associada é mínima e tem estados.d ˉ x ≈ ˉ $\bar x\approx \bar y :\iff x\equiv y \mod a$$d$$\bar x \approx \bar y \iff 10x+d \equiv 10y+d \mod a \iff \bar x d \approx \bar y d$$L$$L$$[0]$$\approx$$a$

Dica 2:

Resolva o caso geral, reutilize o autômato induzido pelo caso .$b=0$

Sabemos que o idioma é regular para . Assim simplesmente tomar a estado FSA para o idioma. Agora vamos construir uma FSA para . Suponha que tenha dígitos. Em seguida, o FSA se ramifica como uma árvore com 10 anos de profundidade e contém todos os caminhos para números com dígitos. Todos os estados que podem ser alcançados com um número que não está no formato estão rejeitando a aceitação. Finalmente, conectamos a parte da árvore da FSA ao autômato , de acordo com o restante da divisão por .$b=0$$a$$M$$b=0$$L$$b$$k$$k$$k$$ax+b$$M$$a$

O idioma é regular.

Dica: expulse nove

Ideia de prova

Para e ,$a=9$$b < 9$

crie um autômato com estados rotulados de a . é o estado inicial e o único estado final é . Do estado , no dígito , faça a transição para o estado .$9$$0$$8$$0$$b$$s$$d$$(s + d) \;\mathrm{mod}\; 9$

Para manipular outros valores de que são coprime com ,$a$$10$

agrupe dígitos em pacotes para encontrar algum tal que divida (por exemplo, pegue se porque ).$k$$a$$10^k-1$$k=3$$a=37$$999 = 27 \times 37$

Para manipular valores de cujos únicos fatores primos são e ,$a$$2$$5$

observe que se trata de um número finito de dígitos no final.

Para generalizar para todos os valores de e ,$a$$b$

use o fato de que a união e a interseção de idiomas regulares são regulares, que idiomas finitos são regulares e que os múltiplos de são exatamente os múltiplos de ambos quando e são coprimes.$a_1 \cdot a_2$$a_1$$a_2$

Observe que usamos a técnica que for mais conveniente; as três principais técnicas elementares (expressões regulares, autômatos finitos, propriedades da teoria dos conjuntos) estão representadas nesta prova.

Prova detalhada

Seja com coprime com . Seja e . Por aritmética elementar, os números iguais a módulo são exatamente os números iguais a módulo e módulo , então . Como a interseção de idiomas regulares é regular e$a = 2^p 5^q a'$$a'$$10$M ″ = { ¯ 2 p 5 $M' = \{\overline{a'\,x+b} \mid x\in\mathbb{Z} \wedge a'\,x+b \ge 0\}$$M'' = \{\overline{2^p 5^q\,x+b} \mid x\in\mathbb{Z} \wedge 2^p 5^q\,x+b \ge 0\}$$b$$a$$b$$a'$$b$$2^p5^q$$M \cap \{\overline{x} \mid x \ge b\} = M' \cap M'' \cap \{\overline{x} \mid x \ge b\}$$\{\overline{x} \mid x \ge b\}$é regular porque é o complemento de uma linguagem finita (portanto regular), se e também são regulares, então é regular; e é, portanto, regular, pois é a união dessa linguagem com um conjunto finito. Portanto, para concluir a prova, basta provar que e são regulares.$M'$$M''$$M \cap \{\overline{x} \mid x \ge b\}$$M$$M'$$M''$

Vamos começar com , ou seja, números módulo . Os números inteiros cuja expansão decimal está em são caracterizados por seus últimos dígitos , pois alterar os dígitos à esquerda significa adicionar um múltiplo de que é um múltiplo de . Portanto, onde é o alfabeto de todos os dígitos e é um conjunto finito de palavras de comprimento e é um idioma comum.$M''$$2^p 5^q$$M''$$\mathrm{max}(p,q)$$10^{\mathrm{max}(p,q)}$$2^p 5^q$$0^* M'' = \aleph^* F$$\aleph$$F$$\mathrm{max}(p,q)$$M'' = (\aleph^* F) \cap ((\aleph \setminus \{0\}) \aleph^*)$

Passamos agora para , ou seja, números módulo onde é coprime com . Se então é o conjunto de expansões decimais de todos os naturais, ou seja, , que é um linguagem regular. Agora assumimos . Seja . Pelo pequeno teorema de Fermat, , ou seja, a divide . Construímos um autômato finito determinístico que reconhecerá seguinte maneira:$M'$$a'$$a'$$10$$a' = 1$$M'$$M' = \{0\} \cup ((\aleph \setminus \{0\}) \aleph^*)$$a' > 1$$k = a'-1$$10^{a'-1} \equiv 1 \mod a'$$a'$$10^k-1$$0^* M'$

• Os estados são . A primeira parte representa uma posição de dígito e a segunda parte representa um módulo numérico .$[0,k-1] \times [0,10^k-2]$$10^k-1$
• O estado inicial é .$(0,0)$
• Existe uma transição rotulada de para se s e .$d$$(i,u)$$(j,v)$$v \equiv d 10^i + u \mod 10^k-1$$j \equiv i + 1 \mod k$
• Um estado é final se (observe que divide ).$(i,u)$$u \equiv b \mod a'$$a'$$10^k-1$

O estado alcançado a partir de uma palavra satisfaz e . Isso pode ser provado por indução sobre a palavra, após as transições no autômato; as transições são calculadas para isso, usando o fato de que . Assim, o autômato reconhece as expansões decimais (permitindo zeros iniciais) dos números da forma com ; Como , o autômato reconhece as expansões decimais dos números iguais a módulo permitindo zeros iniciais, o que é$(i,u)$$\overline{x}$$i \equiv |\overline{x}| \mod k$$u \equiv x \mod 10^k-1$$10^k \equiv 1 \mod 10^k-1$$u + y 10^k$$u \equiv b \mod a'$$10^k \equiv 1 \mod a'$$b$$a'$$0^* M'$ . Esta linguagem é assim provada regular. Finalmente, é uma linguagem comum.$M' = (0^* M') \cap ((\aleph \setminus \{0\}) \aleph^*)$

Para generalizar para bases diferentes de , substitua e acima por todos os fatores primos da base.$10$$2$$5$

Prova formal

Deixado como um exercício para o leitor, no seu provador de teoremas favorito.