Máquina de estados finitos não determinística

Na teoria da computação, uma máquina de estados finita não-determinística ou um autômato finito não-determinístico (AFND) é uma máquina de estados finita onde para cada par de estado e símbolo de entrada pode haver vários próximos estados possíveis. Isso o distingue do autômato finito determinístico (AFD), onde o próximo estado possível é univocamente determinado. Embora AFD e AFND possuam definições distintas, pode ser mostrado na teoria formal que eles são equivalentes e, deste modo, para qualquer AFND dado, pode-se construir um AFD equivalente e vice-versa: essa é a construção do conjunto das partes. Ambos os tipos de autômatos reconhecem apenas linguagens regulares. Máquinas de estados finitas não-determinísticas são às vezes estudadas com o nome de subshifts de tipo finito.

Máquinas de estados finitas não-determinísticas são generalizadas pelo autômato probabilístico, o qual atribui uma probabilidade para cada transição de estado, e por várias outras maneiras, tais como autômatos com pilha e AFNs com transições ε.

Autômatos finitos não-determinísticos foram introduzidos em 1959 por Michael O. Rabin e Dana Scott,^[1] que também mostraram sua equivalência com autômatos finitos determinísticos.

Explicação intuitiva

Um AFND, similarmente a um AFD, lê uma cadeia de símbolos de entrada. Para cada símbolo da entrada há uma transição para um novo estado, até que todos os símbolos de entrada sejam lidos.

Ao contrário de um AFD, há um não-determinismo onde, para cada símbolo de entrada, seu próximo estado pode ser um de dois ou mais estados possíveis. Assim, na definição formal, o próximo estado é um elemento do conjunto das partes dos estados. Este elemento, um conjunto, representa algum subconjunto de todos os possíveis estados que podem ser considerados.

Uma extensão do AFND é o AFND-lambda (também conhecido como AFND-epsilon ou como AFND com transições epsilon), o qual permite uma transição para um novo estado sem ler nenhum símbolo de entrada. Por exemplo, se está no estado 1, com o próximo símbolo de entrada um a, pode-se se mover para o estado 2 sem ler nenhum símbolo de entrada. Assim, tem-se uma ambiguidade: o sistema está no estado 1 ou no estado 2 antes de ler a entrada a? Por causa desta ambiguidade, é mais conveniente falar de um conjunto de possíveis estados que o sistema pode estar. Assim, antes de ler um símbolo de entrada a, o AFND-epsilon pode estar em qualquer um dos estados do conjunto {1,2}. Equivalentemente, pode-se imaginar que o AFND está nos estados 1 e 2 'ao mesmo tempo': isso dá uma ideia informal da construção do conjunto das partes: o AFD equivalente a um AFND é definido como aquele que está no estado q={1,2}. Transições para novo estados sem ler símbolos de entrada são chamadas de transições lambda ou transições epsilon. Elas são comumente rotuladas com as letras gregas λ ou ε.

A noção de aceitação de uma entrada é similar àquela em um AFD. Quando o último símbolo de entrada é lido, diz-se que o AFND aceita se e somente se existe algum conjunto de transições que irá levá-lo a um estado de aceitação. Do mesmo modo, ele rejeita, se, não importando quais transições sejam aplicadas, ele não terminar num estado de aceitação.

Definição formal

Dois tipos similares de AFNDs são comumente definidos: o AFND e o AFND com transições ε. O tipo comum é definido como uma 5-tupla, ${\displaystyle M=(Q,\Sigma ,\delta ,q_{0},F)\,\!}$, consistindo de

• um conjunto finito de estados ${\displaystyle Q}$;
• um conjunto finito de símbolos de entrada ${\displaystyle \Sigma }$, denominando o alfabeto;
• uma função de transição ${\displaystyle \delta :Q\times \Sigma \rightarrow }$ ${\displaystyle {\mathcal {P}}(Q)}$;
• um estado inicial ${\displaystyle q_{0}\in Q}$;
• um conjunto distinto de estados ${\displaystyle F}$ como estados de aceitação (ou estados finais), ${\displaystyle F\subseteq Q}$.

Aqui, ${\displaystyle {\mathcal {P}}(Q)}$ denota o conjunto das partes de ${\displaystyle Q}$

O AFND com transições ε (também conhecido como AFN-epsilon ou AFN-lambda) é definido por uma 5-upla extremamente semelhante, porém, a função de transição é substituída por uma que permite a cadeia vazia ε como uma entrada possível. Desse modo, sua função de transição é dada por:

${\displaystyle \delta :Q\times (\Sigma \cup \{\epsilon \})\rightarrow }$ ${\displaystyle {\mathcal {P}}(Q)}$

Pode-se mostrar que AFND comum e um AFND com transições ε são equivalentes e, assim, dado qualquer AFND comum, pode-se construir um AFND com transições ε que reconhece a mesma linguagem e vice-versa.

Propriedades dos AFNDs

A máquina começa no estado inicial especificado e lê uma cadeia de símbolos do seu alfabeto. O autômato usa a função de transição de estado ${\displaystyle \delta }$ para determinar o próximo estado usando o estado atual e o símbolo que acabou de ser lido, o que inclui a cadeia vazia, no caso dos AFNDs com transições ε. Entretanto, "o próximo estado de um AFND não depende somente do evento atual, mas também de um número arbitrário de eventos subsequentes de entradas. Até esses eventos subsequentes ocorrerem, não é possível determinar onde a máquina de estados está".^[2]

O conjunto de todas as cadeias que são aceitas por um AFND é a linguagem que o AFND aceita. Esta linguagem deve ser uma linguagem regular.

Para todo AFND pode ser encontrada um AFD que aceite a mesma linguagem. Portanto, é possível converter um AFND existente em um AFD com o propósito de implementar (talvez) uma máquina mais simples. Isto pode ser realizado usando a construção do conjunto das partes, o que pode levar a um aumento exponencial no número de estados necessários. Uma prova formal desta construção do conjunto das partes pode ser encontrada aqui.

Muitas vezes, pode ser mais fácil construir um AFND do que um AFD equivalente, tanto pelo entendimento como pelo tamanho da construção. AFNDs são comumente introduzidos no início de cursos de informática teórica para desenvolver a ideia de não-determinismo em modelos computacionais mais poderosos, como as máquina de Turing.

Definição formal de computação dos AFNDs

Seja ${\displaystyle N=(Q,\Sigma ,\delta ,q_{0},F)}$ um AFND e ${\displaystyle w\in \Sigma }$ uma cadeia do alfabeto.

Diz-se que ${\displaystyle N}$ aceita ${\displaystyle w}$ se podemos escrever ${\displaystyle w}$ como ${\displaystyle w=y_{1}y_{2}...y_{n}}$ onde cada ${\displaystyle y_{i}\in \Sigma _{\epsilon }}$ e existe uma sequência de estados ${\displaystyle r_{0}r_{1}..r_{n}}$ em ${\displaystyle Q}$ seguindo as três condições a seguir:

1. ${\displaystyle r_{0}=q_{0}}$;
2. ${\displaystyle r_{i+1}\in \delta (r_{i},y_{i+1})}$ para ${\displaystyle i=0,1,...,n-1}$;
3. ${\displaystyle r_{n}\in F}$.

Propriedades do AFND-ε

Para todo ${\displaystyle p,q\in Q,}$ escreve-se ${\displaystyle p{\stackrel {\epsilon }{\rightarrow }}q}$ se e somente se ${\displaystyle q}$ pode ser alcançado a partir de ${\displaystyle p}$ através de zero ou mais transições ${\displaystyle \epsilon }$. Em outras palavras, ${\displaystyle p{\stackrel {\epsilon }{\rightarrow }}q}$ se e somente se existe ${\displaystyle q_{1},q_{2},\cdots q_{k}\in Q}$ onde ${\displaystyle k\geq 0}$ tal que

${\displaystyle q_{1}\in T(p,\epsilon ),q_{2}\in T(q_{1},\epsilon ),\cdots q_{k}\in T(q_{k-1},\epsilon ),q\in T(q_{k},\epsilon )}$.

Para qualquer ${\displaystyle p\in Q}$, o conjunto de estados que podem ser alcançados a partir de p é chamado de fecho-epsilon ou fecho-ε de p, e é escrito como

${\displaystyle E(\{p\})=\{q\in Q:p{\stackrel {\epsilon }{\rightarrow }}q\}}$.

Para qualquer subconjunto ${\displaystyle P\subset Q}$, define-se o fecho-ε de P como

${\displaystyle E(P)=\bigcup \limits _{p\in P}E(\{p\})}$.

As transições ε são transitivas, de modo que pode ser demonstrado que, para todo ${\displaystyle q_{0},q_{1},q_{2}\in Q}$ e ${\displaystyle P\subset Q}$, se ${\displaystyle q_{1}\in E(\{q_{0}\})}$ e ${\displaystyle q_{2}\in E(\{q_{1}\})}$, então ${\displaystyle q_{2}\in E(\{q_{0}\})}$.

Igualmente, se ${\displaystyle q_{1}\in E(P)}$ e ${\displaystyle q_{2}\in E(\{q_{1}\})}$ então ${\displaystyle q_{2}\in E(P)}$

Seja ${\displaystyle x}$ uma cadeia sobre o alfabeto ${\displaystyle \Sigma \cup \{\epsilon \}}$. Um AFND-ε ${\displaystyle M}$ aceita a cadeia ${\displaystyle x}$ se existe tanto uma representação de ${\displaystyle x}$ na forma ${\displaystyle x_{1}x_{2}...x_{n}}$, onde ${\displaystyle x_{i}\in \{\Sigma \cup \epsilon \}}$, como uma sequência de estados ${\displaystyle p_{0},p_{1},...,p_{n}}$, onde ${\displaystyle p_{i}\in Q}$, seguindo as seguintes condições:

1. ${\displaystyle p_{0}\in E(\{q_{0}\})}$;
2. ${\displaystyle p_{i+1}\in E(\delta (p_{i},x_{i+1}))}$ para ${\displaystyle i=0,1,...,n-1}$;
3. ${\displaystyle p_{n}\in F}$.

Implementação

Existem várias maneiras de implementar um AFND:

• Converter para o AFD equivalente. Em alguns casos isso pode causar um aumento exponencial no tamanho do autômato e, assim, espaço proporcional auxiliar ao número de estados do AFND (como o armazenamento do estado exige no máximo um bit para cada estado no AFND).

• Manter uma estrutura do conjunto de dados de todos os estados em que a máquina poderia estar. Na leitura do ultimo simbolo de entrada, se um desses estados é um estado final, a máquina aceita a cadeia. No pior dos casos, isso pode exigir espaço auxiliar proporcional ao número de estados do AFND; se a estrutura de conjunto usa um bit por estado do AFND, então esta solução é exatamente equivalente a anterior.

• Criar múltiplas cópias. Para cada n maneiras de decidir, o AFND cria até ${\displaystyle n-1}$ cópias da máquina. Durante sua computação, caso o AFND se depare com uma situação na qual existam múltiplas maneiras de se prosseguir, isto é, a função de transição leve a mais de um estado, pode-se considerar que o AFND divide-se em múltiplas cópias e cada uma dessas cópias fica responsável pela computação de uma das transições possíveis. Quando alguma cópia da máquina chega a uma situação na qual não há transição possível, diz-se que essa cópia do AFND "morre", não mais fazendo parte da computação. Se forma semelhante, caso alguma das cópias do AFND esteja em um estado de aceitação ao final da computação da cadeia de entrada, diz-se que o AFND aceita a dada cadeira. Isso também requer armazenamento linear com respeito ao número de estados do AFND, como também pode haver uma máquina para cada estado do AFND. Dessa forma, pode-se pensar no não-determinismo dos AFNDs como uma computação paralela, na qual o AFND (análogo a um processo) pode se bifurcar (de forma análoga à chamada de sistema Fork).

• Árvore de possibilidades. Derivada da ideia de ramos de computação, nessa forma, representamos a computação a partir de uma árvore de possibilidades cuja raiz corresponde ao início da computação. A cada símbolo de entrada lido, analisa-se a transição e se criam nós filhos adequadamente, isto é, caso haja 2 estados possíveis em uma dada transição, a árvore ramifica no nível atual e criam-se 2 novos filhos. Analogamente, se houver apenas uma transição possível, a árvore não é ramificada no dado momento e se não houver transição possível, o ramo "morre" e não é mais levado em conta na computação.

• Explicitamente propague tokens através da estrutura de transição do AFND e combine sempre que um token alcançar um estado final. Isto, às vezes, é útil quando o AFND pode codificar contextos adicionais sobre os eventos que desencadearam da transição. (Para uma implementação que usa esta técnica acompanhe as referências e olhe os Tracematches.^[3])

Exemplo

• Exemplo 1: O seguinte exemplo explica um AFND M, com um alfabeto binário, que determina se uma entrada contém um número par de 0s ou um número par de 1s (Note que 0 ocorrências é um número par de ocorrências). Seja M= (Q, Σ, T, s₀, F) onde
• Σ = {0, 1},
• Q= {s₀, s₁, s₂, s₃, s₄},
• E({s₀}) = { s₀, s₁, s₃ }
• F= {s₁, s₃}, and
• A função de transição T pode ser definida por esta tabela de transição de estados:

	0	1	ε
S0	{}	{}	{S1, S3}
S1	{S2}	{S1}	{}
S2	{S1}	{S2}	{}
S3	{S3}	{S4}	{}
S4	{S4}	{S3}	{}

O diagrama de estados para M é:

 :

M pode ser visto como a união de dois AFDs: um com os estados {S₁, S₂} e o outro com os estados {S₃, S₄}.

A linguagem de M pode ser descrita pela linguagem regular dada por esta expressão regular ${\displaystyle (1^{*}(01^{*}01^{*})^{*})\cup (0^{*}(10^{*}10^{*})^{*})}$.

• Exemplo 2:

Criar o diagrama do AFND da linguagem L = {w | w termina em 00} com 3 estados. Resposta: O estado inicial é de não aceitação e fica em loop recebendo 1's e 0's até que ele "adivinha" de forma não determinística que um 0 recebido é o penúltimo 0 da cadeia, e assim, passa para o segundo estado, que por sua vez, recebe o último zero e passa para o estado final de aceitação, que não tem nenhuma transição partindo dele, e caso recebe um outro símbolo, o ramo da computação morre.

(Exemplo de exercícío não resolvido do Sipser).

• Exemplo 3:

Criar o diagrama do AFND da linguagem U = { w | w é 0* } com 1 estado. Resposta: O estado inicial é o estado de aceitação e tem apenas 1 transição, que é para ele mesmo, no caso de ler o símbolo 0 da entrada. Caso outro símbolo seja lido, o ramo da computação morre. Neste caso, o não determinismo está associado a não ter uma transição para todos os símbolos do alfabeto. Fazendo um comparativo com o AFD, seria necessário criar um outro estado que é alcançado caso o estado inicial leia 1 da entrada, e que possui um loop para ele mesmo ao receber 0's e 1's.

(Exemplo de exercício não resolvido do Sipser).

• Exemplo 4:

Criar do diagrama do AFND da linguagem A = { w | w = {0}} com 2 estados. Resposta: O estado inicial é estado de não aceitação e tem uma transição para o estado final de aceitação ao ler o símbolo 0 da entrada. O estado final de aceitação não possui transições para nenhum outro estado. Caso o estado inicial leia o símbolo 1 da entrada ou o estado final ler 0 ou 1, o ramo da computação morre.

(Exemplo de exercício não resolvido do Sipser).

• Exemplo 5:

Criar o diagrama do AFND da linguagem B = { w | w = vazio } com 1 estado. Resposta: Só há 1 estado que é o estado de aceitação. Não há nenhuma transição. Se o estado receber qualquer símbolo, o ramo da computação morre.

(Exemplo de exercício não resolvido do Sipser).

Aplicação de AFND-ε

AFNDs e AFDs são equivalentes tal que se uma linguagem é reconhecida por um AFND, ela também é reconhecida por um AFD e vice versa. O estabelecimento de tal equivalência é importante e útil. É útil porque construir um AFND que reconhece uma dada linguagem é algumas vezes mais fácil do que construir um AFD para aquela linguagem. Isso é importante porque AFNDs podem ser usadas para reduzir a complexidade do trabalho matemático necessário para estabelecer muitas propriedades importantes na teoria da computação. Por exemplo, é muito mais fácil provar as propriedades que seguem usando AFNDs do que AFDs:

• A união de duas linguagens regulares é regular:

A ideia da prova parte do princípio de que, tendo duas linguagens regulares e os AFNDs que as reconhecem, podemos tomar os dois AFNDs e combiná-los com um terceiro AFND que aceita sua entrada de qualquer um dos dois AFNDs prévios a aceita. A prova formal pode ser encontrada aqui.

• A concatenação de duas linguagens regulares é regular:

Sendo dois AFNDs iniciais ${\displaystyle A_{1}}$ e ${\displaystyle A_{2}}$, a ideia da prova consiste em construir um novo AFND ${\displaystyle A_{concat}}$ usando a estrutura de ${\displaystyle A_{1}}$ e ${\displaystyle A_{2}}$ na construção. O novo AFND possui como estado inicial, o estado inicial do AFND ${\displaystyle A_{1}}$ e possui toda a estrutura de ${\displaystyle A_{1}}$, com os estados de aceitação de ${\displaystyle A_{1}}$ transformados em estados de não-aceitação possuidores de transições ${\displaystyle \epsilon }$ para o estado inicial de ${\displaystyle A_{2}}$. O novo AFND, por conseguinte, também possui toda a estrutura de ${\displaystyle A_{2}}$, e seus estados de aceitação são os mesmos de ${\displaystyle A_{2}}$. Dessa forma, a entrada sempre poderá ser quebrada em duas partes não-deterministicamente, e só será aceita se puder ter a primeira parte aceita por ${\displaystyle A_{1}}$ e a segunda por ${\displaystyle A_{2}}$.

• O Fecho de Kleene de uma linguagem regular é regular:

Sendo o AFND inicial ${\displaystyle A_{1}}$, é construído um novo AFND ${\displaystyle A_{*}}$ que modifica a estrutura de ${\displaystyle A_{1}}$ para fazer com que os estados de aceitação deste possuam, cada um, uma transição ${\displaystyle \epsilon }$ para o estado inicial de ${\displaystyle A_{1}}$. Adicionalmente, cria-se um novo estado de aceitação que passa a ser o estado inicial de ${\displaystyle A_{*}}$, este possuindo uma transição ${\displaystyle \epsilon }$ para o estado inicial antigo (estado inicial de ${\displaystyle A_{1}}$).

É importante notar que a construção de ${\displaystyle A_{*}}$ a partir da mera adição do estado inicial de ${\displaystyle A_{1}}$ ao conjunto dos estados de aceitação não provaria o que é proposto, pois há casos nos quais certas cadeias indesejadas seriam aceitas. Um exemplo de linguagem cuja computação nessa construção leva a uma falha é a linguagem ${\displaystyle 1(01)^{*}}$.

Notas

1. Rabin and Scott (1959)
2. FOLDOC Free Online Dictionary of Computing, Finite State Machine^{[ligação inativa]}
3. Allan, C., Avgustinov, P., Christensen, A. S., Hendren, L., Kuzins, S., Lhoták, O., de Moor, O., Sereni, D., Sittampalam, G., and Tibble, J. 2005. Adding trace matching with free variables to AspectJ Arquivado em 18 de setembro de 2009, no Wayback Machine.. In Proceedings of the 20th Annual ACM SIGPLAN Conference on Object Oriented Programming, Systems, Languages, and Applications (San Diego, CA, USA, October 16–20, 2005). OOPSLA '05. ACM, New York, NY, 345-364.

Referências

• M. O. Rabin and D. Scott, "Finite Automata and their Decision Problems", IBM Journal of Research and Development, 3:2 (1959) pp. 115–125.
• Michael Sipser, Introduction to the Theory of Computation. PWS, Boston. 1997. ISBN 0-534-94728-X. (see section 1.2: Nondeterminism, pp.47–63.)
• John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-02988-X. (ver capítulo 2)
• Martin, John C. - Introduction to languages and the theory of computation (2ª Edição)

Softwares

• Auger - Software brasileiro com interface gráfica para construção e simulação de autômatos finitos e conversão para outros modelos formais.
• Simulador de Autômatos - Software para criação, teste e conversão de Modelos Formais. Com interface gráfica.
• SCTMF - Software para Criação e Teste de Modelos Formais.
• JFlap - Software americano para testes com interface gráfica.

Conceitos relacionados

• Linguagens formais
• Teoria da computação
• Teoria dos grafos