Si

12

Digamos, L{0} . Entonces, ¿cómo podemos demostrar que L es regular?

Si L es regular, entonces, por supuesto, L también es regular. Si L es finito, entonces es regular y nuevamente L es regular. También he notado que, para L={0pp is a prime} , L no es regular, L{0} y L es regular.

Pero, ¿cómo mostrar esto para cualquier subconjunto L de {0} ?

ChesterX
fuente

Respuestas:

9

Supongamos que L contiene dos palabras w1 y w2 de tal manera que las longitudes de estas palabras, |w1|y |w2|, no tienen factores en común. Entonces, tenemos que la palabra más larga que no se puede formar concatenando estas palabras tiene longitud (|w1|1)(|w2|1)1 ( número de Frobenius) Es decir, si hay palabras en el idioma cuyas longitudes no tienen un factor común, entonces todas las palabras de cierta longitud mínima están en el idioma L . Es fácil ver que esto es regular ya que, necesariamente, hay un número finito de clases de equivalencia bajo la relación de indistinguibilidad de Myhill-Nerode.

¿Qué pasa si las longitudes de todas las palabras en comparten un factor común? Bueno, no es difícil ver que en tales casos, L también es regular. Simplemente tenga en cuenta que, en lugar de todas las palabras cuyas longitudes son mayores que una longitud mínima en L , será cierto que todas las palabras cuyas longitudes son múltiplos del MCD de longitudes de palabras estarán en L , y no hay palabras cuyas longitudes no son múltiplos de este GCD, y dado que ( L k ) es regular para cualquier entero k , L también es regular.LLLL(Lk)kL

Esto es bastante informal, pero todo lo que necesita para formalizar esto debería estar aquí.

Patrick87
fuente
4

wLLL˚wL˚L=L˚L˚L

Deje que sea un subconjunto de y una palabra en . puede expresarse como una concatenación de palabras en iffpuede ser expresada como una suma de elementos de , donde es el conjunto de longitudes de palabras en . Por lo tanto, el problema se reduce a expresar un número entero como una suma de números enteros en un conjunto particular (con repeticiones permitidas): canse expresará como con y ?MLwLwL|w|SNSM|w|k1s1++kmsmi,siSk1N

Este es un problema bien conocido en aritmética, y la respuesta es que si los coeficientes pueden ser negativos ( ),es expresable si y sólo si es un múltiplo del máximo común divisor de los elementos de : . Con un requerimiento de coeficientes no negativos, esto todavía es válido para.(ki)kiZ|w|SgcdS|w|

Considere la secuencia infinita definida por . Esta es una secuencia decreciente de enteros (comenzando con , por lo que es constante después de cierto índice ; y Según el teorema del resto chino, cada elemento de puede ser expresado como con y . Si y entonces puede elegir todos los coeficientes no negativos.(gi)iminSgi=gcd(S[0,i])gminS=minSjgj=gcdSSk1s1++kmsmi,kiZ{s1,,sm}=S[0,j]xSxs1sm

Suficiente aritmética. Deje . Cada palabra en puede expresarse como una concatenación de palabras en cuya longitud es como máximo , es decir, . Como también tenemos , tenemos , que es regular ya que es finito, por lo tanto, regular.L˚={wL|w|gj}LLgjLL˚L˚LL=L˚L˚


Alternativamente, use la caracterización de idiomas regulares en alfabetos de una letra .

Gilles 'SO- deja de ser malvado'
fuente