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

editar

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

editar

Seja R = a, para algum a em Σ. Então basta construirmos o seguinte AFN que reconhece  :

 
 
 
 

Caso 2: R = ε

editar

Se R = ε, o seguinte AFN reconhece  :

 
 
 
 

Caso 3: R = {}

editar

Se R =  , o seguinte AFN reconhece  :

 
 
 
 

Caso 4: R = A U B

editar

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

 
 

Então,

 

Tal que

 

e

 

Caso 5: R = A o B

editar

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

 
 

Então,

 

Tal que   é:

 
 
 
 

Caso 6: R = A*

editar

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

 

Então,

 

Tal que   é:

 
 
 
 
 

De AFN para AFD

editar

Seja o AFN   e o AFD  . Para convertermos o AFN N para o AFD D, temos quatro casos mais simples, onde setas   não são levadas em consideração:

 

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


 

Ou seja,   é a união dos conjuntos   para todo r pertencente a R.


 

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  , é 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  , incluindo os próprios membros de R. Formalmente, para R   Q seja E(R) = {q | q pode ser atingido a partir de R viajando-se ao longo de 0 ou mais setas  }. 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   após cada passo. Substituindo   por   dá esse efeito. Consequentemente,   = {q   Q |  ) para algum r   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  . Mundando   para   dá esse efeito. Agora completamos a construção do AFD D que simula o AFN N.

Referências

editar
  • 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