Propriedades de Decisão para Linguagens Regulares

Prévia do material em texto

PROPRIEDADES DE DECISÃO 
PARA LINGUAGENS REGULARES 
Marcelo Guerra 
INTRODUÇÃO 
 Responderemos a importantes questões sobre 
linguagens regulares. 
 Como formular uma questão sobre uma linguagem? 
 Note que uma linguagem típica é infinita  a 
pergunta a ser formulada não pode exigir a inspeção 
de todos os elementos de um conjunto infinito! 
 Solução: apresentar uma linguagem por meio de uma 
de suas representações finitas: DFA, NFA, e-NFA ou 
uma expressão regular. 
INTRODUÇÃO 
 Formular questões sobre linguagens regulares - 
questionamos a respeito de uma representação 
finita. 
 autômato ou expressão regular – são capazes de 
representar apenas linguagens regulares e nunca 
uma linguagem arbitrária. 
 Apesar de termos representações finitas para 
outros tipos de linguagens, apenas as regulares 
tem somente problemas decidíveis. 
 
INTRODUÇÃO 
 Algumas questões fundamentais: 
 
1. A linguagem é vazia? 
 
2. Um determinado string w pertence à linguagem? 
 
3. Duas descrições de uma linguagem realmente 
descrevem a mesma linguagem? 
 Equivalência de linguagens. 
 
1. TESTANDO SE UMA LINGUAGEM É VAZIA 
TESTANDO SE UMA LINGUAGEM É VAZIA 
 “L é vazia?” Parece ser óbvia: 
 ∅ é vazia e todas as outras linguagens não o são 
 
 Porém, encontrar a resposta pode ser mais 
complicado: 
 
 Dada uma representação para L, precisamos saber se 
essa representação denota a linguagem ∅. 
TESTANDO SE UMA LINGUAGEM É VAZIA 
 Se a representação é qualquer tipo de autômato 
finito: 
 
 a questão do caráter vazio se resume a saber se 
existe um caminho desde o estado inicial até um 
estado de aceitação. 
 Caso positivo, a linguagem é não vazia. 
 Se todos os estados de aceitação estiverem 
desconectados do estado inicial, a linguagem é vazia. 
 
TESTANDO SE UMA LINGUAGEM É VAZIA – 
AUTÔMATO FINITO 
 
 Corresponde a testar se é possível alcançar um 
estado de aceitação a partir do estado inicial do 
autômato. 
 Instância simples do problema da acessibilidade em 
grafos. 
 Semelhante ao ε-fechamento. 
 
TESTANDO SE UMA LINGUAGEM É VAZIA 
 O algoritmo recursivo é o seguinte: 
 
 Base: o estado inicial é alcançável a partir do 
estado inicial. 
 
 Indução: 
 Se o estado q é alcançável a partir do estado inicial e 
 Se existir um arco de q até p com qualquer rótulo, 
então p é alcançável. 
 
TESTANDO SE UMA LINGUAGEM É VAZIA 
 Assim, podemos calcular o conjunto de estados 
alcançáveis. 
 
 Se qualquer estado de aceitação estiver entre eles, 
então, a linguagem não é vazia. 
 
 Caso contrário, a resposta é sim, vazia. 
 
 Se a linguagem é representada por uma exp reg, 
devemos converte-la em um ε-AFN e prosseguir como 
descrito anteriormente. 
TESTANDO SE UMA LINGUAGEM É VAZIA 
PARA EXPRESSÕES REGULARES 
 Também podemos examinar uma exp reg 
diretamente para testar se a linguagem denotada é 
vazia: 
 
 Se a expressão não contiver nenhuma ocorrência de ∅, 
então a linguagem certamente não é vazia. 
 
 Se existirem ∅’s a linguagem pode ou não ser vazia, o 
que é testado pelo algoritmo a seguir: 
TESTANDO SE UMA LINGUAGEM É VAZIA 
PARA EXPRESSÕES REGULARES 
 Base: ∅ denota a linguagem vazia; ε e a para qualquer 
símbolo de entrada a não a denotam. 
 
 Indução: suponha que R seja uma exp reg, então 
devemos considerar os casos: 
1. R = R1 + R2. Então L(R) é vazia sse L(R1) e L(R2) forem 
ambas vazias. 
2. R = R1R2. Então L(R) é vazia sse L(R1) ou L(R2) for vazia. 
3. R = R1*. Então L(R) não é vazia pois ela sempre inclui ε. 
4. R = (R1). Então L(R) é vazia sse L(R1) for vazia, pois ela 
denota a mesma linguagem. 
2. TESTANDO A PERTINÊNCIA A UMA 
LINGUAGEM REGULAR 
TESTANDO A PERTINÊNCIA A UMA 
LINGUAGEM REGULAR 
 Dados um string w e uma linguagem regular L, 
w  L? 
 Embora w seja dada explicitamente, L é representada por 
um autômato ou uma exp reg. 
 
 Se L for representada por um AFD, simule o AFD 
processando w como entrada: 
 se o AFD estiver num estado de aceitação ao fim da 
leitura, a resposta é “sim”. 
 Caso contrário, a resposta é não. 
TESTANDO A PERTINÊNCIA A UMA 
LINGUAGEM REGULAR 
 
 Se L estiver representada de outra maneira, 
devemos convertê-la em um AFD e executar o teste 
anterior. 
 
 Se a representação for um AFN, o mais simples é 
simular sua execução diretamente – a complexidade 
é menor. 
 
 Se a representação for uma exp reg, podemos 
convertê-la em um AFN com transições vazias e 
efetuar a simulação anterior. 
 
3. EQUIVALÊNCIA E MINIMIZAÇÃO DE 
AUTÔMATOS 
EQUIVALÊNCIA E MINIMIZAÇÃO DE 
AUTÔMATOS 
 
 A questão de saber se duas descrições de linguagens 
regulares representam a mesma linguagem tem uma 
resposta bastante elaborada. 
 
 Veremos o teste de equivalência entre dois descritores 
de linguagens regulares. 
 Conseqüência importante: existe uma maneira de 
minimizar um AFD. 
 O AFD resultante é único: os demais serão equivalentes, 
bastando renomear os estados para obter o mesmo AFD. 
COMO TESTAR A EQUIVALÊNCIA DE 
ESTADOS 
 Formulamos a questão sobre os estados de um único 
AFD: 
 dois estados distintos p e q podem ser trocados por um 
único estado que se comporte como p e q? 
 
 Estados distintos p e q são equivalentes quando: 
 Para todo string w, δ*(p,w) é um estado de aceitação sse 
δ*(q,w) é um estado de aceitação. 
 Em outras palavras, é impossível encontrar a diferença entre 
esses estados. 
 OBS: não há exigência que p e q alcancem o mesmo estado 
processando w, apenas que sejam de aceitação. 
COMO TESTAR A EQUIVALÊNCIA DE 
ESTADOS 
 Se dois estados não são equivalentes, dizemos que 
são distinguíveis. 
 Um estado p é distinguível de um estado q se existe pelo 
menos um string w tal que um estado entre δ*(p,w) e 
δ*(q,w) é de aceitação e o outro é de não-aceitação. 
 
EXEMPLO 
 
 C e G são distinguíveis por ε. 
 Considere os estados A e G: 
 O string ε não os distingue, pois ambos são de não-aceitação. 
 0 também não os distingue, pois eles vão para os estados B e G, 
respectivamente, de não-aceitação. 
 1 também não distingue A de G, pois vão para F e E, de não 
aceitação. 
 O string 01 os distingue, pois os leva para C e E, onde o primeiro é 
de aceitação. 
 
EXEMPLO 
 
 Considere os estados A e E: 
 O string ε não os distingue, pois ambos são de não-aceitação 
 Para a entrada 1 ambos vão para F, qualquer cadeia que comece 
com 1 não os distinguirá 
 Para a entrada 0 eles vão para os estados B e H, 
respectivamente, de não-aceitação 
 Em B e H ambos vão para C em 1 e para G em 0, portanto, para 
nenhum string é possível distinguir A de E 
 A e E são equivalentes 
 
MINIMIZAÇÃO DE ESTADOS 
 Uma conseqüência do teste de equivalência é que 
podemos encontrar AFD’s equivalentes que 
contenham um número mínimo de estados. 
 
 Um autômato finito, para ser minimizado, 
precisa satisfazer os seguintes pré-requisitos: 
 
 Precisa ser um AFD; 
 Não pode ter estados inacessíveis; 
 d deve ser total. 
MINIMIZAÇÃO DE ESTADOS 
 Caso o autômato não satisfaça a alguns dos pré-
requisitos, é necessário gerar um autômato 
equivalente: 
 
 Efetuar conversão de AFNs para AFD; 
 Eliminar os estados inacessíveis e suas 
correspondentes transições; 
 Transformar d em total, introduzindo um estado de 
morte e incluindo as transições não previstas para 
este estado. 
ALGORITMO DE PREENCHIMENTO DE 
TABELA1. Construir uma tabela relacionando estados 
diferentes, onde cada par de estados ocorre somente 
uma vez; 
ALGORITMO DE PREENCHIMENTO DE 
TABELA 
2. Marcar estados obviamente não equivalentes: marcar 
pares de estados finais com estados não finais; 
3. Marcar estados não equivalentes. Para cada par {q, q’} 
e para cada símbolo a  S, suponha que d(q, a) = p e 
d(q’, a) = p’ e: 
a) Se p = p’, então q é equivalente a q’ para a e não deve ser 
marcado; 
b) Se p  p’ e o par {p, p’} não está marcado, então {q, q’} é 
incluído em uma lista para posterior análise; 
c) Se p  p’ e o par {p, p’} está marcado: 
 {q, q’} não é equivalente e deve ser marcado; 
 Se {q,q’} encabeça uma lista de pares, então marcar todos os pares 
da lista. 
 
ALGORITMO DE PREENCHIMENTO DE 
TABELA 
4. Unificar os estados equivalentes. Os estados dos pares 
não marcados são equivalentes e podem ser unificados 
como segue: 
 A equivalência é transitiva; 
 Pares de estados não finais equivalentes podem ser 
unificados como um único estado não final; 
 Pares de estados finais equivalentes podem ser unificados 
como um único estado final; 
 Se algum dos estados equivalentes é inicial, então o 
correspondente estado unificado é inicial. 
5. Excluir estados inúteis. Um estado q é inútil se é não 
final e a partir de q não é possível atingir um estado 
final. 
 O estado de morte é sempre inútil. 
EXEMPLO 
1. Construção da 
tabela 
2. Marcação dos pares 
de estados finais 
com não finais. 
q0 q1 q2 q3 q4 
q1 X 
q2 X 
q3 X X 
q4 X X 
q5 X X X 
EXEMPLO 
3. Análise dos pares 
não marcados 
(representados 
por – ). 
q0 q1 q2 q3 q4 
q1 X 
q2 X - 
q3 - X X 
q4 X - - X 
q5 - X X - X 
EXEMPLO 
 Par {q0, q3}: 
 d(q0, a) = q2 d(q0, b) = q1 
 d(q3, a) = q4 d(q3, b) = q2 
 
 como {q1, q2} e {q2, q4} são 
não marcados (-), então {q0, 
q3} é incluído nas listas 
encabeçadas por {q1, q2} e 
{q2, q4}: 
 
 [{q1, q2}, {q0, q3}] 
 [{q2, q4}, {q0, q3}] 
q0 q1 q2 q3 q4 
q1 X 
q2 X - 
q3 - X X 
q4 X - - X 
q5 - X X - X 
Passo 3.b do algoritmo 
EXEMPLO 
 Par {q0, q5}: 
 d(q0, a) = q2 d(q0, b) = q1 
 d(q5, a) = q2 d(q5, b) = q4 
 
 O par {q2, q2} está fora da 
tabela e não será usado para 
análise. 
 Como {q1, q4} é não marcado (-), 
então {q0, q5} é incluído na lista 
encabeçada por {q1, q4}: 
 
 [{q1, q2}, {q0, q3}] 
 [{q2, q4}, {q0, q3}] 
 [{q1, q4}, {q0, q5}] 
q0 q1 q2 q3 q4 
q1 X 
q2 X - 
q3 - X X 
q4 X - - X 
q5 - X X - X 
Passo 3.b do algoritmo 
EXEMPLO 
 Par {q1, q2}: 
 d(q1, a) = q1 d(q1, b) = q0 
 d(q2, a) = q3 d(q2, b) = q5 
 
 como {q1, q3} é marcado (X), 
então {q1, q2} também é 
marcado (+). Como {q1, q2} 
encabeça uma lista, {q0, q3} 
também é marcado (+). 
 
 [{q1, q2}, {q0, q3}] 
 [{q2, q4}, {q0, q3}] 
 [{q1, q4}, {q0, q5}] 
 
q0 q1 q2 q3 q4 
q1 X 
q2 X + 
q3 + X X 
q4 X - - X 
q5 - X X - X 
Passo 3.c do algoritmo 
EXEMPLO 
 Par {q1, q4}: 
 d(q1, a) = q1 d(q1, b) = q0 
 d(q4, a) = q5 d(q4, b) = q3 
 
 como {q1, q5} é marcado (X) e 
{q0, q3} também é marcado 
(+), então {q1, q4} também é 
marcado (+). Como {q1, q4} 
encabeça uma lista, {q0, q5} 
também é marcado (+). 
 
 [{q1, q2}, {q0, q3}] 
 [{q2, q4}, {q0, q3}] 
 [{q1, q4}, {q0, q5}] 
 
q0 q1 q2 q3 q4 
q1 X 
q2 X + 
q3 + X X 
q4 X + - X 
q5 + X X - X 
Passo 3.c do algoritmo 
EXEMPLO 
 Par {q2, q4}: 
 d(q2, a) = q3 d(q2, b) = q5 
 d(q4, a) = q5 d(q4, b) = q3 
 
 como {q3, q5} é não marcado 
(-), {q2, q4} é incluído na lista 
encabeçada por {q3, q5}: 
 
 [{q1, q2}, {q0, q3}] 
 [{q2, q4}, {q0, q3}] 
 [{q1, q4}, {q0, q5}] 
 [{q3, q5}, {q2, q4}] 
q0 q1 q2 q3 q4 
q1 X 
q2 X + 
q3 + X X 
q4 X + - X 
q5 + X X - X 
Passo 3.b do algoritmo 
EXEMPLO 
 Par {q3, q5}: 
 d(q3, a) = q4 d(q3, b) = q2 
 d(q5, a) = q2 d(q5, b) = q4 
 
 como {q2, q4} é não marcado (-), 
{q3, q5} é incluído na lista 
encabeçada por {q2, q4}: 
 
 [{q1, q2}, {q0, q3}] 
 [{q2, q4}, {q0, q3}] 
 [{q1, q4}, {q0, q5}] 
 
 [{q2, q4}, {q0, q3}, {q3, q5}] 
q0 q1 q2 q3 q4 
q1 X 
q2 X + 
q3 + X X 
q4 X + - X 
q5 + X X - X 
Passo 3.b do algoritmo 
EXEMPLO 
4. Unificação dos 
estados equivalentes: 
como os estados {q2, 
q4} e {q3, q5} são não 
marcados, unifica-se: 
 q2 e q4: unificação 
dos estados não 
finais: q24 
 q3 e q5: unificação 
dos estados finais: 
q35 
 O resultado final é 
mostrado na figura 
ao lado. 
RESUMO: AUTÔMATOS EQUIVALENTES 
Versão original: Versão minimizada: