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)=\mathrm{\varnothing },\mathrm{\forall }q\in Q,\mathrm{\forall }a\in \mathrm{\Sigma }$

Caso 3: R = {}

Se R = $\mathrm{\varnothing }$, o seguinte AFN reconhece $L(R)$:

$Q=\{q_1\}$

$q_0=q_1$

$q_{acc}=\mathrm{\varnothing }$

$\delta (q,a)=\mathrm{\varnothing },\mathrm{\forall }q\in Q,\mathrm{\forall }a\in \mathrm{\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,\mathrm{\Sigma },{\delta }_1,q_1,F_1)$

$K=(Q_2,\mathrm{\Sigma },{\delta }_2,q_2,F_2)$

Então,

$N=(Q_1\times Q_2,\mathrm{\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,\mathrm{\Sigma },{\delta }_1,q_1,F_1)$

$K=(Q_2,\mathrm{\Sigma },{\delta }_2,q_2,F_2)$

Então,

$N=(Q_1\cup Q_2,\mathrm{\Sigma },\delta ,q_1,F_2)$

Tal que $\delta$ é:

$q\in Q_1\wedge q\notin F_1\to \delta (q,a)={\delta }_1(q,a)$

$a\ne ϵ\wedge q\in F_1\to \delta (q,a)={\delta }_1(q,a)$

$a=ϵ\wedge q\in F_1\to \delta (q,a)={\delta }_1(q,a)\cup \{q_2\}$

$q\in Q_2\to \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,\mathrm{\Sigma },{\delta }_1,q_1,F_1)$

Então,

$N=(Q_1\cup \{q_0{\}}_2,\mathrm{\Sigma },\delta ,q_0,F_1\cup \{q_0\})$

Tal que $\delta$ é:

$q\in Q_1\wedge q\notin F_1\to \delta (q,a)={\delta }_1(q,a)$

$a\ne ϵ\wedge q\in F_1\to \delta (q,a)={\delta }_1(q,a)$

$a=ϵ\wedge q\in F_1\to \delta (q,a)={\delta }_1(q,a)\cup \{q_1\}$

$q=q_0\wedge a=ϵ\to \delta (q,a)=\{q_1\}$

$q=q_0\wedge a\ne ϵ\to \delta (q,a)=\mathrm{\varnothing }$

De AFN para AFD

Seja o AFN $N=(Q,\mathrm{\Sigma },\delta ,q_0,F)$ e o AFD $D=(Q^{\prime },\mathrm{\Sigma },\delta {\text{'}}_1,{q_0}^{\prime },F^{\prime })$. Para convertermos o AFN N para o AFD D, temos quatro casos mais simples, onde setas $varϵ$ não são levadas em consideração:

$Q^{\prime }=P(Q)$

Todo estado de D é um conjunto de estados de N, sendo P(Q) o conjunto de subconjuntos de Q.

${\delta }^{\prime }(R,a)=\bigcup _{r\in R}\delta (r,a)$

Ou seja, ${\delta }^{\prime }$ é a união dos conjuntos $\delta (r,a)$ para todo r pertencente a R.

${q_0}^{\prime }=q_0$

D começa no estado correspondente à coleção contendo somente o estado inicial de N.

F' = {R $ϵ$ 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 $\epsilon$, é 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 $\epsilon$, 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 $\epsilon$}. 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 $\epsilon$ após cada passo. Substituindo $\delta (r,a)$ por $E(\delta (r,a))$ dá esse efeito. Consequentemente, $\delta (R,a{)}^{\prime }$ = {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 $\epsilon$. Mundando ${q_0}^{\prime }$ para $E(\{q_0\})$ dá esse efeito. Agora completamos a construção do AFD D que simula o AFN N.

Referências

• Predefinição:Citar livro. Section 1.1: Finite Automata, pp. 31–47. Subsection "Decidable Problems Concerning Regular Languages" of section 4.1: Decidable Languages, pp. 152–155.4.4 DFA can accept only regular language

• Predefinição:Citar livro