En la teoría del cómputo, un autómata finito no determinista generalizado o el autómata finito no determinista generalizado (GNFA) es un NFA donde cada transición se puede etiquetar con cualquier expresión regular . El GNFA lee bloques de símbolos de la entrada que constituyan una secuencia según lo definido por la expresión regular en la transición.

Definición formal

Un GNFA se puede definir como tuple 5, (el S, Σ, T, s, un ), consistiendo en el
un sistema finito de los estados ( S );
un sistema finito llamado el alfabeto (Σ);
una función ( T de la transición: ( S - { un }) × ( S - { s }) R del →);
un estado del comienzo ( S del ∈ del s );
un estado del aceptado ( un S del ∈ de ); donde está la colección el R de todas las expresiones regulares sobre el alfabeto Σ.

Un DFA o el NFA se puede convertir fácilmente en un GNFA y entonces el GNFA se puede convertir fácilmente en una expresión regular por las partes en varias ocasiones que se derrumban de él para escoger los bordes hasta el S = {el s, un }. Semejantemente, GNFAs se puede reducir a NFAs cambiando a operadores de la expresión regular en los nuevos bordes hasta que cada borde se etiquete con una expresión regular que empareja una sola secuencia de la longitud a lo más que 1. NFAs, alternadamente, se pueden reducir a DFAs usar la construcción de Powerset. Esto demuestra que GNFAs reconoce el mismo sistema de los lenguajes formales como DFAs y NFAs.