Automatas finitos deterministico

INFORMATICA UNIVERSIDAD

INTRODUCCIÓN

Un autómata finito determinista (abreviado AFD) es un autómata finito que además es un sistema determinista; es decir, para cada estado en que se encuentre el autómata, y con cualquier símbolo del alfabeto leído, existe siempre a lo más una transición posible desde ese estado y con ese símbolo

Definición formal

Formalmente, se define como una 5-tupla (Q, Σ, q0, δ, F) donde:

En un AFD no pueden darse ninguno de estos dos casos:

  • Que existan dos transiciones del tipo δ(q,a)=q1 y δ(q,a)=q2, siendo q1q2;
  • Que existan transiciones del tipo δ(q, ε), donde ε es la cadena vacía, salvo que q sea un estado final, sin transiciones hacia otros estados.

(Puede quitar la publicidad ampliando la cuenta)