DIM0606 - LINGUAGENS FORMAIS E AUTÔMATOS

Um Autômato Finito Não-determinístico (AFN) é uma quintupla $$A=⟨\mathcal{Q},\Sigma ,{\delta }_N,q_0,F⟩$$ onde:

• $\mathcal{Q}$ é um conjunto não-vazio e finito de estados internos.
• $\Sigma$ é um alfabeto de entrada.
• ${\delta }_N:\mathcal{Q}\times \Sigma \to \wp \left(\mathcal{Q}\right)$ é uma função total de transição.
• $q_0\in \mathcal{Q}$ é o estado inicial.
• $F\subseteq \mathcal{Q}$ é o conjunto de estados finais ou de aceitação.

Seja $A=⟨\mathcal{Q},\Sigma ,{\delta }_N,q_0,F⟩$ um AFN. Define-se a função de transição não-determinística estendida $${\hat{\delta }}_N:\mathcal{Q}\times {\Sigma }^{\ast }\to \wp \left(Q\right),$$ tal que: $${\hat{\delta }}_N\left(q,\lambda \right)=q$$ $${\hat{\delta }}_N\left(q,wa\right)=\bigcup _{q^{\prime }\in {\hat{\delta }}_N\left(q,w\right)}{\delta }_N\left(q^{\prime },a\right),$$ para todo $q\in \mathcal{Q}$, $w\in {\Sigma }_{\ast }$ e $a\in \Sigma$.