Conversão de expressões regulares para AFD/AFN
# Conversão de expressões regulares para AFD/AFN

Conversão de expressões regulares para AFD/AFN é um procedimento utilizado para, dada uma expressão regular (ER), transformá-la em um autômato finito não determinístico(AFN), e deste para um autômato finito determinístico(AFD).

## De ER para AFN

Para converter uma ER R para um AFN N, devemos considerar 6 casos, sendo os três primeiros casos considerados casos-base e os três últimos casos "recursivos":

### Caso 1: R = a

Seja R = a, para algum a em Σ. Então basta construirmos o seguinte AFN que reconhece $L(R)$:
    $Q=\{q_{1},q_{2}\}$
    $q_{0}=q_{1}$
    $q_{acc}=\{q_{2}\}$
    $\delta (q_{1},a)=q_{2}$

### Caso 2: R = ε

Se R = ε, o seguinte AFN reconhece $L(R)$:
    $Q=\{q_{1}\}$
    $q_{0}=q_{1}$
    $q_{acc}=\{q_{1}\}$
    $\delta (q,a)=\emptyset ,\forall q\in Q,\forall a\in \Sigma$

### Caso 3: R =

Se R = $\emptyset$, o seguinte AFN reconhece $L(R)$:
    $Q=\{q_{1}\}$
    $q_{0}=q_{1}$
    $q_{acc}=\emptyset$
    $\delta (q,a)=\emptyset ,\forall q\in Q,\forall a\in \Sigma$

### Caso 4: R = A U B

Se R = A U B, e A e B são expressões regulares, construa o seguinte AFN N para reconhecer L(R), a partir dos AFNs J e K para A e B, respectivamente: Sejam
    $J=(Q_{1},\Sigma ,{\delta }_{1},q_{1},F_{1})$
    $K=(Q_{2},\Sigma ,{\delta }_{2},q_{2},F_{2})$
Então,
    $N=(Q_{1}\times Q_{2},\Sigma ,{\delta },(q_{1},q_{2}),F)$
Tal que
    $\delta ((r_{1},r_{2}),a)=({\delta }_{1}(r_{1},a),{\delta }_{2}(r_{2},a))$
e
    $F=\{(r_{1},r_{2})|r_{1}\in F_{1}\vee r_{2}\in F_{2}\}$

### Caso 5: R = A o B

Se R = A o B(concetenação entre A e B), e A e B são expressões regulares, construa o seguinte AFN N para reconhecer L(R), a partir dos AFNs J e K para A e B, respectivamente: Sejam
    $J=(Q_{1},\Sigma ,{\delta }_{1},q_{1},F_{1})$
    $K=(Q_{2},\Sigma ,{\delta }_{2},q_{2},F_{2})$
Então,
    $N=(Q_{1}\cup Q_{2},\Sigma ,{\delta },q_{1},F_{2})$
Tal que $\delta$ é:
    $q\in Q_{1}\wedge q\notin F_{1}\rightarrow \delta (q,a)={\delta }_{1}(q,a)$
    $a\neq \epsilon \wedge q\in F_{1}\rightarrow \delta (q,a)={\delta }_{1}(q,a)$
    $a=\epsilon \wedge q\in F_{1}\rightarrow \delta (q,a)={\delta }_{1}(q,a)\cup \{q_{2}\}$
    $q\in Q_{2}\rightarrow \delta (q,a)={\delta }_{2}(q,a)$

### Caso 6: R = A*

Se R = A*, e A é uma expressão regular, construa o seguinte AFN N para reconhecer L(R), a partir do AFN J que reconhece A, respectivamente: Sejam
    $J=(Q_{1},\Sigma ,{\delta }_{1},q_{1},F_{1})$
Então,
    $N=(Q_{1}\cup \{q_{0}\}_{2},\Sigma ,{\delta },q_{0},F_{1}\cup \{q_{0}\})$
Tal que $\delta$ é:
    $q\in Q_{1}\wedge q\notin F_{1}\rightarrow \delta (q,a)={\delta }_{1}(q,a)$
    $a\neq \epsilon \wedge q\in F_{1}\rightarrow \delta (q,a)={\delta }_{1}(q,a)$
    $a=\epsilon \wedge q\in F_{1}\rightarrow \delta (q,a)={\delta }_{1}(q,a)\cup \{q_{1}\}$
    $q=q_{0}\wedge a=\epsilon \rightarrow \delta (q,a)=\{q_{1}\}$
    $q=q_{0}\wedge a\neq \epsilon \rightarrow \delta (q,a)=\emptyset$

## De AFN para AFD

Seja o AFN $N=(Q,\Sigma ,{\delta },q_{0},F)$ e o AFD $D=(Q',\Sigma ,{\delta }'_{1},q_{0}',F')$. Para convertermos o AFN N para o AFD D, temos quatro casos mais simples, onde setas $var\epsilon$ não são levadas em consideração:
    $Q'=P(Q)$
Todo estado de D é um conjunto de estados de N, sendo P(Q) o conjunto de subconjuntos de Q.
    $\delta '(R,a)=\bigcup _{r\in R}\delta (r,a)$
Ou seja, $\delta '$ é a união dos conjuntos $\delta (r,a)$ para todo r pertencente a R.
    $q_{0}'={q_{0}}$
D começa no estado correspondente à coleção contendo somente o estado inicial de N.
F' = {R $\epsilon$ Q' | R contém um estado de aceitação de N} A máquina D aceita se um dos possíveis estados nos quais N poderia estar nesse ponto é um estado de aceitação.
Para considerar as setas $\varepsilon$, é preciso fixar um pouco mais de notação. Para qualquer estado R de D, definimos E(R) como a coleção de estados que podem ser atingidos a partir de R indo somente ao longo de setas $\varepsilon$, incluindo os próprios membros de R. Formalmente, para R $\subseteq$ Q seja E(R) = {q | q pode ser atingido a partir de R viajando-se ao longo de 0 ou mais setas $\varepsilon$}. Então modificamos a função de transição de D para colocar dedos adicionais sobre todos os estados que podem ser atingidos indo ao longo de setas $\varepsilon$ após cada passo. Substituindo $\delta (r,a)$ por $E(\delta (r,a))$ dá esse efeito. Consequentemente, $\delta (R,a)'$ = {q $\in$ Q | $q\in E(\sigma (r,a)$) para algum r $\in$ R}.
Adicionalmente, precisamos modificar o estado inicial de D para mover os dedos inicialmente para todos os estados possíveis que podem ser atingidos a partir do estado inicial de N ao longo das setas $\varepsilon$. Mundando $q_{0}'$ para $E(\{q_{0}\})$ dá esse efeito. Agora completamos a construção do AFD D que simula o AFN N.