En una máquina finita determinista, su entrada es una palabra, como abbaaabb. El autómata funciona según las reglas (una función) que le dice que transista de un estado a otro según el carácter actual de la entrada.
El autómata siempre comienza desde el estado s, que se denomina “estado inicial” y realiza tantas transiciones como letras en la palabra, por lo tanto, el número de transiciones depende de la entrada.
Después de las transiciones de longitud (w), la palabra se procesa completamente y el autómata se detiene . Si el estado en el que se detiene es un estado final , entonces el autómata acepta la palabra. De lo contrario, lo rechaza .
Una máquina puede tener tantos estados de aceptación como sea necesario para aceptar todas las palabras necesarias. Por ejemplo, si desea aceptar una palabra que coincida con la descripción “Al menos cinco ‘a’s y termina en’ b ‘o solo cuatro’ b’s ‘, entonces necesita dos estados finales, uno para cada caso.
El nombre “final” es engañoso: no obliga al autómata a detenerse una vez que se ha alcanzado. Prefiero llamarlos estados “aceptar”, porque acepta la palabra si y solo si se detiene en uno.
- ¿Hay alguna manera de tener un archivo 7-zip inicial y tener versiones similares almacenadas como 'lo que ha cambiado'?
- ¿Existe un MOOC gratuito para aprender A +, seguridad de red u otros cursos necesarios para certificaciones informáticas comunes?
- ¿Cuál es la diferencia entre una maestría en informática (MS) y una maestría en aplicaciones informáticas (MCA)? Este año busqué una Licenciatura en Aplicación de Computadoras (BCA), ¿qué título debo elegir ahora?
- ¿Por qué + y + = se comportan de manera diferente para las listas de Python?
- ¿Qué tan bueno es Ingeniería Física, especialmente en IIT Hyderabad?
Piense en ello como una máquina expendedora: el cliente ingresa una cantidad de monedas. Después de cada moneda, la máquina expendedora transita a un estado diferente. Acepta la solicitud (“dame una lata de refresco”) si la cantidad de monedas es suficiente para que llegue a un estado final .
Obtenga una copia de Lewis-Papademetriou para un análisis asombroso de autómatas y otros temas sobre la teoría de la computación
