Probar que el siguiente lenguaje NO es regular: El conjunto de las cadenas de ceros y unos que comienzan con un 1 tales que, interpretadas como un número entero, dicho entero sea primo.
R: Estamos hablando de secuencias como las siguientes:
1
11
101
111
1101
1111
1011
1001
..
Es decir, las descritas por las expresión regular 1+1(0+1)^*1. El uno al final se impone para que el número sea primo (de lo contrario sería divisible por 10, si es entero decimal o por 2 si es entero binario. Suponemos en lo que sigue que hablamos de enteros decimales).
1) Sea L el lenguaje descrito por esa expresión regular.
2) Sea n tal que |w| = n.
1) Sea w = 11^(m)1, con 1 < m < n.
2) Sea x=1, y=1^m, z=1. Claramente, y no es vacía y |xy| < n.
1) Con k = 1 y m = 1, w = 111, pero el ciento once no es un número primo. Es divisible por 3. Es decir, no pertenece al lenguaje!. LQQD.
Se podrán encontrar otros casos que sirvan a la prueba, con m>1? (recuerde aquella regla para los múltiplos de 3: :Un número es múltiplo de 3 si la suma de sus cifras es 3 o un múltiplo de 3.).
0 comentarios:
Publicar un comentario