Tenemos una máquina que tiene una entrada y una salida. La entrada es una letra del conjunto finito $I$ y la salida es una lámpara que en cada momento tiene uno de los colores del conjunto $C=\{c_1,\dots,c_p\}$ . En cada momento la máquina tiene un estado interno que es uno de los $n$ miembros del conjunto finito $S$ . La función $o: S \rightarrow C$ es una función sobreyectiva que define que en cada estado, qué color debe tener la lámpara, y la función $t:S \times I \rightarrow S$ es una función que define cómo el dar cada entrada en cada estado cambia el estado. Solo veremos la lámpara y no tenemos información directa del estado del coche en el momento actual. En otras palabras, una máquina es $M=(S,I,C,o,t)$ tal que $S,I,C$ son finitos, $t:S \times I \rightarrow S$ , y $o:S \rightarrow C$ es sobreyectiva. Se garantiza que para cada dos estados internos diferentes, hay una secuencia de entradas tal que el color de la lámpara después de dar la secuencia a la máquina en el primer estado es diferente del color de la lámpara después de dar la secuencia a la máquina en el segundo estado. (a) La máquina $M$ tiene $n$ estados internos diferentes. Demuestre que para cada dos estados internos diferentes, hay una secuencia de entradas de longitud no mayor que $n-p$ tal que el color de la lámpara después de dar la secuencia a la máquina en el primer estado es diferente del color de la lámpara después de dar la secuencia a la máquina en el segundo estado. (b) Demuestre que para una máquina $M$ con $n$ estados internos diferentes, existe un algoritmo con no más de $n^2$ entradas que, comenzando en cualquier estado interno desconocido, al final del algoritmo el estado de la máquina en ese momento se conoce. ¿Puede demostrar la afirmación anterior para $\frac{n^2}{2}$ ?