Computação Não Determinista

Generalização dos autómatos deterministas.

• Computação Não Determinista
  • Introdução
  • Autómatos Finitos Não Deterministas
  • Equivalência entre Expressões Regulares e Autómatos Finitos Não Deterministas
    • Construção de Thompson
    • Algoritmo de Kleene
  • Equivalência entre AFND e AFD
  • Conclusão

Introdução

Com vista a obter-se um modelo de computação das linguagens regulares, estão por responder duas questões:

1. Qualquer linguagem regular é aceite por um AFD?
2. Qualquer linguagem aceite por um AFD é regular?

Formalmente, para responder a estas questões, mostra-se como obter um AFD "equivalente" a uma ER dada e, reciprocamente, como obter uma RE "equivalente" a um dado AFD.

Para construir estas equivalências é necessária estudar uma variante não determinista dos AFD.

Autómatos Finitos Não Deterministas

Nos AF deterministas há sempre exatamente uma transição para cada combinação $(q,a)\in Q\times \Sigma$. Isto é, no diagrama, de cada estado $q$ sai sempre exatamente uma aresta $a$, para cada $a\in \Sigma$.

Diagrama de Um AFD.
De cada vértice sai exatamente uma aresta para cada símbolo.

Para os diagramas das expressões regulares o caso é diferente:

• Algumas arestas "são" $\lambda$.
• Não é necessário sair uma aresta para cada símbolo.
• Podem sair várias arestas com o mesmo símbolo.

Por exemplo, para a expressão regular ${\left(11\cup 0\right)}^{\ast }{\left(00\cup 1\right)}^{\ast }$ tem-se o diagrama

Diagrama de uma ER.
Não se verificam as restrições dos AFD.

Intuitivamente, as arestas dos AFD são caminhos obrigatórios enquanto que as arestas das RE são caminhos possíveis.

Os Autómatos Finitos Não Deterministas generalizam os AFD com todos os tipos de arestas das ER. Desta forma obtém-se um modelo computacional das ER que pode "correr" e ser analisado em termos de desempenho.

Autómato Finito Não Determinista (AFND). Um Autómato Finito Não Determinista (AFND) é um tuplo $A=\left(Q,\Sigma ,\delta ,q_I,F\right)$ em que

• Estados de Controlo $Q$ é um conjunto finito.
• Alfabeto de Entrada $\Sigma$ é um alfabeto.
• Transição $\delta :Q\times \left(\Sigma \cup \left\{\lambda \right\}\right)\to \mathcal{P}\left(Q\right)$ é uma função.
• Estado Inicial $q_I\in Q$.
• Estados Finais ou de Aceitação $F\subseteq Q$.

A diferença entre as definições de AFD e AFND está na assinatura da transição:

1. A assinatura da transição dos AFD é $\delta :Q\times \Sigma \to Q$.
2. Nos AFND acrescenta-se a palavra vazia $\lambda$ a $\Sigma$. Desta forma, nos diagramas algumas arestas também podem ser $\lambda$, além de $a\in \Sigma$.
3. Em vez de $\delta \left(q,x\right)$ ser um único estado de controlo, nos AFND é um conjunto de possíveis estados, incluindo nenhum. Isto é, em vez de $\delta \left(q,x\right)\in Q$, nos AFND $\delta \left(q,x\right)\subseteq Q$.

É necessário replicar nos AFND o percurso feito com os AFD. Em particular, definir para os AFND o que é uma configuração, computação, palavra e linguagem aceite. Porém, é mais útil começar por definir o diagrama de um AFND.

Diagrama de um AFND. Seja $A=\left(Q,\Sigma ,\delta ,q_I,F\right)$ um AFND. O diagrama de $A$ define-se como no caso dos AFD, tendo em conta que algumas arestas podem ser $\lambda$.

Por exemplo, dado o AFND com estado inicial $q_I=0$, estados finais $F=\left\{2\right\}$ e transição $$\begin{array}{cccc}q& 0& 1& \lambda \\ 0& \varnothing & \left\{0,1\right\}& \left\{1\right\}\\ 1& \left\{2\right\}& \left\{1,2\right\}& \varnothing \\ 2& \left\{2\right\}& \varnothing & \left\{1\right\}\end{array}$$ o diagrama que se obtém é

Exemplo de Diagrama de um AFND

Note-se que:

• A tabela da transição tem uma coluna adicional, $\lambda$.
• As "células" da tabela são subconjuntos de estados de controlo. Um valor possível é o conjunto vazio $\varnothing$.
• Neste primeiro exemplo os conjuntos foram denotados com $\left\{\dots \right\}$ mas sempre que possível será usada uma notação mais compacta:
  • Em vez de se escrever "$\left\{0,2\right\}$" escreve-se apenas "$02$", "$02$" ou "$0,2$" se a vírgula for mesmo necessária.
  • O conjunto vazio é representado por nada: em vez de "$\varnothing$" escreve-se apenas "".
• Os estados finais podem ser assinalados com o prefixo "$f$" e o estado inicial com um prefixo "$i$". Se nada for indicado o estado inicial é sempre $q_0$ ou $0$ e dispensa-se a indicação de que é inicial.

De acordo com estas convenções a tabela da transição acima fica $$\begin{array}{rccc}& 0& 1& \lambda \\ 0& & 01& 1\\ 1& 2& 12& \\ f2& 2& & 1\end{array}$$ e define completamente o AFND $A$. Isto é, lendo a tabela determinam-se $Q,\Sigma ,\delta ,q_I,F$ todos os atributos que definem um AFND.

Tal como observado para os AFD, a função de transição de um AFND é quase sempre representada por uma tabela mas por vezes é conveniente apresentá-la como um conjunto de triplos: $$\left\{\left(i,a,J\right):J=\delta \left(i,a\right)\right\}.$$

A transição acima, como um conjunto de triplos, fica: $$\left\{\left(0,0,\varnothing \right),\left(0,1,\left\{0,1\right\}\right),\left(0,\lambda ,\left\{1\right\}\right),\left(1,0,\left\{2\right\}\right),\left(1,1,\left\{1,2\right\}\right),\left(1,\lambda ,\varnothing \right),\dots \right\}$$

Observação: No caso dos AFD os triplos são $\left(i,a,j\right)\in Q\times \Sigma \times Q$ e para os AFND os triplos são $\left(i,a,J\right)\in Q\times \Sigma \times \mathcal{P}\left(Q\right)$. Enquanto que nos AFD $j\in Q$, nos AFND $J\subseteq Q$, podendo $J$ ser vazio, ter zero, um, dois, $n$ elementos de $Q$.

Configuração. Computação AFND. Seja $A=\left(Q,\Sigma ,\delta ,q_I,F\right)$ um AFND.

A definição de configuração como um par $\left(q,s\right)\in Q\times {\Sigma }^{\ast }$ permanece igual ao caso dos AFD.

A computação da palavra $p=a_1{a}_2\dots a_n\in {\Sigma }^{\ast }$ pelo AFND $A$ é uma sequência de configurações $$\left(q_0,p_0\right){⊢}_A\left(q_1,p_1\right){⊢}_A\cdots {⊢}_A\left(q_n,p_n\right)$$ em que:

• base (configuração inicial) $q_0=q_I$ e $p_0=p$.
• passo (processamento do símbolo ativo): $q_{i+1}\in \delta \left(q_i,a\right)$ e $p_i=a{p}_{i+1}$.
• passo (transição vazia): $q_{i+1}\in \delta \left(q_i,\lambda \right)$ e $p_i=p_{i+1}$.
• fim $p_n=\lambda$ ou não há mais passos possíveis.

Ao contrário do que acontece com os AFD, nos AFND cada palavra pode ter mais do que uma computação possível.

Por exemplo, a palavra $01$ tem três computações possíveis:

• $0\stackrel{\lambda }{⊢}1\stackrel{0}{⊢}2\stackrel{\lambda }{⊢}1\stackrel{1}{⊢}1\notin F$: rejeita?
• $0\stackrel{\lambda }{⊢}1\stackrel{0}{⊢}2\stackrel{\lambda }{⊢}1\stackrel{1}{⊢}2\in F$: aceita?
• $0\stackrel{\lambda }{⊢}1\stackrel{0}{⊢}2\stackrel{\lambda }{⊢}1\stackrel{1}{⊢}2\stackrel{\lambda }{⊢}1\notin F$: rejeita?

Esta situação, em que as computações de uma palavra podem terminar em vários estados, alguns finais e outros não, torna a definição de palavra aceite um pouco mais complicada do que para os AFD:

Palavra Aceite. Linguagem Reconhecida (AFND). Seja $A=\left(Q,\Sigma ,\delta ,q_I,F\right)$ um AFND.

Uma palavra $p\in {\Sigma }^{\ast }$ é aceite por $A$ se existe alguma computação de $p$ por $A$ que termina num estado final $q\in F$ depois de terem sido lidos todos os símbolos de $p$. Isto é, se entre todas as computações de $p$ por $A$ alguma termina numa configuração $\left(q,\lambda \right)$ com $q\in F$.

A linguagem reconhecida (ou aceite) por $A$ é o conjunto de todas as palavras aceites por $A$: $$L(A)=\left\{p:\exists \left(q_I,p\right){⊢}_A^{\ast }\left(q,\lambda \right),q\in F\right\}$$

Neste ponto a situação em relação ao Problema Principal de ALP é a seguinte :

1. As Linguagens e as Expressões Regulares são candidatas para formalizar rigorosamente as linguagens de programação. Idealmente, cada linguagem de programação poderia ser representada por uma ER.
2. Os Autómatos Finitos Deterministas são candidatos para resolver computacionalmente a questão de saber se um palavra dada está, ou não, numa certa linguagem regular.
3. Mas os AFD parecem ser demasiado restritivos para representar as ER. Comparando os respetivos diagramas, não há arestas vazias, etc.
4. Os Autómatos Finitos Não Deterministas generalizam os AFD de forma a suportarem todos os tipos de arestas das ER.

De forma a resolver a questão da representação computacional das linguagens regulares, há que responder afirmativamente às seguintes duas questões;

1. Qualquer linguagem regular é aceite por um AFND?
2. Qualquer linguagem aceite por um AFND é regular?

Equivalência entre Expressões Regulares e Autómatos Finitos Não Deterministas

Para estabelecer a equivalência entre ER e AFND têm de ser resolvidos dois problemas:

1. ER → AFND (Construção de Thompson): Dada uma ER qualquer, $e$, encontrar um AFND $A$ tal que $L(A)=L(e)$ (isto é, Qualquer linguagem regular é aceite por um AFND?).
2. AFND → ER (Algoritmo de Kleene): Dado um AFND qualquer, $A$, encontrar uma ER $e$ tal que $L(e)=L(A)$ (isto é, Qualquer linguagem aceite por um AFND é regular?).

A resolução do primeiro problema usa a "Construção de Thompson" descrita já a seguir. Para resolver o segundo problema usa-se o "Algoritmo de Kleene", que remove um a um os vértices do diagrama do AFND.

Construção de Thompson

O primeiro problema é de resolução muito fácil, considerando os diagramas das ER e dos AFND:

Construção de Thompson. Dada uma ER $e$ sobre $\Sigma$, o diagrama de $e$ pode ser interpretado como o diagrama de um AFND $A$. Nesse caso $L(A)=L(e)$.

Por exemplo, seja $e=a\cup b{\left(a\cup b\right)}^{\ast }$. Numerando os vértices do seu diagrama da esquerda para a direita (mas serve qualquer critério desde que cada vértice fique com um "nome" diferente dos restantes) obtém-se:

Exemplo de um Diagrama da ER $a\cup b{\left(a\cup b\right)}^{\ast }$

Seja $A$ o AFND que se obtém deste diagrama, descrito pela tabela

$$\begin{array}{rccc}& a& b& \lambda \\ 0& 3& 1& \\ 1& & & 2\\ 2& 2& 2& 3\\ f3& & & \end{array}$$

A "equivalência" entre $e$ e $A$ depende de se verificarem as seguintes duas condições:

• $L(e)\subseteq L(A)$: Cada palavra de $L(e)$ é aceite por $A$ ou, equivalentemente, $\overline{L(A)}\subseteq \overline{L(e)}$: cada palavra rejeitada por $A$ não está em $L(e)$.
• $L(A)\subseteq L(e)$: Cada palavra aceite por $A$ está em $L(e)$ ou, equivalentemente, $\overline{L(e)}\subseteq \overline{L(A)}$: cada palavra que não está em $L(e)$ é rejeitada por $A$.

A demonstração completa e formal de cada um dos pontos anteriores sai do âmbito de ALP. Mas a verificação de alguns casos é um exercício importante.

• Palavras de $L(e)$: $a,b,ba,baba$. Estas palavras são aceites por $A$?
• Palavras que não estão em $L(e)$: $\lambda ,aa,ab$. Estas palavras são rejeitadas por $A$?

Para verificar que a palavra $p$ é aceite por $A$, basta que uma computação de $p$ por $A$ processe todos os símbolos $p$ e termine num estado final.

Por exemplo, $p=a$ tem a seguinte computação por $A$: $0\stackrel{a}{⊢}3\in F$. Portanto $p=a$ é aceite por $A$.

Para $p=b$ há a seguinte computação: $0\stackrel{b}{⊢}1\stackrel{\lambda }{⊢}2\stackrel{\lambda }{⊢}3\in F$. Todos os símbolos de $p=b$ foram processados e a computação termina num estado final. Portanto $p=b$ é aceite.

Exercício. Verifique que as restantes palavras de $L(e)$ listadas acima também são aceites por $A$.

Para verificar que a palavra $p$ é rejeitada por $A$ é necessário que nenhuma computação de $p$ por $A$ processe todos os símbolos $p$ e termine num estado final.

Por exemplo, $p=\lambda$ tem apenas uma computação por $A$: $0\notin F$ (começa no estado inicial e não avança mais).

Embora esta computação processe todos os símbolos de $p=\lambda$, não termina num estado final. Como não há mais computações de $p=\lambda$ por $A$ conclui-se que $A$ rejeita $p=\lambda$.

Se $p=aa$ também só há uma computação possível: $0\stackrel{a}{⊢}3\in F$ e daqui não é possível avançar mais. Neste caso, embora a computação tenha terminado num estado final, faltou processar todos os símbolos de $p=aa$. Portanto esta palavra é rejeitada.

Exercício. Verifique que as restantes palavras listadas acima que não estão em $L(e)$ também são rejeitadas por $A$.

Algoritmo de Kleene

Com a Construção de Thompson fica estabelecido que qualquer linguagem regular é aceite por um AFND. Falta verificar que qualquer linguagem aceite por um AFND é regular.

Para esse efeito apresenta-se um método, o "Algoritmo de Kleene", que transforma o diagrama de um AFND numa expressão regular "equivalente".

Neste processo o diagrama é transformado por uma sequência de passos onde se remove um vértice de cada vez. O vértice removido é substituído por certas ER. No fim do processo fica apenas o vértice inicial e um vértice final, ligados por uma aresta com a ER final.

Um exemplo, ainda informal

1. Dado o seguinte AFND na forma de um diagrama:

   

2. Representa-se por $E_{ij}$ a expressão da aresta que liga o vértice $i$ ao vértice $j$. Por exemplo, $E_{12}=a,E_{23}=\lambda$.

3. Neste diagrama:

   1. Nenhuma aresta entra no vértice inicial.
   2. Existe apenas um vértice final.
   3. Nenhuma aresta sai do vértice final.

4. Para eliminar o vértice $1$:

   1. Que caminhos "passam em $1$"? Há dois: $0\to 1\to 2$ e $2\to 1\to 2$.
   2. Seja $i\to k\to j$ um desses caminhos. Adiciona-se ao diagrama a aresta $i\to j$ com $E_{ij}\cup E_{ik}{\left(E_{kk}\right)}^{\ast }{E}_{kj}$.
   3. Repete-se o passo anterior para todos os caminhos que passam no vértice a eliminar.

5. O novo diagrama, sem o vértice $1$, é:

   

6. Eliminado o vértice $2$, obtém-se:

   

7. Restam apenas o vértice inicial e o final. A expressão regular "equivalente" ao AFND é $a{\left(ba\right)}^{\ast }$.

O núcleo do processo está no passo 4 mas antes de começar é preciso que o diagrama do AFND esteja "bem preparado", conforme as condições do passo 3.

Diagrama Bem Preparado. Um diagrama está bem preparado se

1. Nenhuma aresta entra no vértice inicial.
2. Existe apenas um vértice final.
3. Nenhuma aresta sai do vértice final.

Nem todos os diagramas estão bem preparados mas é sempre possível transformar um diagrama de forma a obter-se outro equivalente e bem preparado:

Autómato Bem Preparado. Seja $A=\left(Q,\Sigma ,\delta ,q_I,F\right)$ um AFND.

O AFND $A^{\prime }=\left(Q\cup \left\{q_I^{\prime },q_f\right\},\Sigma ,{\delta }^{\prime },q_I^{\prime },\left\{q_F\right\}\right)$ em que:

• $q_I^{\prime }\ne q_F$ e $\left\{q_I^{\prime },q_F\right\}\cap Q=\varnothing$.
• ${\delta }^{\prime }\left(q_I^{\prime },\lambda \right)=\left\{q_I\right\}$.
• ${\delta }^{\prime }\left(q,\lambda \right)=\left\{q_F\right\}$ para cada $q\in F$.
• ${\delta }^{\prime }\left(q,x\right)=\delta \left(q,x\right)$ nos restantes casos.

está bem preparado e é equivalente a $A$.

Por exemplo, se $A$ for dado pela tabela $$\begin{array}{rccc}\delta & a& b& \lambda \\ 0& 1& & \\ f1& & 0& \end{array}$$ não está bem preparado porque o estado inicial, $0$, recebe uma aresta de $1$ e, também, porque sai uma aresta do estado final. Um AFND equivalente e bem preparado é $$\begin{array}{rccc}{\delta }^{\prime }& a& b& \lambda \\ i{q}_I^{\prime }& & & 0\\ 0& 1& & \\ 1& & 0& q_F\\ f{q}_F& & & \end{array}$$ que está bem preparado. Em termos de diagramas:

Diagrama Mal Preparado	Diagrama Equivalente Bem Preparado

Com autómatos bem preparados pode aplicar-se o processo de eliminação de vértices.

Algoritmo de Kleene. Sejam $A$ um AFND bem preparado e $E_{ij}$ a ER da aresta $i\to j$ no diagrama de $A$.

O caminho $i\to k\to j$ passa no vértice $k$ se $i,j\ne k$ (pode ser $i=j$) e no diagrama existem arestas $i\to k$ e $k\to j$.

A eliminação do vértice $k$ produz um novo diagrama idêntico ao anterior exceto:

• O novo diagrama não tem o vértice $k$.
• Para cada caminho $i\to k\to j$ do diagrama original, o novo diagrama tem a aresta $i\to j$ com valor

$$E_{ij}\cup E_{ik}{\left(E_{kk}\right)}^{\ast }{E}_{kj}.$$

No diagrama que se obtém quando foram eliminados todos os vértices exceto o inicial e final, a expressão regular $E_{IF}$ que está na aresta $q^{\prime }I\to q$ é "equivalente" ao AFND $A$ no sentido em que $$L\left(E_{IF}\right)=L\left(A\right).$$

Um exemplo mais complicado, passo a passo. Seja $A$ o seguinte diagrama/AFND, que não está bem preparado:

Uma versão equivalente, bem preparada é

Eliminar $0$. Caminhos que passam em $0$:

• $I\to 0\to 1$. ER resultante: $\lambda \cup a$.
• $I\to 0\to 2$. ER resultante: $b$.

Eliminar $2$. Caminhos que passam em $2$:

• $I\to 2\to 3$. ER resultante: $b$.
• $3\to 2\to 3$. ER resultante: $a\cup b$.

Eliminar $3$. Caminhos que passam em $3$:

• $I\to 3\to 1$. ER resultante: $\lambda \cup a\cup b{\left(a\cup b\right)}^{\ast }a$.
• $1\to 3\to 1$. ER resultante: $b\cup b{\left(a\cup b\right)}^{\ast }a$.

Eliminar $1$. Caminhos que passam em $1$:

• $I\to 1\to F$. ER resultante, e final: $$x=\left(\lambda \cup a\cup b{\left(a\cup b\right)}^{\ast }a\right){\left(b\cup b{\left(a\cup b\right)}^{\ast }a\right)}^{\ast }.$$

A ER final pode ser um pouco simplificada: $$x=\left(\lambda \cup a\right){\left(b\cup b{\left(a\cup b\right)}^{\ast }a\right)}^{\ast }.$$

Exercícios:

• Aplique a Construção de Thompson à ER $x$ acima.
• Escolha palavras de $L(x)$ e verifique que $A$ as aceita.
• Encontre palavras de $L(A)$ e verifique que estão em $L(x)$.
• O que se passa com a palavra $aa$? Está em $L(x)$? E em $L(A)$?

Equivalência entre AFND e AFD

A Construção de Thompson e o Algoritmo de Kleene asseguram que os AFND são "equivalentes" às ER, no sentido em que os AFND e as ER definem exatamente as mesmas linguagens.

Mas os AFND são um mau modelo computacional porque pode ser necessário um número exponencial (no número de estados do autómato) para decidir se $p\in L\left(A\right)$.

Para computar $p\in L(A)$ não se sabe, à partida, quantos "passos" vão ser necessários. No caso em que $p\notin L(A)$ é preciso testar todas computações de $p$ por $A$.

O problema da eficiência da computação não se coloca nos AFD: Demora sempre exatamente $\left|p\right|$ passos, o que é um desempenho ótimo (no sentido em que não há melhor).

Como os AFND generalizam os AFD, todas as linguagens aceites por AFD são também aceites por AFND.

Nesta secção mostra-se que os AFD e os AFND são equivalentes: As linguagens aceites pelos AFD são exatamente as linguagens aceites pelos AFND.

Com as transições vazias, um AFND pode percorrer vários estados sem processar símbolos, ao contrário do que acontece com os AFD. Esta situação fica representada com o fecho vazio e com a transição de entrada.

Fecho Vazio. Seja $A=\left(Q,\Sigma ,\delta ,q_I,F\right)$ um AFND e $q\in Q$.

O fecho vazio de $q$, ${\text{fecho}}_{\lambda }\left(q\right)$, é o conjunto de todos os estados que podem ser alcançados a partir de $q$ com zero ou mais transições vazias. Formalmente:

• base $q\in {\text{fecho}}_{\lambda }\left(q\right)$.
• passo Se $p\in {\text{fecho}}_{\lambda }\left(q\right)$ e $p^{\prime }\in \delta \left(p,\lambda \right)$ então também $p^{\prime }\in {\text{fecho}}_{\lambda }\left(q\right)$.

Também devido às transições vazias, $\delta \left(q,a\right)$ não contém todos os estados que podem ser alcançados a partir de $q$ lendo o símbolo $a$. Para esse efeito tem-se a transição de entrada:

Transição de Entrada. Seja $A=\left(Q,\Sigma ,\delta ,q_I,F\right)$ um AFND.

A transição de entrada é a função de assinatura ${\delta }_{\lambda }:Q\times \Sigma \to \mathcal{P}\left(Q\right)$ que, para cada $q\in Q,a\in \Sigma$, define o conjunto dos estados que podem ser alcançados a partir de $q$ lendo o símbolo $a$. Isto é: $${\delta }_{\lambda }\left(q,a\right)=\bigcup _{q^{\prime }\in {\text{fecho}}_{\lambda }\left(q\right)}{\text{fecho}}_{\lambda }\left(\delta \left(q^{\prime },a\right)\right).$$

Por exemplo, seja $A$ o AFND definido pela tabela $$\begin{array}{rcccl}q& a& b& \lambda & {\text{fecho}}_{\lambda }\left(q\right)\\ 0& & 01& 1& 01\\ 1& 2& 12& & 1\\ f2& 2& & 1& 21\end{array}$$ com o fecho vazio de cada estado já calculado e com o seguinte diagrama

Transição de Entrada: Diagrama do AFND acima

A transição de entrada de alguns casos: $$\begin{array}{rl}{\delta }_{\lambda }\left(0,b\right)& =\left\{0,1,2\right\}\\ {\delta }_{\lambda }\left(0,a\right)& =\left\{2,1\right\}\end{array}$$ Neste caso, por exemplo, $2\in {\delta }_{\lambda }\left(0,a\right)$ porque $0\stackrel{\lambda }{⊢}1\stackrel{a}{⊢}2$ é uma computação de $A$. Já $1\in {\delta }_{\lambda }\left(0,a\right)$ de duas maneiras diferentes: $1\stackrel{a}{⊢}1$ e $1\stackrel{a}{⊢}2\stackrel{\lambda }{⊢}1$.

Exercício: Calcule todas as transições de entrada deste exemplo.

Este "desvio" pelo fecho vazio e transição de entrada serve para formalizar as ferramentas que faltam para o objetivo desta secção: Mostrar que para cada AFND $A$ existe um AFD $A^{\prime }$ "equivalente" no sentido em que $L(A)=L(A^{\prime })$.

Simulação de Não Determinismo. Seja $A=\left(Q,\Sigma ,\delta ,q_I,F\right)$ um AFND.

O AFD equivalente a $A$ é o AFD $A^{\prime }=\left(Q^{\prime },\Sigma ,{\delta }^{\prime },q_I^{\prime },F^{\prime }\right)$ em que:

• Estado Inicial $q_I^{\prime }={\text{fecho}}_{\lambda }\left(q_I\right)$.
• Transição ${\delta }^{\prime }\left(q,a\right)={\bigcup }_{p\in q}{\delta }_{\lambda }\left(p,a\right)$.
• Estados de Controlo $Q^{\prime }$ é definido recursivamente por
  • base $q_I^{\prime }\in Q^{\prime }$.
  • passo Se $q\in Q^{\prime }$ então, para cada $a\in \Sigma ,{\delta }^{\prime }\left(q,a\right)\in Q^{\prime }$.
  • fecho Mais nenhum estado está em $Q^{\prime }$.
• Estados Finais $F^{\prime }=\left\{q\in Q^{\prime }:q\cap F\ne \varnothing \right\}$.

Neste caso $$L(A)=L(A^{\prime }).$$

Por exemplo, para o AFND

Um AFND para $a^{\ast }{b}^{\ast }{c}^{\ast }$

o cálculo de ${\delta }^{\prime }$ e de $Q^{\prime }$ é feito em conjunto:

$$\begin{array}{rccc}{\delta }^{\prime }& a& b& c\\ if{q}_I^{\prime }={\text{fecho}}_{\lambda }\left(0\right)=\underline{02}& 02& 12& 1\\ f\underline{12}& \varnothing & 12& 1\\ f\underline{1}& \varnothing & \varnothing & 1\\ \varnothing & \varnothing & \varnothing & \varnothing \end{array}$$

Os estados de $A^{\prime }$ são conjuntos de estados de $A$. Para evitar uma notação muito pesada (por exemplo, $\left\{0,2\right\}$) omitem-se as chavetas e as vírgulas (e escreve-se apenas $02$). O texto vermelho $xyz$ representa estados "novos" na tabela e os estados finais de $A$ estão sublinhados. O respetivo diagrama é

Um AFD equivalente ao AFND para $a^{\ast }{b}^{\ast }{c}^{\ast }$

O teorema/método da Simulação de Não Determinismo assegura que estes dois autómatos são equivalentes, isto é, reconhecem a mesma linguagem.

Conclusão

Uma vantagem dos AFD é que a computação é linear no comprimento da palavra pois executa exatamente $\left|p\right|$ passos para computar a resposta a $p\in L(A^{\prime })$ enquanto que para o AFND a computação da resposta $p\in L(A)$ é exponencial.

Este ganho no número de passos tem um custo: se o AFND $A$ tem $n$ estados então $A^{\prime }$, o AFD equivalente, pode ter até $2^n$ estados.

Estão determinadas três equivalências:

• As ER e os AFND são equivalentes devido à Construção de Thompson e ao Algoritmo de Kleene.
• Os AFND e os AFD são equivalentes devido à Definição de AFND e à Simulação de Não Determinismo.
• Portanto, também as ER e os AFD são equivalentes.

Portanto

Os AFD proporcionam um bom modelo computacional para as ER.

Mas ainda há questões importantes a resolver. A próxima secção trata de formas de reduzir o tamanho dos AFD e de facilitar a construção automática de AFD e AFND antes de ser tratada a questão final, saber se "as linguagens regulares são adequadas para todas as linguagens de programação?"