Saltar para o conteúdo

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

Origem: Wikipédia, a enciclopédia livre.

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 | editar código-fonte]

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 | editar código-fonte]

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

Caso 2: R = ε

[editar | editar código-fonte]

Se R = ε, o seguinte AFN reconhece :

Caso 3: R = {}

[editar | editar código-fonte]

Se R = , o seguinte AFN reconhece :

Caso 4: R = A U B

[editar | editar código-fonte]

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 | editar código-fonte]

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 | editar código-fonte]

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 | editar código-fonte]

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.

  • 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