Conversão de AFD's em Expressões Regulares por Eliminação

Prévia do material em texto

CONVERSÃO DE AFD’S EM 
EXPRESSÕES REGULARES POR 
ELIMINAÇÃO DE ESTADOS 
Marcelo Guerra 
INTRODUÇÃO 
 Na aula anterior, vimos um método para 
transformar um AFD em uma expressão regular que 
sempre funciona. 
 Ele não depende do determinismo e pode ser 
aplicado também a um AFN ou ε-AFN. 
 Porém, a construção da expressão regular é 
dispendiosa: 
Para um autômato com n estados, temos de 
construir cerca de n3 expressões com até 4n símbolos. 
 
INTRODUÇÃO 
 Veremos uma abordagem semelhante que evita a 
duplicação de trabalho. 
 
 Por exemplo, todas as expressões com sobrescrito (k) 
na construção do Teorema 3.4 utilizam a mesma 
expressão 
 O trabalho de escrever essa expressão é repetido n2 
vezes. 
 
 A nova abordagem para construção de expressões 
regulares que estudaremos agora envolve a 
eliminação de estados. 
*)( 1kkkR
ELIMINAÇÃO DE ESTADOS 
 Metodologia: 
 
 Eliminar um estado s implica em suprimir todos os 
caminhos que passam por s. 
 
 Os rótulos de algum caminho de q a p passando por s 
são incluídos em um arco direto de q até p. 
 Note que esses rótulos podem agora conter strings. 
 
 Esses rótulos são representados na forma de uma 
expressão regular. 
 
 
ELIMINAÇÃO DE ESTADOS 
 Teremos então autômatos com expressões 
regulares rotulando seus arcos. 
 
 A linguagem correspondente é a união sobre 
todos os caminhos desde o estado inicial até um 
estado de aceitação da linguagem formada pela 
concatenação das linguagens das expressões 
regulares ao longo desse caminho. 
 
GENERALIZAÇÃO DE UM AUTÔMATO 
 O estado genérico s está prestes 
a ser eliminado; 
 Os estados de q1 a qk são seus 
predecessores; 
 Os estados de p1 a pm seus 
sucessores; 
 Q1 a Qk representam exp reg’s 
de um estado qi para s; P1 a Pm 
de s para pj; 
 S é a exp reg que corresponde a 
um loop em s. 
 Existe uma exp reg Rij no arco 
de qi até pj, para todo i e todo j. 
q1 
qk 
s 
pm 
p1 
.
.
. 
.
.
. 
R11 
Rkm 
S 
Q1 
Qk 
Rk1 
R1m 
P1 
Pm 
ELIMINAÇÃO DE S 
q1 
qk pm 
p1 
.
.
. 
.
.
. 
R11 + Q1S*P1 
Rkm +QkS*Pm 
q1 
qk 
s 
pm 
p1 
.
.
. 
.
.
. 
R11 
Rkm 
S 
Q1 
Qk 
Rk1 
R1m 
P1 
Pm 
INTRODUÇÃO DOS RÓTULOS 
 Para cada predecessor qi e 
para cada sucessor pj de s 
introduzimos uma exp reg 
que representa todos os 
caminhos de q para p 
passando por s 
(possivelmente com loops 
em s). 
 
 A expressão para esses 
caminhos é QiS*Pj que é 
adicionada ao arco que vai 
diretamente de qi para pj 
através do operador de 
união (+). 
 Se não houver tal arco, então 
ele deve ser criado com a exp 
reg  
 
q1 
qk pm 
p1 
.
.
. 
.
.
. 
R11 + Q1S*P1 
Rkm +QkS*Pm 
ESTRATÉGIA DE CONSTRUÇÃO 
 Para cada estado de aceitação q, aplique o 
processo de redução de estados. 
 
1. Obtenha o autômato equivalente com rótulos de 
expressões regulares nos arcos. 
 
2. Elimine todos os estados, exceto q0 e q. 
 
 
ESTRATÉGIA DE CONSTRUÇÃO 
 Se q  q0 obteremos um autômato de dois estados 
semelhante ao seguinte: 
 
 
 
 
 
 
 A expressão regular para as strings aceitas podem 
ser descritas de várias maneiras, por exemplo: 
S 
T 
U 
R 
 (R + SU*T)*SU* 
 
ESTRATÉGIA DE CONSTRUÇÃO 
 Se o estado inicial for também um estado de 
aceitação, obteremos um autômato com um único 
estado, cuja exp reg é R*. 
 
 
 
 
 A exp reg desejada é a soma (união) de todas as 
expressões derivadas dos autômatos reduzidos 
correspondentes a cada estado de aceitação pelas 
regras anteriores. 
R 
EXEMPLO 
 O AFN que aceita strings em S={0,1} que tem um 
símbolo 1 a duas ou três posições a partir do seu 
final. 
 
 
 
 
C 
0,1 
A B D 
1 0,1 0,1 
 O primeiro passo é convertê-lo num autômato com 
rótulos formados por expressões regulares. 
 
 Como ainda não fizemos eliminações de estados, 
trocamos os rótulos 0,1 pela exp reg equivalente: 0+1. 
EXEMPLO 
 
 
 
 
 Primeiro vamos eliminar o estado B – não é inicial nem de 
aceitação. 
 
 Predecessor A, Sucessor C 
 
 Segundo o diagrama geral Q1 = 1,P1=0+1, R11 = , S =  
 
 A exp do arco de A para C é +1*(0+1), que pode ser 
simplificada para 1(0+1). 
C 
0+1 
A B D 
1 0+1 0+1 
q1 
s 
p1 
R11 
S Q1 
P1 
q1 p1 
R11 + Q1S*P1 
EXEMPLO 
 
 
 
 Devemos eliminar os estados C e D em reduções 
separadas. 
 
 Na eliminação de C: Q1 = 1(0+1), P1=0+1, R11 = , S = , 
obtemos +1(0+1)*(0+1) = 1(1+0)(1+0) 
 
 
C 
0+1 
A D 
1(0+1) 0+1 
0+1 
A D 
1(0+1)(0+1) 
q1 
s 
p1 
R11 
S Q1 
P1 
q1 p1 
R11 + Q1S*P1 
EXEMPLO 
 
 
 
 
 Em termos do autômato genérico de dois estados, as 
expressões regulares são R = 0+1, S = 1(0+1)(0+1), T = , 
U =  
 
 A exp genérica é, neste caso, simplificada de 
(R+SU*T)*SU* para R*S e obtemos (0+1)*1(0+1)(0+1) 
 
S 
T 
U 
R 
0+1 
A D 
1(0+1)(0+1) 
EXEMPLO 
 Agora devemos voltar e considerar a eliminação de D antes 
de C: 
 
 
 
 
 Como D não tem sucessores, de acordo com o diagrama geral, 
ele será eliminado junto com o arco de C até D. 
 
 
 
 
 De maneira similar ao caso anterior, a expressão 
correspondente é (0+1)*1(0+1). 
 
C 
0+1 
A D 
1(0+1) 0+1 
C 
0+1 
A 
1(0+1) 
EXEMPLO 
 Falta apenas unir as expressões para obter o 
resultado final, que é: 
 
 (0+1)*1(0+1) + (0+1)*1(0+1)(0+1) 
 
C 
0+1 
A B D 
1 0+1 0+1 
Eliminando D Eliminando C 
EXERCÍCIO 
 Utilizando o método da eliminação, escreva a 
expressão regular que descreve a linguagem aceita 
pelo autômato abaixo: 
EXERCÍCIO 
 Utilizando o método da eliminação, escreva a 
expressão regular que descreve a linguagem aceita 
pelo autômato abaixo: 
S 
T 
U 
R 
 (R + SU*T)*SU* 
 
 (1 + 01*0)*01*