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.

Referências

• Sipser, Michael (1997). Introduction to the Theory of Computation. Boston: PWS. ISBN 0-534-94728-X . 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

• Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001). Introduction to Automata Theory, Languages, and Computation 2 ed. [S.l.]: Addison Wesley. ISBN 0-201-44124-1. Consultado em 19 de novembro de 2012