Autómata completo
En la definición básica de autómata finito no es necesario que desde todos los estados exista una transición para todos los símbolos. Un autómata completo es un autómata que tiene definidas las transiciones desde todos los estados para todos los símbolos del alfabeto de entrada.
Cómo construir un autómata completo
Tomemos este autómata A = ⟨Q, Σ, δ, q0, F⟩:
Aquí no está dibujada la transición desde el estado q0 para la letra «b». Si se diera esa situación, diríamos que el autómata no acepta la palabra de entrada. Sin embargo, desde el punto de vista de la formalización puede no ser conveniente que la función de transición δ no esté definida para algunos valores; aquí, por ejemplo, no está definida para δ(q0, b).
Esto se resuelve fácilmente construyendo un autómata equivalente que tenga un estado más: hacia este estado apuntarán las transiciones «que faltan», este estado no será final y todas las entradas siguientes se quedarán dando vueltas en él. A este autómata lo llamaremos autómata completo. El autómata equivalente modificado podría quedar así:
Hemos añadido el estado qfail. Desde los demás estados hemos trazado una transición hacia él si y solo si antes no existía allí ninguna transición. Este estado no es final y se queda en bucle para todas las entradas siguientes. Así, si en el autómata anterior nos topábamos con una transición que faltaba, aquí no falta ninguna transición y el autómata llegaría al estado qfail.
Por tanto, siempre podemos suponer, sin pérdida de generalidad, que el autómata tiene definidas las transiciones para todas las combinaciones de estados y símbolos del alfabeto.
Definición
Para un autómata completo A = ⟨Q, Σ, δ, q0, F⟩ se cumple, por tanto, que
Fuentes
Capítulos: Autómata finito, Autómata completo, Autómata finito no determinista, Simulación de un autómata finito no determinista, Conversión de un AFND en un AFD
