Lenguaje de los valores de una función afín.

Escriba para la expansión decimal de (sin encabezado ). Deje y ser enteros, con . Considere el lenguaje de las expansiones decimales de los múltiplos de más una constante:$\bar n$$n$0$a$$b$$a > 0$$a$

¿ M es $M$regular? sin contexto?

(Contraste con el lenguaje de la gráfica de una función afín )

_{Creo que esta sería una buena pregunta para la tarea, por lo que las respuestas que comienzan con una pista o dos y explican no solo cómo resolver la pregunta sino también cómo decidir qué técnicas usar serían apreciadas.}

Muy simple: suponga que los números se escriben en decimal (otras bases se manejan mediante una modificación trivial). Construir un DFA, con estados 0, 1, ..., . El estado inicial es 0, y desde el estado en la entrada, el dígito va al estado . El estado de aceptación es (podría necesitar un ajuste si ).a - 1 q d ( 10 q + d ) mod a b mod a b > $a$$a - 1$$q$$d$$(10 q + d) \bmod a$$b \bmod a$$b > a$

Es regular. Primero trabajemos en binario, que se generalizará a cualquier base> 1. Sea el idioma en cuestión. Para a = 1, b = 0 obtenemos$M_{a,b}$

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

que es todas las cadenas sobre sin ceros a la izquierda, lo cual es regular (construya una expresión regular para ello).$\{0,1\}$

Ahora para cualquier , con b todavía 0 obtenemos de multiplicando numéricamente por a, es decir, realizando la transformación en cada cadena de . Eso se puede hacer a nivel de bits mediante una secuencia de cambios y adiciones de que dependen de los bits de la cadena fija . Las dos transformaciones que necesitamos son:M a , 0 M 1 , 0 ˉ x → ¯ a x M a , 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 es$\bar x \rightarrow \bar x0$

y

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

Concatenar un 0 a la derecha conserva claramente la regularidad. Por lo tanto, solo tenemos que demostrar que la segunda operación conserva la regularidad. La forma de hacerlo es con un transductor de estado finito trabajando en de derecha a izquierda. Ese es el paso más difícil. Sugiero hacerlo con un programa de pseudocódigo y un poco de memoria auxiliar finita (como algunas variables de bit) en lugar de usar estados. Siempre que la memoria tenga un tamaño fijo en todas las entradas y escanee estrictamente de derecha a izquierda, es una transducción de estado finito y conserva la regularidad.$\bar x$

Finalmente, para obtener de necesitamos agregar numéricamente a cada cadena, pero eso se hace con un transductor similar que depende del número fijo b. M a , 0 b T $M_{a,b}$$M_{a,0}$$b$$T_b$

Para hacer lo mismo en cualquier base, muestre adicionalmente cómo realizar la multiplicación por un solo dígito en esa base, utilizando un transductor que depende de d. Con eso, podemos multiplicar por números de varios dígitos y aún permanecer en los idiomas regulares. O bien, podemos precisar esto diciendo que la multiplicación por es una suma repetida.S d$d$$S_d$$d$

Solo querías pistas. Cada uno de esos pasos depende de un teorema / técnica bastante complejo, por lo que probarlos para obtener una prueba completa será un trabajo adicional.

Sugerencia n. ° 1 : primero resuelva el problema más popular "escriba un autómata que reconozca las representaciones decimales / binarias de los números divisibles por 3" cuando el bit menos significativo aparezca primero.

Pregunta intermedia: pruebe que es regular.$\{ \overline{a\,x+b}\mid a\,x+b≥0 \quad x\in\mathbb{Z}\}$

Sugerencia n. ° 2 : El gráfico de la función "módulo " es finito. Puede calcularlo para cada en que es tanto el conjunto de dígitos como el idioma de su autómata.a d { 0 , … , 9 $(n \mapsto 10n+d)$$a$$d$$\{0, \dots, 9\}$

Consejo # 3 : Ahora, reemplace con . ¿Qué cambia esto? Intente utilizar el hecho de que los lenguajes regulares son estables por intersección en lugar de construir un autómata ad-hoc . x ∈ $x∈\mathbb Z$$x∈\mathbb N$

Sugerencia n. ° 4 : ahora suponga que es un número primo (de modo que es un campo) y que todavía estamos en el caso dondeZ / a Z x ∈ $a$$\mathbb Z/a\mathbb Z$$x∈\mathbb Z$ . Ahora usamos una representación donde el primer bit es el bit más significativo . ¿Puedes construir el autómata de la misma manera?

Pista # 5 : no siempre tienes que construir un autómata para probar que un idioma es regular. ¿Cómo puedes usar los resultados anteriores para demostrar que es regular? (con el bit más significativo primero)$M$

Estoy siguiendo la idea de @vonbrand:

Pista 1:

Resuelve primero para . Puedes usar el Teorema de Myhill-Nerode .$b=0$

Definimos la siguiente relación . Obviamente, esta es una relación de equivalencia. Además, es congruente a la derecha, ya que si agregamos un dígito d obtenemos ˉ x ≈ ˉ $\bar x\approx \bar y :\iff x\equiv y \mod a$$d$. Finalmente saturaL, ya queLes la clase de equivalencia[0]. Como≈tiene un número finito de clases, según el Teorema de Myhill-Nerode, es regular. La FSA asociado es mínimo y tieneunosestados.$\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$

Pista 2:

Resuelva el caso general, reutilice el autómata inducido por el caso .$b=0$

Sabemos que el lenguaje es regular para . Por lo tanto simplemente tomar el un estado FSA M para el b = 0 idioma. Ahora construimos un FSA para L . Suponga que b tiene k dígitos. Luego, la FSA se ramifica como un árbol de profundidad k de 10 arios y contiene todos los caminos a los números con k dígitos. Todos los estados a los que se puede llegar con un número que no está en la forma a x + b están rechazando o aceptando. Finalmente conectamos la parte del árbol de la FSA con el autómata $b=0$$a$$M$$b=0$$L$$b$$k$$k$$k$$ax+b$$M$, según el resto por la división por .$a$

El lenguaje es regular.

Sugerencia: expulsar nueves

Idea de prueba

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

construir un autómata con estados etiquetados de 0 a 8 . 0 es el estado inicial, y el último estado es b . Desde el estado s , en el dígito d , transición al estado ( s + d $9$$0$$8$$0$$b$$s$$d$ .$(s + d) \;\mathrm{mod}\; 9$

Para manejar otros valores de que son coprimos con 10 ,$a$$10$

agrupe los dígitos en paquetes para encontrar algo de modo que a divida 10 k - 1 (por ejemplo, tome k = 3 si a = 37 porque 999 = 27 × 37 ).$k$$a$$10^k-1$$k=3$$a=37$$999 = 27 \times 37$

Para manejar valores de cuyos únicos factores primos son 2 y 5 ,$a$$2$$5$

tenga en cuenta que se trata de un número finito de dígitos al final.

Para generalizar a todos los valores de y b ,$a$$b$

use el hecho de que la unión y la intersección de los lenguajes regulares son regulares, que los lenguajes finitos son regulares y que los múltiplos de son exactamente los múltiplos de ambos cuando un 1 y un 2 son coprimos.$a_1 \cdot a_2$$a_1$$a_2$

Tenga en cuenta que utilizamos la técnica que sea conveniente; Las tres técnicas elementales principales (expresiones regulares, autómatas finitos, propiedades de teoría de conjuntos) están representadas en esta demostración.

Prueba detallada

Sea con un ′ coprimo con 10 . Deje M ′ = { ¯ a $a = 2^p 5^q a'$$a'$$10$ y M ″ = { ¯ 2 p 5 $M' = \{\overline{a'\,x+b} \mid x\in\mathbb{Z} \wedge a'\,x+b \ge 0\}$ . Por aritmética elemental, los números iguales a b módulo a son exactamente los números iguales a b módulo a ′ y a b módulo 2 p 5 q , entonces M ∩ { ¯ x ∣ x ≥ b } = M ′ ∩ M ″ ∩ { ¯ x ∣ x ≥ b } . Dado que la intersección de los idiomas regulares es regular, y$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\}$ es regular porque es el complemento de un lenguaje finito (por lo tanto, regular), si M ′ y M ″ también son regulares, entonces M ∩ { ¯ x ∣ x ≥ b } es regular; y M es, por lo tanto, regular ya que es la unión de ese lenguaje con un conjunto finito. Por lo tanto, para concluir la prueba, es suficiente demostrar que M ' y M ″ son regulares.$\{\overline{x} \mid x \ge b\}$$M'$$M''$$M \cap \{\overline{x} \mid x \ge b\}$$M$$M'$$M''$

Comencemos con , es decir, números módulo 2 p 5 q . Los enteros cuya decimal expansión está en M " se caracterizan por su último m un x ( p , q ) dígitos, ya que el cambio dígitos además medios que dejan la adición de un múltiplo de 10 m una x ( p , q ) que es un múltiplo de 2 p 5 q . Por lo tanto, 0 ∗ M ″ = ℵ ∗ F donde$M''$$2^p 5^q$$M''$$\mathrm{max}(p,q)$$10^{\mathrm{max}(p,q)}$$2^p 5^q$$0^* M'' = \aleph^* F$ es el alfabeto de todos los dígitos y F es un conjunto finito de palabras de longitud m a x ( p , q ) , y M ″ = ( ℵ ∗ F ) ∩ ( ( ℵ ∖ { 0 } ) ℵ ∗ ) es un idioma.$\aleph$$F$$\mathrm{max}(p,q)$$M'' = (\aleph^* F) \cap ((\aleph \setminus \{0\}) \aleph^*)$

Ahora pasamos a , es decir, los números del módulo a ′ donde a ′ es coprimo con 10 . Si a ′ = 1, entonces M ′ es el conjunto de expansiones decimales de todos los naturales, es decir, M ′ = { 0 } ∪ ( ( ℵ ∖ { 0 } ) ℵ ∗ ) , que es un lenguaje normal. Imaginemos ahora un ' > 1 . Deje k = a ′$M'$$a'$$a'$$10$$a' = 1$$M'$$M' = \{0\} \cup ((\aleph \setminus \{0\}) \aleph^*)$$a' > 1$ . Según el pequeño teorema de Fermat, 10 a ′ - 1 ≡ $k = a'-1$ , lo que significa que a ′ divide 10 k - 1 . Construimos un autómata finito determinista que reconocerá 0 ∗ M ′ de la siguiente manera:$10^{a'-1} \equiv 1 \mod a'$$a'$$10^k-1$$0^* M'$

• Los estados son . La primera parte representa una posición de dígitos y la segunda parte representa un módulo de número 10 k - 1 .$[0,k-1] \times [0,10^k-2]$$10^k-1$
• El estado inicial es .$(0,0)$
• Hay una transición etiquetada de ( i , u ) a ( j , v ) iff v ≡ d 10 i + $d$$(i,u)$$(j,v)$ y j ≡ i + $v \equiv d 10^i + u \mod 10^k-1$ .$j \equiv i + 1 \mod k$
• Un estado es final si u ≡ $(i,u)$ (tenga en cuenta que a ′ divide 10 k - 1 ).$u \equiv b \mod a'$$a'$$10^k-1$

El estado alcanzado desde una palabra ¯ x satisface i ≡ | ¯ x$(i,u)$$\overline{x}$ y u ≡ $i \equiv |\overline{x}| \mod k$ . Esto se puede probar por inducción sobre la palabra, siguiendo las transiciones en el autómata; las transiciones se calculan para esto, usando el hecho de que 10 k ≡ $u \equiv x \mod 10^k-1$ . Así, el autómata reconoce las expansiones decimales (permitiendo ceros iniciales) de los números de la forma u + y 10 k con u ≡ $10^k \equiv 1 \mod 10^k-1$$u + y 10^k$ ; desde 10 k ≡ $u \equiv b \mod a'$ , el autómata reconoce las expansiones decimales de los números iguales a b módulo a ′ permitiendo ceros iniciales, que es 0 ∗ M ′ . Este lenguaje se demuestra así regular. Finalmente, M ′ = ( 0 ∗ M ′ ) ∩ ( ( ℵ ∖ { 0 } ) ℵ ∗ ) es un lenguaje regular.$10^k \equiv 1 \mod a'$$b$$a'$$0^* M'$$M' = (0^* M') \cap ((\aleph \setminus \{0\}) \aleph^*)$

Para generalizar a bases distintas de , reemplace 2 y 5 anteriores por todos los factores primos de la base.$10$$2$$5$

Prueba formal

Dejado como ejercicio para el lector, en su probador de teoremas favorito.