No puedes, como otros han señalado. Como justificación, algunos han hecho referencia al Lema de bombeo para los idiomas normales (sin más elaboración), que de hecho se puede utilizar para demostrar esta imposibilidad, pero permítanme dar otra explicación que se basa en el Teorema de Myhill-Nerode, que encuentro un mejor manera de demostrar la no regularidad.
Suponga que tiene una máquina de estado finito y está leyendo una cadena para determinar si acepta o no. Entonces estás sentado en algún estado y estás a punto de leer el resto de la cadena. En este punto, no importa qué camino tomaste a través de la máquina para llegar a donde estás ahora; todo lo que importa es a dónde vas después de leer las letras restantes de la cadena. Dicho de otra manera, supongamos que, después de leer las dos cadenas [matemáticas] u [/ matemáticas] y [matemáticas] v [/ matemáticas], terminas en el mismo estado. Entonces debería ser obvio que, para cualquier cadena [math] w [/ math], también terminarás en el mismo estado después de leer cada una de las concatenaciones [math] uw [/ math] y [math] vw [/ math ] En particular, no hay forma de que estés en un estado final después de leer [math] uw [/ math] y un estado no final después de leer [math] vw [/ math], o viceversa, ya que estos deben ser El mismo estado.
Ahora, supongamos que tenemos una máquina de estado finito que acepta exactamente su idioma: cadenas con números iguales de 0s y 1s. Pregúntese: ¿en qué estado estará después de leer cada una de las cadenas 0, 00, 000, 0000, y así sucesivamente? Afirmo que cada uno de estos estados debe ser diferente. Por ejemplo, considere 00 y 0000. Si los estados en los que se encontraba después de leer estas dos cadenas eran los mismos, entonces, como se explicó anteriormente, aún estaría en el mismo estado después de leer 00 [math] w [/ math] y 0000 [math] w [/ math], para cualquier cadena [math] w [/ math]. Pero, ¿qué pasa con [matemáticas] w [/ matemáticas] = 11? Después de leer 0011, debe estar en un estado final, porque esta cadena tiene el mismo número de 0s y 1s. Pero después de leer 000011, debe estar en un estado no final, porque esta cadena no tiene el mismo número de 0s y 1s. ¡Por lo tanto, no puedes estar en el mismo estado!
- ¿Por qué uno usaría máquinas de Turing Multi-cinta?
- ¿Será Econometrics o Machine Learning más importante en el futuro?
- ¿La inteligencia artificial es fácil para una persona que no es de TI?
- ¿Puedo encontrar la contraseña de un archivo comprimido si se conoce el contenido de los archivos incluidos?
- ¿Cuál es el significado del teorema de Kirchoff?
La conclusión es que, después de leer cada una de las diferentes cadenas 0, 00, 000, etc., debe estar en un estado diferente, lo que significa que su máquina no puede tener un número finito de estados. Es por eso que ninguna máquina de estado finito puede aceptar su idioma.
