Propriedades de Fechamento das Linguagens Regulares

Prévia do material em texto

PROPRIEDADES DE 
FECHAMENTO DAS LINGUAGENS 
REGULARES 
Marcelo Guerra 
INTRODUÇÃO 
 Veremos diversos teoremas sobre as operações 
fechadas sobre linguagens regulares. 
 
 Provar diversos teoremas da forma: “Se certas 
linguagens são regulares, e uma linguagem L é 
formada a partir delas por certas operações, então L 
também é regular.” 
 
 Esses teoremas são chamados de propriedades de 
fechamento das LR, pois mostra que a classe de LR é 
fechada sobre a operação mencionada. 
INTRODUÇÃO 
 Expressam que quando uma linguagem é regular, 
certas linguagens relacionadas também o são. 
 
 Mostram a utilidade das várias representações 
equivalentes de uma LR (autômatos e ER) e o quão 
são complementares. 
 Muitas vezes uma representação é melhor do que a outra 
para provar uma propriedade de fechamento. 
INTRODUÇÃO 
 As operações fechadas para linguagens regulares são: 
 
 União entre duas linguagens regulares. 
 Interseção entre duas linguagens regulares. 
 Complemento de uma linguagem regular. 
 Diferença entre duas linguagens regulares. 
 O reverso de uma linguagem regular. 
 O fechamento estrela de uma linguagem regular. 
 A concatenação de duas linguagens regulares. 
 Um homomorfismo de uma linguagem regular. 
 O homomorfismo inverso de uma linguagem regular. 
 
FECHAMENTO SOB OPERAÇÕES 
BOOLEANAS 
 As operações booleanas de interseção, união e 
complemento são fechadas para linguagens 
regulares: 
 Sejam L e M linguagens sobre o alfabeto Σ. Então 
 
1. L  M é a linguagem que contém todos os strings de 
L e de M ou ambos. 
 
2. L ∩ M é a linguagem que contém todos os que estão 
simultaneamente em L e M 
 
3. é o conjunto de strings em Σ * que não estão em L. 
FECHAMENTO SOB UNIÃO 
 Se L e M são linguagens regulares, então L  M 
também é. 
 
 Prova: 
 
 Como L e M são regulares, há expressões regulares que as 
descrevem. 
 
 Se L = L(R) e M = L(S), então 
 
 L  M = L(R+S), pela definição do operador + para 
expressões regulares. 
FECHAMENTO SOB COMPLEMENTO 
 Se L é uma linguagem regular sobre um alfabeto Σ, 
então = Σ* - L é uma linguagem regular. 
 
 A prova para a operação de união foi fácil devido à 
representação por expressão regular. 
 
 Para fazer a mesma prova para o complemento, seria 
necessário construir a expressão regular que denota o 
complemento a partir de uma expressão regular dada. 
 
 Como calcular o complemento de expressão regular? 
 
 Artifício: Encontre um autômato que aceite o complemento da 
linguagem. 
FECHAMENTO SOB COMPLEMENTO -
CONVERSÃO 
 Começando com uma expressão regular, podemos 
encontrar uma expressão regular para seu 
complemento da seguinte forma: 
 
1. Converta a expressão regular em um ε-AFN. 
 
2. Converta esse ε-AFN em um AFD usando a construção 
de conjuntos. 
 
3. Complemente os estados de aceitação desse AFD. 
 
4. Transforme o AFD complemento de novo em uma 
expressão regular através da eliminação de estados. 
FECHAMENTO SOB COMPLEMENTO-
CONVERSÃO 
 Seja L=L(A) para algum AFD A=(Q,Σ,δ,q0,F), então 
...=L(B), onde B é o AFD(Q,Σ,δ,q0,Q-F). Isto é, B é 
exatamente igual a A, mas os estados de aceitação de 
A se tornaram os estados de não aceitação de B e 
virce-versa. 
 W está em L(B), se somente se δ(q0, w) está em Q-F, o que 
ocorre, se somente se w não está em L(A). 
 Para essa prova, é importante que δ(q0, w) seja sempre 
algum estado. 
 
^ 
^ 
FECHAMENTO SOB COMPLEMENTO-
CONVERSÃO (EXEMPLO) 
 Seja o autômato da figura que aceita todos os strings 
de 0s e 1s que terminam em 01, que também pode ser 
representado pela ER: (0+1)*01. 
{q0, q1} {q0} {q0, q2} 
Início 0 1 
1 0 
0 
1 
FECHAMENTO SOB COMPLEMENTO-
CONVERSÃO (EXEMPLO) 
 O complemento desse autômato é portanto todos os 
strings de 0s e 1s que não terminam em 01. 
{q0, q1} {q0} {q0, q2} 
Início 0 1 
1 0 
0 
1 
FECHAMENTO SOB COMPLEMENTO-
CONVERSÃO (EXEMPLO) 
 Relembrando o slide 9: “Seja L=L(A) para algum AFD 
A=(Q,Σ,δ,q0,F), então =L(B), onde B é o 
AFD(Q,Σ,δ,q0,Q-F). Isto é, B é exatamente igual a A, 
mas os estados de aceitação de A se tornaram os 
estados de não aceitação de B e virce-versa.” 
{q0, q1} {q0} {q0, q2} 
Início 0 1 
1 0 
0 
1 
FECHAMENTO SOB COMPLEMENTO-
CONVERSÃO (EXEMPLO) 
{q0, q1} {q0} {q0, q2} 
Início 0 1 
1 0 
0 
1 
{q0, q1} {q0} {q0, q2} 
Início 0 1 
1 0 
0 
1 
FECHAMENTO SOB A INTERSEÇÃO 
 Se L e M são linguagens regulares, então L ∩ M 
também é. 
 
 Há duas maneiras de raciocinar sobre esse fato: 
 Efetuar a complementação e união para obter a 
intersecção. 
 
 Construir diretamente um AFD que executa os AFD’s 
das duas linguagens em paralelo. 
 Os estados do autômato A, produto de AL e AM, são pares de 
estados (p,q), onde p é um estado de AL e q um estado AM . 
 Seus estados de aceitação são aqueles pares onde ambos são 
estados de aceitação no AFD original. 
FECHAMENTO SOB A INTERSEÇÃO 
 Exemplo: 
 δ*((p,q),w) = (δL*(p,w), δM*(q,w)), de modo que A aceita 
a intersecção de L e M. 
 
FECHAMENTO SOB A DIFERENÇA 
 A diferença entre as linguagens L e M é o 
conjunto das strings que estão em L mas não 
estão em M. 
 
 Se L e M são linguagens regulares, L – M 
também o é. 
 
 As linguagens regulares também são fechadas 
sob esta operação. 
 
 A prova decorre dos teoremas que acabamos de 
demonstrar 
FECHAMENTO SOB A DIFERENÇA 
 
 Prova: 
 
 Observe que L – M = L ∩ . 
 
 e L ∩ são regulares (provado anteriormente), 
portanto, L – M é regular. 
 
 Levando em conta as provas do fechamento sob a 
interseção e o complemento, portanto, L-M também é 
regular. 
REVERSÃO 
 Teorema: Se L é uma linguagem regular, então LR 
também é. 
 
 O reverso de uma string a1a2...an é o string escrito ao 
contrário, anan-1...a1. 
 Usamos wR para representar o reverso do string w. 
 Exemplo: 0010R é 0100. 
 
 A reversão da linguagem L, escrita LR é a linguagem 
que consiste nos reversos de todos as strings de L. 
 
 A reversão é uma operação fechada para linguagem 
regular. 
REVERSÃO 
 Prova(esboço): 
 
 Seja L=L(A) para algum autômato finito A. Construímos 
um autômato para LR : 
 
1. Inverta todos os arcos no diagrama de A. 
 
2. Torne o estado inicial de A no único estado de aceitação 
no novo autômato. 
 
3. Adicione um novo estado inicial com transições vazias 
para todos os estados que seriam de aceitação em A. 
 
 O resultado é o autômato que aceita o reverso de L. 
EXEMPLO 
HOMOMORFISMOS 
 Um homomorfismo de string é uma função que 
substitui cada símbolo do string por um string 
específico. 
 
 Exemplo: 
 A função h definida por h(0) = ab e h(1) = ε é um 
homomorfismo. 
 h(0011) = abab. 
 
 Formalmente, se h é um homomorfismo sobre ∑ e 
w=a1a2...an, então h(w) = h(a1)h(a2)...(an). 
HOMOMORFISMOS 
 Podemos aplicar um homomorfismo a uma 
linguagem, aplicando-a a cada membro dela. 
 h(L) = {h(w) | w está em L} 
 
 Exemplo: 
 
 h(0) = ab e h(1) = ε. 
 Se L é a linguagem da exp reg 10*1, então h(L) = 
(ab)*. 
 
 Teorema: se L é uma linguagem regular sobre o 
alfabeto ∑, e h é um homomorfismo sobre ∑, 
então h(L) também é regular. 
 
HOMOMORFISMOS INVERSOS 
 Homomorfismos podem ser aplicados “ao 
contrário”. 
 
 Dessa forma, também são operações fechadas 
 Seja h um homomorfismo sobre ∑ para strings 
definidos em um alfabeto Τ. Seja L uma linguagem sobre o alfabeto Τ. 
 
 Então h-1(L) é o conjunto de strings w em ∑* tal que 
h(w) está em L. 
 
HOMOMORFISMOS INVERSOS 
 Exercício: Suponha que h é o homomorfismo do 
alfabeto {0, 1, 2} para o alfabeto {a, b} definido 
por h(0) = a; h(1) = ab e h(2) = ba. 
 Suponha, ainda, que L seja a linguagem {ababa}, 
isto é, a linguagem que consiste somente no único 
string ababa. O que é h-1(L)? 
 
 Cada b deve vir ou de um 1 ou de um 2. 
 
 No entanto, se o primeiro b vier de um 2 e o segundo vier de 
um 1, então eles vão ambos precisar de um a entre eles 
como parte de h(2) e h(1), respectivamente. Assim, o 
homomorfismo inverso consiste dos strings {110, 102, 022}. 
EXERCÍCIO: 
 Suponha que h é o homomorfismo do alfabeto 
{0,1,2} para o alfabeto {a,b} definido por: 
 h(0)=a 
 h(1)=ab 
 h(2)=ba 
 O que é h(0120)? 
 O que é h(21120)? 
 Se L é a linguagem L(a(ba)*), o que é h-1(L)? 
EXERCÍCIO: 
 Suponha que h é o homomorfismo do alfabeto 
{0,1,2} para o alfabeto {a,b} definido por: 
 h(0)=a 
 h(1)=ab 
 h(2)=ba 
 h(0120)=aabbaa 
 h(21120)=baababbaa 
 Se L é a linguagem L(a(ba)*), o que é h-1(L)? 
 L(0(2)*)