En la teoría de la computación , un autómata finito no determinista generalizado ( GNFA ), también conocido como autómata de expresión o máquina de estados finitos no determinista generalizada , es una variación de un autómata finito no determinista (NFA) donde cada transición está etiquetada con cualquier expresión regular . El GNFA lee bloques de símbolos de la entrada que constituyen una cadena según lo definido por la expresión regular en la transición. Existen varias diferencias entre una máquina de estados finitos estándar y una máquina de estados finitos no determinista generalizada. Un GNFA debe tener solo un estado de inicio y un estado de aceptación, y estos no pueden ser el mismo estado, mientras que un NFA o DFA pueden tener varios estados de aceptación, y el estado de inicio puede ser un estado de aceptación. Un GNFA debe tener solo una transición entre dos estados, mientras que un NFA o DFA permiten numerosas transiciones entre estados. En un GNFA, un estado tiene una única transición a cada estado de la máquina, aunque a menudo es una convención ignorar las transiciones que están etiquetadas con el conjunto vacío cuando se dibujan máquinas de estados finitos no deterministas generalizadas.
Un GNFA se puede definir como una 5-tupla , ( S , Σ, T , s , a ), que consta de
donde R es la colección de todas las expresiones regulares sobre el alfabeto Σ.
La función de transición toma como argumento un par de dos estados y genera una expresión regular (la etiqueta de la transición). Esto difiere de otras máquinas de estados finitos, que toman como entrada un solo estado y una entrada del alfabeto (o la cadena vacía en el caso de máquinas de estados finitos no deterministas) y generan el siguiente estado (o el conjunto de estados posibles en el caso de máquinas de estados finitos no deterministas). Un DFA o NFA se puede convertir fácilmente en un GNFA y luego el GNFA se puede convertir fácilmente en una expresión regular colapsando repetidamente partes de él en aristas simples hasta que S = { s , a }. De manera similar, los GNFA se pueden reducir a NFA cambiando los operadores de expresión regular en nuevas aristas hasta que cada arista esté etiquetada con una expresión regular que coincida con una sola cadena de longitud como máximo 1. Los NFA, a su vez, se pueden reducir a DFA utilizando la construcción de conjunto de potencias . Esto muestra que los GNFA reconocen el mismo conjunto de lenguajes formales que los DFA y NFA.
