Autômato finito não determinístico generalizado

Na Teoria da computação, um autômato finito não determinístico generalizado (AFNG), também conhecido como autômato de expressão ou máquina de estados finita não determinística generalizada é uma variação do AFN onde cada transição é rotulada por alguma expressão regular. O AFNG lê blocos de símbolos da entrada, os quais constituem uma cadeia definida pela expressão regular associada à transição. Existem diversas diferenças entre uma máquina de estados finita usual e uma máquina de estados finita não determinística generalizada. Um AFNG deve possuir apenas um estado inicial e um estado de aceitação, e estes não podem ser o mesmo estado, enquanto que AFNs ou AFDs podem ambos ter vários estados de aceitação, e o estado inicial pode ser de aceitação. Um AFNG deve possuir apenas uma transição entre quaisquer dois estados, enquanto que AFNs ou AFDs permitem ambos muitas transições entre estados. Em um AFNG, um estado possui uma única transição para cada um dos outros estados da máquina, embora frequentemente seja uma convenção ignorar as transições que são rotuladas com o conjunto vazio no desenho de máquinas de estados finitas não determinísticas generalizadas.

Definição formal

Um AFNG pode ser definido como uma 5-upla, (S, Σ, T, s, a), composta de

• um conjunto finito de estados (S);
• um conjunto finito chamado de 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 recebe como seu argumento um par de dois estados e retorna uma expressão regular (o rótulo da transição). Isto difere das funções de transição das outras máquinas de estado finito, que recebem como entrada um único estado e um símbolo do alfabeto (ou a cadeia vazia no caso de máquinas de estados finitos não determinísticas) e retornam o próximo estado (ou o conjunto de próximos estados no caso de máquinas de estados finitos não determinísticas). Um AFD ou AFN pode ser facilmente convertido num AFNG e em seguida o AFNG pode ser facilmente convertido em uma expressão regular através do repetido colapso de suas transições para uma única equivalente até que S = {s, a}. Similarmente, AFNGs podem ser reduzidos a AFNs através da transformação dos rótulos de expressões regulares em novas transições até que cada transição tenha como rótulo uma expressão regular que corresponde a uma única cadeia de tamanho no máximo igual a 1. AFNs, por sua vez, podem ser reduzidos a AFDs utilizando a construção do conjunto das partes. Isto demonstra que AFNGs reconhecem o mesmo conjunto de linguagens formais que AFDs e AFNs.

Um exemplo de AFNG

Conversão de AFNG para expressão regular

Seja G um AFNG com k estados. Então, como um AFNG deve ter um estado inicial, um estado de aceitação e eles devem ser diferentes um do outro, sabemos que k ≥ 2. Se k > 2, nós construimos um AFNG equivalente com k - 1 estados usando o procedimento CONVERT(G) descrito abaixo. Este passo pode ser repetido no novo AFNG até que esse seja reduzido a dois estados. Se k = 2, o AFNG tem uma única transição que vai do estado inicial para o estado de aceitação. O rótulo desta seta é a expressão regular equivalente.

CONVERT(G):

1. Seja k o número de estados de G:
2. Se k = 2, retorne a expressão regular que rotula a única seta que vai do estado inicial ao final.
3. Se k > 2, selecionamos qualquer estado $q_{sai}$ ∈ S, $q_{sai}$ ≠ $q_{inicio}$ e $q_{sai}$ ≠ $q_{aceita}$ e seja G′ o AFNG (S, Σ, T, $q_{inicio}$, $q_{aceita}$), onde S′ = S - {$q_{sai}$}, e para qualquer $q_{i}$ ∈ S - {$q_{aceita}$} e $q_{j}$ ∈ S - {$q_{inicio}$} seja T($q_{i},q_{j}$) = $(R_{1})(R_{2})$*$(R_{3})\cup (R_{4})$. Para $R_{1}$ = T$(q_{i},q_{sai}),R_{2}$ = T$(q_{sai},q_{sai}),R_{3}=$T$(q_{sai},q_{j})$ e $R_{4}$= T$(q_{i},q_{j})$.
4. Retorne G'.

Referências

• Yo-Sub Han e Derick Wood. "The Generalization of Generalized Automata: Expression Automata." Na: 9th International Conference on Implementation and Application of Automata, CIAA 2004, Kingston, Canada, 22–24 de Julho, 2004, Revised Selected Papers, LNCS 3317, pp. 156–166. doi:10.1007/b105090
• Michael Sipser. 2006. Introduction to the Theory of Computation (2nd ed.). International Thomson Publishing.

Ligações externas

• Uma descrição gráfica de AFNGs e o processo de conversão de um AFN para uma expressão regular utilizando AFNGs pode ser encontrado em [1] (em inglês)