Autómatas finitos deterministas

Un alfabeto Σ es un conjunto finito de símbolos. Una palabra es una lista finita ordenada de ellos. Σ* reúne todas esas palabras, incluida ε, la palabra vacía. Un lenguaje L es cualquier subconjunto de Σ*.

Un DFA se describe por (Q,Σ,δ,q₀,F): estados finitos no vacíos, alfabeto, transición, inicio y estados aceptantes. La función total δ:Q×Σ→Q asigna exactamente un destino a cada estado y símbolo. No dispone de una memoria que crezca con la entrada.

Empezamos en q₀. Consumimos el primer símbolo, seguimos su transición y repetimos hasta agotar la entrada. Solo entonces miramos si el estado está en F.

La palabra vacía no hace ningún movimiento: se acepta exactamente cuando q₀∈F.

Para contar la paridad de unos basta recordar si hemos visto una cantidad par o impar. P representa par; I, impar. No necesitamos almacenar el número exacto.

Cero no cambia ese número y deja el estado. Uno aumenta la cantidad en uno y cambia par por impar o al revés. P es inicial porque cero unos es par; también es el único aceptante.

El invariante es: después de cualquier prefijo, el estado representa la paridad de sus unos. Se cumple en ε porque la cantidad inicial es cero.

Si se añade cero, no cambia la paridad ni el estado. Si se añade uno, cambian ambas. La inducción sobre la longitud prueba el invariante para todos los prefijos y, al terminar, aceptación equivale a la propiedad pedida.

En un DFA completo, q estados y a símbolos requieren q·a parejas definidas. Una flecha puede llevar varias etiquetas y representar varias parejas; no se cuentan solo flechas dibujadas.

Para completar una tabla parcial añadimos un sumidero no aceptante. Todo paso ausente llega a él y cada símbolo lo mantiene allí. Así el rechazo no depende de desaparecer de la ejecución.

Un NFA puede ofrecer varias transiciones y movimientos ε que no consumen símbolos. Acepta una palabra si existe una ejecución completa aceptante; no hace falta que todas acepten.

El DFA equivalente recuerda un subconjunto de estados posibles. Parte del cierre ε del inicial, avanza cada posibilidad con el símbolo y vuelve a cerrar por ε. Acepta si el subconjunto contiene algún aceptante. Con q estados hay como máximo 2ᑫ subconjuntos, incluido el vacío.

Para dos DFA del mismo alfabeto usamos estados pareja y actualizamos ambas coordenadas con cada símbolo. Si aceptamos cuando ambas aceptan, reconocemos intersección; si basta una, unión.

Para complemento intercambiamos aceptantes y no aceptantes de un DFA completo. Si había transiciones ausentes, primero se completa: una palabra sin ejecución no se vuelve aceptada solo por cambiar círculos.

Dos estados son equivalentes si toda continuación produce la misma respuesta final desde ambos. Si un sufijo acepta desde uno y rechaza desde el otro, no se pueden fusionar.

Para minimizar, quitamos estados inaccesibles y refinamos clases empezando por aceptantes y no aceptantes. Separamos quienes tienen alguna transición hacia clases diferentes y repetimos hasta estabilizar. El cociente resultante es mínimo, salvo renombrado de estados.

Los lenguajes de estos autómatas son regulares, equivalentes a las expresiones regulares matemáticas de unión, concatenación y estrella. Un DFA fijo consume una transición por símbolo: tiempo proporcional a la longitud y memoria de estado constante.

Puede recordar restos de una cuenta, como paridad, pero no un contador arbitrario escondido en sus estados. Comparar dos bloques de longitud igual sin límite, 0ⁿ1ⁿ, no es regular; bombeo y continuaciones lo prueban formalmente.