Aula_07_Automato_Finitos_N_o_Determin_sticos__Parte_3_

Prévia do material em texto

LINGUAGENS FORMA IS E AUTÔMATOS
Prof. Mário Sérgio Cavalcante
DCA0212
Natal - Rio Grande do Norte
Departamento de Engenharia de Computação e Automação
Universidade Federal do Rio Grande do Norte
marioffcavalcante@dca.ufrn.br
Aula 7 - Autômatos Finitos Não-Determinísticos (Parte 3)
SUMÁRIO DA AULA
Fecho sob as Operações Regulares: 
União
Concatenação
Estrela
Observações sobre Interseção
02
FEDERALUNIVERSIDADE DO RIO GRANDE DO NORTE
Fecho sob as Operações Regulares : União Fecho sob as Operações Regulares : Concatenação Fecho sob as Operações Regulares : Estrela Conclusão
Fecho sob as operações regulares
Nesta aula, retomamos o fecho da classe de linguagens regulares
(união, concatenação e estrela ;
Relembrando o conceito de fechamento sob operações :
∀a, b ∈ N, a + b ∈ N e a× b ∈ N
Porém, N não é fechado sob as operações de subtração e divisão : por exem-
plo :
1, 2 ∈ N, (1− 2) 6∈ N e 1÷ 2 6∈ N
Na aula de hoje mostraremos as provas para o fecho sob as três
operações, usando a técnica do não-determinismo
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 3 / 23
FEDERALUNIVERSIDADE DO RIO GRANDE DO NORTE
Fecho sob as Operações Regulares : União Fecho sob as Operações Regulares : Concatenação Fecho sob as Operações Regulares : Estrela Conclusão
Fecho sob as Operações Regulares : União
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 3 / 23
FEDERALUNIVERSIDADE DO RIO GRANDE DO NORTE
Fecho sob as Operações Regulares : União Fecho sob as Operações Regulares : Concatenação Fecho sob as Operações Regulares : Estrela Conclusão
Fecho sob as Operações Regulares : União
Teorema 1.45
A classe de linguagens regulares é fechada sob a operação de união.
A1 ∪ A2 = {w ∈ Σ∗|w ∈ A1 ∨ w ∈ A2}
Fecho sob união :
- Temos as linguagens regulares A1 e A2 e queremos mostrar que A1 ∪ A2
também é regular ;
- Como A1 e A2 são regulares, implica que existe autômatos finitos (N1 e N2,
respectivamente) que as reconhecem. Então deve existe um autômato finito,
M, que reconhece A1 ∪ A2
A máquina N deve aceitar sua cadeia de entrada se N1 ou N2
aceita essa cadeia.
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 4 / 23
FEDERALUNIVERSIDADE DO RIO GRANDE DO NORTE
Fecho sob as Operações Regulares : União Fecho sob as Operações Regulares : Concatenação Fecho sob as Operações Regulares : Estrela Conclusão
Recapitulando :
Ideia da prova do fecho sob a união usando AFDs :
Exemplo :
- A1 = {Cadeias binárias contendo um número ímpar de 0s}
- A2 = {Cadeias binárias contendo exatamente um ’1’}
1
A1 ∪ A2 = { Cadeias binárias contendo um número ímpar de 0s
ou exatamente um ’1’}
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 5 / 23
FEDERALUNIVERSIDADE DO RIO GRANDE DO NORTE
Fecho sob as Operações Regulares : União Fecho sob as Operações Regulares : Concatenação Fecho sob as Operações Regulares : Estrela Conclusão
Recapitulando :
Ideia da prova do fecho sob a união usando AFDs :
Exemplo :
- A1 = {Cadeias binárias contendo um número ímpar de 0s}
- A2 = {Cadeias binárias contendo exatamente um ’1’}
1
A1 ∪ A2 = { Cadeias binárias contendo um número ímpar de 0s
ou exatamente um ’1’}
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 5 / 23
FEDERALUNIVERSIDADE DO RIO GRANDE DO NORTE
Fecho sob as Operações Regulares : União Fecho sob as Operações Regulares : Concatenação Fecho sob as Operações Regulares : Estrela Conclusão
Fecho sob as operações regulares
União :
FIGURE – Caption
- A máquina N é construída direta-
mente a partir de N1 e N2 ;
- N tem um novo estado inicial que
ramifica para os estados iniciais de
N1 e N2
- A nova máquina adivinha não-
deterministicamente qual das
duas máquinas originais aceita a
cadeia de entrada :
Se uma delas aceita a cadeia de en-
trada, N aceita ;
Se nenhuma das duas aceita a en-
trada, N também rejeita.
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 6 / 23
FEDERALUNIVERSIDADE DO RIO GRANDE DO NORTE
Fecho sob as Operações Regulares : União Fecho sob as Operações Regulares : Concatenação Fecho sob as Operações Regulares : Estrela Conclusão
Fecho sob as operações regulares - (União)
Ideia da prova do fecho sob união usando AFNs - Exemplo.
Exemplo :
- A1 = {Cadeias binárias contendo um número ímpar de 0s}
- A2 = {Cadeias binárias contendo exatamente um ’1’}
1
A1 ∪ A2 = { Cadeias binárias contendo um número ímpar de 0s ou exatamente
um ’1’}
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 7 / 23
FEDERALUNIVERSIDADE DO RIO GRANDE DO NORTE
Fecho sob as Operações Regulares : União Fecho sob as Operações Regulares : Concatenação Fecho sob as Operações Regulares : Estrela Conclusão
Fecho sob as operações regulares - União (Prova)
Suponha que :
N1 = (Q1,Σ, δ1, q1,F1) reconheça A1
N2 = (Q2,Σ, δ2, q2,F2) reconheça A2
Construa N = (Q,Σ, δ, q0,F ) para que seja possível reconhecer : A1 ∪ A2.
1. Q = {q0} ∪ Q1 ∪ Q2.
Os estados de N são todos os estados N1 e N2, com a adição de um novo estado
inicial q0 ;
2. O estado q0 é o estado inicial de N.
3. Os estados de aceitação F = F1 ∪ F2. Os estados de aceitação N são todos os
estados de aceitação de N1 e N2. Dessa forma N aceita se N1 ou N2 aceita.
4. Defina δ de modo que para qualquer q ∈ Q e qualquer a ∈ Σ�
δ(q, a) =

δ1(q, a) , q ∈ Q1
δ2(q, a) , q ∈ Q2
{q1, q2} , q = q0 e a = �
∅ , q = q0 e a 6= �
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 8 / 23
FEDERALUNIVERSIDADE DO RIO GRANDE DO NORTE
Fecho sob as Operações Regulares : União Fecho sob as Operações Regulares : Concatenação Fecho sob as Operações Regulares : Estrela Conclusão
Fecho sob as Operações Regulares : Concatenação
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 8 / 23
FEDERALUNIVERSIDADE DO RIO GRANDE DO NORTE
Fecho sob as Operações Regulares : União Fecho sob as Operações Regulares : Concatenação Fecho sob as Operações Regulares : Estrela Conclusão
Fecho sob as Operações Regulares : Concatenação
Teorema 1.47
A classe de linguagens regulares é fechada sob a operação de concatenação.
A1 ◦ A2 = {xy ∈ Σ∗|x ∈ A1 ∧ y ∈ A2}
Fecho sob concatenação :
Temos as linguagens regulares A1 e A2 (cada qual com seus autômatos finitos
N1 e N2, respectivamente) e queremos mostrar que A1◦A2 também é regular ;
É possível a partir de N1 e N2, montar um autômato finito não-determinístico
N que reconhece A1 ◦ A2.
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 9 / 23
FEDERALUNIVERSIDADE DO RIO GRANDE DO NORTE
Fecho sob as Operações Regulares : União Fecho sob as Operações Regulares : Concatenação Fecho sob as Operações Regulares : Estrela Conclusão
Fecho sob as Operações Regulares : Concatenação
Por definição, uma cadeia w pertence a A1 ◦ A2 se e somente
se, w puder ser dividida em duas subcadeias, w = xy, tais que
x ∈ A1 e y ∈ A2
Logo, N somente deve aceitar a cadeia se ela puder ser dividida
em duas partes, w = xy , em que a 1ª parte (x) é aceita por N1 e
a 2ª parte (y) é aceita por N2
O AFN N deve simular (não-deterministicamente) a execução de N1 e de N2 em
série, sendo que N1 faria a computação sobre x e N2 sobre y.
N deve "adivinhar" onde fazer a divisão de w = xy.
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 10 / 23
FEDERALUNIVERSIDADE DO RIO GRANDE DO NORTE
Fecho sob as Operações Regulares : União Fecho sob as Operações Regulares : Concatenação Fecho sob as Operações Regulares : Estrela Conclusão
Fecho sob as Operações Regulares : Concatenação
Atribua ao estado inicial de N o estado de N1
Estados finais de N1 tem setas � que não deterministicamente permite ramificar
para N2 sempre que N1 está em um estado de aceitação ;
Estados de aceitação de N são somente os estados de aceitação de N2
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 11 / 23
FEDERALUNIVERSIDADEDO RIO GRANDE DO NORTE
Fecho sob as Operações Regulares : União Fecho sob as Operações Regulares : Concatenação Fecho sob as Operações Regulares : Estrela Conclusão
Fecho sob as Operações Regulares : Concatenação
Ideia da prova do fecho sob união usando AFNs - Exemplo.
Exemplo :
- A1 = {Cadeias binárias contendo um número ímpar de 0s}
- A2 = {Cadeias binárias contendo exatamente um ’1’}
1
A1 ◦ A2
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 12 / 23
FEDERALUNIVERSIDADE DO RIO GRANDE DO NORTE
Fecho sob as Operações Regulares : União Fecho sob as Operações Regulares : Concatenação Fecho sob as Operações Regulares : Estrela Conclusão
Fecho sob as operações regulares - Concatenação
Suponha que :
N1 = (Q1,Σ, δ1, q1,F1) reconheça A1
N2 = (Q2,Σ, δ2, q2,F2) reconheça A2
Construa N = (Q,Σ, δ, q0,F ) para que seja possível reconhecer : A1 ◦ A2.
1. Q = Q1 ∪ Q2.
Os estados de N são todos os estados os estados de N1 e N2 ;
2. O estado q1 é o mesmo estado inicial de N1.
3. Os estados de aceitação F = F2. Os estados de aceitação N são todos os estados
de aceitação de F2.
4. Defina δ de modo que para qualquer q ∈ Q e qualquer a ∈ Σ�
δ(q, a) =

δ1(q, a) , q ∈ Q1 e q 6∈ F1
δ1(q, a) , q ∈ F1 e a 6= �
δ1(q, a) ∪{q2} , q ∈ F1 e a = �
δ2(q, a) , q ∈ Q2
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 13 / 23
FEDERALUNIVERSIDADE DO RIO GRANDE DO NORTE
Fecho sob as Operações Regulares : União Fecho sob as Operações Regulares : Concatenação Fecho sob as Operações Regulares : Estrela Conclusão
Fecho sob as Operações Regulares : Estrela
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 13 / 23
FEDERALUNIVERSIDADE DO RIO GRANDE DO NORTE
Fecho sob as Operações Regulares : União Fecho sob as Operações Regulares : Concatenação Fecho sob as Operações Regulares : Estrela Conclusão
Fecho sob as Operações Regulares : Estrela
Teorema 1.49
A classe de linguagens regulares é fechada sob a operação estrela.
A∗ = {x1x2...xk |k ≥ 0 ∧ x1 ∈ A, i = 1, 2, 3....k}
Fecho sob estrela - Ideia da prova :
Temos a linguagem regular A1 (com o autômato finito N1 que a reconhece) e que-
remos mostrar que A∗1 também é regular ;
Mostramos como construir, a partir de N1, um autômato finito não-determinístico
N que reconhece A∗1
N deve aceitar a cadeia w se :
w = � ;
w puder ser quebrado em várias partes w = x1x2...xk e N1 aceitar cada uma
das partes de x1
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 14 / 23
FEDERALUNIVERSIDADE DO RIO GRANDE DO NORTE
Fecho sob as Operações Regulares : União Fecho sob as Operações Regulares : Concatenação Fecho sob as Operações Regulares : Estrela Conclusão
Fecho sob as Operações Regulares : Estrela
Como construir ?
Acrescentamos setas com transições rotuladas de � para o estado inicial de N1 ;
Ideia : uma vez que uma das partes (xi ) de w seja aceita por N1 e ainda haja
símbolos a serem lidos, retornamos ao estado inicial de N1 para encontrar se
a próxima parte (xi+1) é aceita também.
Adiciona-se também um novo estado inicial que seja também estado de aceitação,
com uma transição para o estado inicial do autômato N1 rotulada por �
Esse estado é acrescentado para aceitar a cadeia vazia.
Então, ele deve ser também um estado de aceitação.
Não podemos tornar o estado inicial do autômato N1 como estado de aceita-
ção, para evitar que o autômato N reconheça linguagens indevidas.
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 15 / 23
FEDERALUNIVERSIDADE DO RIO GRANDE DO NORTE
Fecho sob as Operações Regulares : União Fecho sob as Operações Regulares : Concatenação Fecho sob as Operações Regulares : Estrela Conclusão
Fecho sob as Operações Regulares : Estrela
A1 = {cadeias binárias iniciadas com zero ou mais "1"s seguidos
da subcadeia 011}
A∗1 :
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 16 / 23
FEDERALUNIVERSIDADE DO RIO GRANDE DO NORTE
Fecho sob as Operações Regulares : União Fecho sob as Operações Regulares : Concatenação Fecho sob as Operações Regulares : Estrela Conclusão
Fecho sob as operações Regulares : Estrela
Suponha que :
N1 = (Q1,Σ, δ1, q1,F1) reconheça A1 ;
Vamos construir :
N = (Q,Σ, δ, q0,F ) para reconhecer A∗1 .
1. Q = {q0} ∪ Q1.
Os estados de N são os estados de N1 mais um novo estado inicial.
2. O estado q0 é o novo estado inicial ;
3. F = {q0} ∪ F1.
Os estados de aceitação são os antigos estados de aceitação mais o novo estado
inicial.
4. Defina δ de modo que para qualquer q ∈ Q e qualquer a ∈ Σ�,
δ(q, a) =

δ1(q, a) , q ∈ Q1 e q 6∈ F1
δ1(q, a) , q ∈ F1 e a 6= �
δ1(q, a) ∪{q1} , q ∈ F1 e a = �
{q1} , q = q0 e a = �
∅ , q = q0 e a 6= �
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 17 / 23
FEDERALUNIVERSIDADE DO RIO GRANDE DO NORTE
Fecho sob as Operações Regulares : União Fecho sob as Operações Regulares : Concatenação Fecho sob as Operações Regulares : Estrela Conclusão
Intersecção
Comentário sobre a Intersecção entre Linguagens Regulares
A intersecção é uma operação é bastante útil, pois algumas lin-
guagens regulares são descritas em termos de intersecção entre
linguagens mais simples :
Ex. : {cadeias binárias contendo um número ímpar de 0s e exatamente um
"1"}
Dadas duas linguagens regulares A1 e A2 (reconhecidas pelos
AFDs N1 e N2, respectivamente), podemos construir um novo AFDs
que reconhece A1 ∩ A2
Demonstração similar à que usamos para união ;
Diferença principal : definição dos estados de aceitação do AFD;
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 18 / 23
FEDERALUNIVERSIDADE DO RIO GRANDE DO NORTE
Fecho sob as Operações Regulares : União Fecho sob as Operações Regulares : Concatenação Fecho sob as Operações Regulares : Estrela Conclusão
Intersecção
Intersecção de Linguagens Regulares
Exemplo :
Exemplo :
- A1 = {Cadeias binárias contendo um número ímpar de 0s}
- A2 = {Cadeias binárias contendo exatamente um ’1’}
1
A1 ∩ A2 = {cadeias binárias contendo um número ímpar de 0s e
exatamente um "1"}
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 19 / 23
FEDERALUNIVERSIDADE DO RIO GRANDE DO NORTE
Fecho sob as Operações Regulares : União Fecho sob as Operações Regulares : Concatenação Fecho sob as Operações Regulares : Estrela Conclusão
Intersecção
Intersecção de Linguagens Regulares
Exemplo :
Exemplo :
- A1 = {Cadeias binárias contendo um número ímpar de 0s}
- A2 = {Cadeias binárias contendo exatamente um ’1’}
1
A1 ∩ A2 = {cadeias binárias contendo um número ímpar de 0s e
exatamente um "1"}
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 20 / 23
FEDERALUNIVERSIDADE DO RIO GRANDE DO NORTE
Fecho sob as Operações Regulares : União Fecho sob as Operações Regulares : Concatenação Fecho sob as Operações Regulares : Estrela Conclusão
Conclusão
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 20 / 23
FEDERALUNIVERSIDADE DO RIO GRANDE DO NORTE
Fecho sob as Operações Regulares : União Fecho sob as Operações Regulares : Concatenação Fecho sob as Operações Regulares : Estrela Conclusão
Conclusões da seção 1.2 - Não Determinismo
Autômatos finitos não-determinísticos são mais fáceis de construir.
Operações regulares permitem a construção de linguagens "com-
plexas" desmembrando-as em sublinguagens mais simples.
Interprete a linguagem original como sendo uma composição de linguagens
mais simples.
Projete um AFN ou AFD para cada uma dessas linguagens.
Combine esses AFNs e AFDs para reconhecer linguagens hierarquicamente
mais complexas, até obter um autômato finito para a linguagem original.
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 21 / 23
FEDERALUNIVERSIDADE DO RIO GRANDE DO NORTE
Fecho sob as Operações Regulares : União Fecho sob as Operações Regulares : Concatenação Fecho sob as Operações Regulares : EstrelaConclusão
Dúvidas??
Dúvidas, Sugestões e Comentários :
mariocavalcante@dca.ufrn.br
Mário Sérgio Cavalcante
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 22 / 23
mariocavalcante@dca.ufrn.br
FEDERALUNIVERSIDADE DO RIO GRANDE DO NORTE
Fecho sob as Operações Regulares : União Fecho sob as Operações Regulares : Concatenação Fecho sob as Operações Regulares : Estrela Conclusão
Bibliografia :
Fontes :
Spiser, M. Introdução à Teoria da Computação.2ª ed., Ed. Thomson.
Notas de aula do professor Marcelo S. Lauretto.
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 23 / 23
	Fecho sob as Operações Regulares: União
	Fecho sob as Operações Regulares: Concatenação
	Fecho sob as Operações Regulares: Estrela
	Intersecção
	Conclusão
	Bibliografia: 
	anm0: 
	0.4: 
	0.3: 
	0.2: 
	0.1: 
	0.0: