Non deterministic Finite Automata

Formalmente se define como una quintupla, (S, Σ, T, s, A), que consiste en:

• Un conjunto finito de estados (S)
• Un conjunto finito llamado alfabeto (Σ)
• Una función de transición T : S × Σ → P(S).
• Un estado perteneciente a S llamdo estado inicial (s ∈ S).
• Un conjunto de estados terminales o de aceptación A.

Esto es muy parecido a la definición de DFA, la relación entre DFA y NFA puede ser mejor comprendida por la siguiente frase "cada automata determinista es uno no determinista." La función de transición especifica una sola transición por cada combinación entre estado y entrada, en un NFA permite cero, una o más transiciones lo cual lo hace ser más sencillo de expresar.

En los apuntes de DFA teniamos un automata "que acepta la cadenas pertenecientes al lenguaje conformado por el alfabeto Σ={A,B,C,D,E} y que termine por ABC", este mismo puede ser representado más sencillo mediante el NFA:

M: La quintupla se define de la siguiente manera,
Q={q0, q1, q2, q3}
Σ={A, B, C, D, E}
s={q0}
F={q3}

T(q0, A)={q0, q1}
T(q0, {B, C, D, E})=q0
T(q1, B)=q2
T(q2, C)=q3