Tengo dificultades con una pregunta aparentemente sencilla. "¿Es posible tener una máquina de estados finitos que detecte si una cadena de bits de longitud arbitraria tiene el mismo número de ceros que de unos? Si es así, ¿qué aspecto tendría? Al tratar de resolver este problema, se me han ocurrido varias máquinas de estado finito. Sin embargo, ninguna ha sido capaz de resolver el problema para una cadena de bits de longitud arbitraria.
¿Alguna sugerencia? Gracias.
El número de $1$ en la primera $n$ bits de entrada puede ser cualquier número entero de $0$ a $n$ y si hay al menos $n$ más bits, para determinar el resultado el FSM necesitaría "recordar" cuál de esos enteros es. Por lo tanto, al menos $n+1$ estados son necesarios para un FSM que pueda hacer esto con $2n$ -de bits. Dado que el tamaño de la cadena de entrada es arbitrario, no es posible un FSM de este tipo.
Esto es claramente posible con las máquinas de Turing, así que permítame suponer que está utilizando autómatas de estado finito.
En este caso, no es posible. La razón es el lema de bombeo . Considere las cadenas $0^n1^n$ , donde $n$ es mayor que el número de estados de la máquina. Esta cadena debe ser aceptada por la máquina, por lo que puede ser bombeada. Pero según el lema de bombeo, el efecto del bombeo será la inserción de $0$ s en la cadena, haciéndola desequilibrada con respecto al criterio, pero aún así aceptada por la máquina. Así que la máquina no funciona como se sugiere. Por tanto, no hay ningún autómata de estado finito que acepte todas y sólo las cadenas equilibradas.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
