Autómata finito no determinista (NFA)
- ? Alfabeto de entrada del autómata.
- Q es el conjunto de los estados del autómata.
- q0 es el estado inicial o de arranque del autómata (q0?Q)
- F?Q es el conjunto de estados finales o de aceptación del autómata
- ? es una relación:
?: Q x (? U {?}) ? ?(Q)
(q, ?) ? {q1, q2, ..., qN}
? asocia a un par (q, ?) (estado y símbolo de entrada) un conjunto de estados (el conjunto de estados a los que puede transitar el autómata)