Sugerencia: Supongamos que el autómata A tiene N estados. Elija un entero m tal que (m 1)2 ฀ m2 N. Considere cadenas de a de longitud entre m2 y ...

Sugerencia: Supongamos que el autómata A tiene N estados. Elija un entero m tal que (m 1)2 ฀ m2 N. Considere cadenas de a de longitud entre m2 y (m 1)2. Ya que hay más cadenas que estados, al menos dos cadenas deben enviar A al mismo estado si: m 1 2 aa aaa aaa aaa a m2 Después de ambas de estas entradas, A está en el estado si Se tiene (eliminando las a que se muestren en color) que el autómata debe aceptar una cadena de forma a k, donde m2 k (m 1)2.

a. 0, clases de equivalencia: {s0, s1, s2}, {s3, s4, s5}
b. 1