En los AFD sabemos exactamente cuál es la transición que debemos llevar a cabo ante una determinada situación. Sin embargo, en los no deterministas podemos encontrarnos con varias opciones e, incluso, con λ-transiciones que se realizan sin considerar el correspondiente símbolo de la cadena de entrada. Para tener en cuenta estas consideraciones, los AFND se definen como una tupla:
AFND = (Σ, Q, f, q0, F, T), f: Q × Σ → 2Q donde
2Q es el conjunto formado por los subconjuntos de Q, incluyendo a Ø
T es una relación binaria definida sobre Q que indica las λ-transiciones del autómata (si pTq ⇒ existe una λ-transición desde p hasta q)
El resto de los símbolos tiene el mismo significado que en la definición de AFD.