Conversão de Expressões Regulares em Autômatos

Prévia do material em texto

CONVERSÃO DE EXPRESSÕES 
REGULARES EM AUTÔMATOS 
Marcelo Guerra 
INTRODUÇÃO 
 Veremos que qualquer linguagem L(R) de uma 
expressão regular R também é L(E) para algum 
ε-AFN E 
AFN 
AFD 
-AFN 
ER 
TEOREMA 3.7 
 Toda linguagem definida por uma expressão 
regular também é definida por um autômato 
finito. 
 A prova será feita por indução estrutural: 
 
 Mostramos como construir autômatos para os símbolos de 
base isoladamente; 
 
 Em seguida, mostramos como combinar esses autômatos em 
autômatos maiores que aceitam a união, concatenação e o 
fechamento. 
 
 Todos os autômatos gerados serão ε-AFN´s com um único 
estado de aceitação. 
PROVA 
 Suponha que L = L(R) para uma exp reg R. 
Mostramos que L = L(E) para algum ε-AFN com: 
 
1. Exatamente um estado de aceitação; 
2. Nenhum arco chega no estado inicial; 
3. Nenhum arco sai do estado de aceitação. 
 
 A prova por indução estrutural sobre R segue a 
definição indutiva de exp reg: 
 
BASE 
 Base: há três etapas de base correspondentes às figuras 
abaixo: correspondentes às linguagens ε,  e a, 
respectivamente: 
 
 
a 
ε 
INDUÇÃO 
 Supomos que a hipótese é verdadeira para as sub-
expressões imediatas de uma dada exp reg, 
 
 As linguagens destas sub-expressões são as linguagens dos 
ε-AFN´s com um único estado de aceitação. 
 
 Temos 4 casos: 
 A exp é R + S para exp menores R e S 
 A exp é RS 
 A expressão é R* 
 A expressão é (R) 
INDUÇÃO 
R 
ε ε 
S 
ε 
ε 
S R 
ε 
R ε 
ε 
ε 
ε 
EXEMPLO 
 Converter a exp reg (0+1)*1(0+1)1 em um 
autômato finito não determinístico. 
 
1. Construir um autômato para 0+1 
2. Construção do fechamento estrela 
3. Construção da concatenação 
EXEMPLO 
 Converter a exp reg (0+1)*1(0+1)1 em um 
autômato finito não determinístico. 
 
1. Construir um autômato para 0+1 
 
 
 
 
 
2. Construção do fechamento estrela 
3. Construção da concatenação 
R 
ε ε 
S 
ε ε 
0 ε ε 
1 
ε ε 
EXEMPLO 
 Converter a exp reg (0+1)*1(0+1)1 em um 
autômato finito não determinístico. 
 
1. Construir um autômato para 0+1 
2. Construção do fechamento estrela 
 
 
 
 
 
3. Construção da concatenação 
0 ε ε 
1 
ε ε 
ε 
ε 
ε 
R ε ε 
ε 
ε 
0 ε ε 
1 
ε ε 
EXEMPLO 
 Converter a exp reg (0+1)*1(0+1) em um 
autômato finito não determinístico. 
 
1. Construir um autômato para 0+1 
2. Construção do fechamento estrela 
3. Construção da concatenação 
0 ε ε 
1 
ε ε 
ε 
ε 
ε 
0 ε ε 
1 
ε ε 
ε 
ε 
ε 
ε ε 1 ε 0 ε ε 
1 
ε ε 
EXEMPLO 
 Converter a exp reg (0+1)*1(0+1) em um 
autômato finito não determinístico. 
 
EXEMPLO 
 Converter a exp reg (0+1)*1(0+1) em um 
autômato finito não determinístico. 
 
0 ε ε 
1 
ε ε 
ε 
ε 
ε 
ε ε 1 ε 0 ε ε 
1 
ε ε 
C 
0,1 
A B 
1 0,1