Autômato finito não determinístico generalizado - Generalized nondeterministic finite automaton

Na teoria da computação , um autômato finito não determinístico generalizado ( GNFA ), também conhecido como um autômato de expressão ou uma máquina de estado finito não determinístico generalizado , é uma variação de um autômato finito não determinístico (NFA), onde cada transição é rotulada com qualquer expressão regular . O GNFA lê blocos de símbolos da entrada que constituem uma string conforme definido pela expressão regular na transição. Existem várias diferenças entre uma máquina de estado finito padrão e uma máquina de estado finito não determinística generalizada. Um GNFA deve ter apenas um estado inicial e um estado de aceitação, e estes não podem ser o mesmo estado, enquanto um NFA ou DFA podem ter vários estados de aceitação, e o estado inicial pode ser um estado de aceitação. Um GNFA deve ter apenas uma transição entre dois estados, enquanto um NFA ou DFA permitem várias transições entre estados. Em um GNFA, um estado tem uma única transição para cada estado na máquina, embora muitas vezes seja uma convenção ignorar as transições que são rotuladas com o conjunto vazio ao desenhar máquinas de estados finitos não determinísticos generalizados.

Definição formal

Um GNFA pode ser definido como um 5-tupla , ( S , Σ, T , s , a ), consistindo em

  • um conjunto finito de estados ( S );
  • um conjunto finito denominado alfabeto (Σ);
  • uma função de transição ( T  : ( S ∖ { a }) × ( S ∖ { s }) → R );
  • um estado inicial ( s ∈ S );
  • um estado de aceitação ( a ∈ S );

onde R é a coleção de todas as expressões regulares sobre o alfabeto Σ.

A função de transição leva como argumento um par de dois estados e produz uma expressão regular (o rótulo da transição). Isso difere de outras máquinas de estados finitos, que tomam como entrada um único estado e uma entrada do alfabeto (ou a string vazia no caso de máquinas de estados finitos não determinísticos) e produzem o próximo estado (ou o conjunto de estados possíveis no caso de máquinas de estados finitos não determinísticos). Um DFA ou NFA pode ser facilmente convertido em GNFA e, em seguida, o GNFA pode ser facilmente convertido em uma expressão regular , recolhendo repetidamente partes dele em bordas únicas até S = { s , a }. Da mesma forma, GNFAs podem ser reduzidos a NFAs mudando operadores de expressão regular em novas arestas até que cada aresta seja rotulada com uma expressão regular correspondendo a uma única string de comprimento no máximo 1. NFAs, por sua vez, podem ser reduzidos a DFAs usando a construção de conjunto de poderes . Isso mostra que os GNFAs reconhecem o mesmo conjunto de linguagens formais que os DFAs e NFAs.

Referências

links externos

  • Uma descrição gráfica dos GNFAs e do processo de conversão de um NFA em uma expressão regular usando GNFAs pode ser encontrada em [1]