Automatas Finitos No Deterministas Ejercicios Resueltos

Un Autómata Finito No Determinista (AFND) es un modelo matemático que describe cómo un programa o máquina puede cambiar de estado al recibir una entrada. Piensa en él como un juego de seguir instrucciones.

¿Qué significa "No Determinista"?

La clave está en la palabra "No Determinista". Esto significa que, para una misma entrada y un mismo estado, el autómata puede tener más de una opción de a qué estado pasar. Es como estar en una bifurcación en el camino. No sabes con seguridad cuál camino tomarás.

Comparemos esto con un autómata determinista. En un autómata determinista, para cada estado y cada entrada, hay exactamente un siguiente estado posible. Es como un camino recto: no hay opciones.

Ejemplo sencillo: Imagina una puerta con dos cerraduras. Para abrirla, necesitas primero la llave 'A' y luego la llave 'B'. Un AFND podría modelar esto permitiendo que, al ingresar 'A', haya dos posibles estados: uno donde "recuerdas" que ya ingresaste 'A' y otro donde "olvidas". Si luego ingresas 'B' desde el estado correcto ("recuerdas A"), la puerta se abre. Si no, no.

Componentes de un AFND

Un AFND tiene cinco partes principales:

1. Conjunto de estados: Los diferentes "lugares" donde puede estar el autómata. En el ejemplo de la puerta, podríamos tener estados como: "Inicio", "Tengo A", "Puerta Abierta".
2. Alfabeto de entrada: Los símbolos que el autómata puede leer (como 'A' y 'B' en el ejemplo).
3. Función de transición: La regla que dice a dónde puedes ir desde un estado dado al leer un símbolo. Aquí es donde entra el no determinismo: puede haber múltiples destinos.
4. Estado inicial: Dónde empieza el autómata (por ejemplo, "Inicio").
5. Conjunto de estados de aceptación: Los estados que indican que el autómata ha "ganado" o completado su tarea (por ejemplo, "Puerta Abierta").

Ejercicios Resueltos (Ejemplo)

Problema: Diseña un AFND que acepte cualquier cadena que contenga la subcadena "ab".

Solución:

1. Estados: Q = {q0, q1, q2}
   • q0: Estado inicial. Aún no hemos visto "a".
   • q1: Hemos visto "a".
   • q2: Hemos visto "ab" (estado de aceptación).
2. Alfabeto: Σ = {a, b}
3. Función de transición:
   • δ(q0, a) = {q0, q1} (Podemos ignorar la 'a' o "recordarla").
   • δ(q0, b) = {q0} (Ignoramos la 'b').
   • δ(q1, a) = {q1} (Otra 'a' consecutiva).
   • δ(q1, b) = {q2} (Hemos visto "ab"!).
   • δ(q2, a) = {q2} (Seguimos en el estado de aceptación).
   • δ(q2, b) = {q2} (Seguimos en el estado de aceptación).
4. Estado inicial: q0
5. Estado de aceptación: F = {q2}

Explicación: El autómata comienza en q0. Si ve una 'a', puede quedarse en q0 (ignorándola) o pasar a q1 (recordándola). Si está en q1 y ve una 'b', pasa a q2 (estado de aceptación). Una vez en q2, cualquier entrada lo mantiene en q2, porque ya ha visto la subcadena "ab".

¿Por qué son útiles los AFND?

Aunque parecen más complicados que los autómatas deterministas, los AFND a menudo son más fáciles de diseñar para ciertos problemas. Además, cualquier AFND puede convertirse en un autómata determinista equivalente. Sirven como una herramienta poderosa para el diseño y análisis de lenguajes formales y compiladores.