Autómatos Finitos Determinísticos

Um autómato finito determinístico é um quíntuplo ($Q$, $\sum$, $\delta$, $q_0$, $F$), onde temos:

• $Q$ é um conjunto finito, não vazio, correspondente aos estados possíveis;
• $\sum$ é um conjunto finito, não vazio, que corresponde ao alfabeto do autómato;
• $\delta$ é a função de transição;
• $q_0$ é o estado inicial ($\in Q$);
• $F$ é o conjunto dos estados finais ($\subseteq Q$);

<aside> 💡 Nota: A função dos autómatos finitos também pode ser representada por diagramas de transição de estados ou grafos direcionados.

</aside>

[1]

<aside> ➡️ Teorema: Uma linguagem diz-se regular se existe um autómato finito determinístico que a reconhece.

</aside>

Exemplo: Especificar um autómato que, de entre as palavras que se escrevem com o alfabeto {0, 1, 2}, aceita as que, somados os números, originam um múltiplo de 3.

• Resolução:

Autómatos Finitos Não-Determinísticos

Um autómato finito não-determinístico é um autómato finito em que pelo menos um dos símbolos de entrada possui duas (ou mais) transições de saída para outro estado.

Conversão de Autómatos Não-Determinísticos para Determinísticos (NFA ⇒ DFA)

Exemplo: Suponhamos que queremos desenhar um autómato finito que reconheça as cadeias de números binários que representam múltiplos de 4 (ex: 4, 8, 12, 16, ...)

• Resolução:

<aside> ➡️ Teorema: Todo o autómato não-determinístico é equivalente a um autómato determinístico.

</aside>