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. *)( 1kkkR 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*