Autômato finito não determinístico generalizado

O autômato finito não determinístico generalizado, abreviado AFNG, é um autômato não determinístico que, nas transições, não precisa ter apenas símbolos do alfabeto, mas pode ter ali uma expressão regular.

Definição

Vamos precisar do AFNG durante o algoritmo de conversão de um autômato finito em uma expressão regular. O AFNG é, assim, um AFN que tem transições definidas por expressões regulares. Exemplo de um AFNG desse tipo:

Vemos que, por exemplo, do estado q₂ sai uma transição para o estado q_f, rotulada com a expressão regular a^∗ b. Outros requisitos para o AFNG:

• O estado inicial q₀ deve ter transição para todos os outros estados. Na figura vemos que do estado q₀ saem transições para todos os outros estados.
• No AFNG existe apenas um estado final, e todos os outros estados têm transição para esse estado. Como se vê na figura, todos os estados têm uma seta apontando para q_f.
• O estado inicial não pode coincidir com o estado final. O AFNG pode ter, assim, no mínimo dois estados.
• Todos os outros estados, exceto o inicial e o final, devem ter transições para todos os outros estados, exceto o inicial e o final. Inclusive laços (transição do estado q_i para o estado q_i).

Conversão de um AFN comum em AFNG

Se temos algum AFN, a conversão em AFNG é simples.

1. Criamos um novo estado inicial q_s e criamos uma transição ε para o estado inicial original.
2. Criamos um novo estado final q_f e de todos os estados finais originais levamos transições ε para o estado q_f. Transformamos os estados finais originais em estados normais.
3. Se em algum lugar existe uma transição múltipla (isto é, se do estado q₁ chegamos ao estado q₂ tanto pelo símbolo 0 quanto pelo símbolo 1), então reunimos essas regras em uma única expressão regular e juntamos todos os símbolos originais com o operador de união (isto é, rotulamos a seta com a expressão regular 0|1).
4. Se no autômato falta alguma transição que, pela definição, deveria estar ali, criamos essa transição e a rotulamos com a expressão regular ∅. Com isso não mudamos a linguagem que o autômato aceita, porque uma transição assim nunca é executada.

Podemos usar esse autômato para a conversão de um autômato em expressão regular.