Minimização de Autômatos - Teoria da Computação

Prévia do material em texto

Minimização de Autômatos
Cloves Oliveira
Glevson da Silva
Jeorgiton Damasceno
Lucas Severo
Marcos Heriberto
UNIVERSIDADE FEDERAL DE ALAGOAS – Campus Arapiraca
Teoria da Computação
Prof.: Alexandre Paes
1
Minimização de Autômato
Reduzir um autômato ao menor número de estados possíveis.
Apresentação: Lucas
2
Minimização de Autômato
Reduzir um autômato ao menor número de estados possíveis.
Cardinalidade:
#A ≥ #A’.
3
Minimização de Autômato
Reduzir um autômato ao menor número de estados possíveis.
O Autômato Finito mínimo é único.
Cardinalidade:
#A ≥ #A’.
4
Minimizar não induz em melhoria de eficiência.
Minimização de Autômato
O Autômato Finito mínimo é único.
Reduzir um autômato ao menor número de estados possíveis.
Cardinalidade:
#A ≥ #A’.
5
Minimização de Autômato
Unificar os estados equivalentes.
6
Algoritmo de minimização
Passo 1: Construção da Tabela
qn
…
q2
q1
q0
q0
q1
q2
…
qn
Apresentação: Cloves
Um passo importante é saber desenvolver o algoritmo de minimização, sendo que o mesmo está subdividido em 5 passos.
O primeiro é escolher a tabela que será usada para combinar os pares possíveis do autômato.
As tabelas que estão nos slides são exemplos que podem ser adotados, já que o intuito é permitir combinar todos os pares de estados possíveis.
7
Algoritmo de minimização
Passo 1: Construção da Tabela
qn
…
q2
q1
q0
q0
q1
q2
…
qn
Um passo importante é saber desenvolver o algoritmo de minimização, sendo que o mesmo está subdividido em 5 passos.
O primeiro é escolher a tabela que será usada para combinar os pares possíveis do autômato.
As tabelas que estão nos slides são exemplos que podem ser adotados, já que o intuito é permitir combinar todos os pares de estados possíveis.
8
Algoritmo de minimização
Passo 1: Construção da Tabela
q0
q1
q2
…
qn
q0
q1
q2
…
qn
Um passo importante é saber desenvolver o algoritmo de minimização, sendo que o mesmo está subdividido em 5 passos.
O primeiro é escolher a tabela que será usada para combinar os pares possíveis do autômato.
As tabelas que estão nos slides são exemplos que podem ser adotados, já que o intuito é permitir combinar todos os pares de estados possíveis.
9
Algoritmo de minimização
Passo 1: Construção da Tabela
q0
q1
q2
…
qn
q0
q1
q2
…
qn
Um passo importante é saber desenvolver o algoritmo de minimização, sendo que o mesmo está subdividido em 5 passos.
O primeiro é escolher a tabela que será usada para combinar os pares possíveis do autômato.
As tabelas que estão nos slides são exemplos que podem ser adotados, já que o intuito é permitir combinar todos os pares de estados possíveis.
10
Algoritmo de minimização
Passo 1: Construção da Tabela
q0
q1
q2
…
qn
q0
q1
q2
…
qn
Um passo importante é saber desenvolver o algoritmo de minimização, sendo que o mesmo está subdividido em 5 passos.
O primeiro é escolher a tabela que será usada para combinar os pares possíveis do autômato.
As tabelas que estão nos slides são exemplos que podem ser adotados, já que o intuito é permitir combinar todos os pares de estados possíveis.
11
Algoritmo de minimização
Passo 1: Construção da Tabela
Passo 2: Marcação dos estados trivialmente não-equivalentes.
Pares do tipo:
{estado final, estado não-final}
No passo 2, deve-se marcar os pares trivialmente não equivalentes, que nesse caso são os pares de estados finais e não finais.
12
Algoritmo de minimização
Passo 1: Construção da Tabela
Passo 3: Marcação dos estados não-equivalentes.
Passo 2: Marcação dos estados trivialmente não-equivalentes.
δ(qu, a) = pu e δ(qv, a) = pv
pu = pv, {qu, qv} equivalentes;
pu ≠ pv e {qu, qv} não marcados, analisa depois;
pu ≠ pv e {qu, qv} marcados:
{qu, qv} não equivalente e deve ser marcado;
Se {qu, qv} encabeça a uma lista de pares, marca todos os pares.
O passo 3 é a marcação dos estados restantes não equivalentes. Nesse passo há algumas regras a serem seguidas.
Se um estado “pu” for equivalente a outro estado “pv” para um símbolo “a”, então não deve ser marcado.
Caso não sejam equivalentes e o par não está marcado, então deixa-os para análise posterior.
Se estiverem marcados e “pu” e “pv” não são equivalentes, deixa-os como estão.
Caso “qu” e “qv” façam parte de uma lista de pares, então marca todos os pares da lista recursivamente.
13
Algoritmo de minimização
Passo 1: Construção da Tabela
Passo 3: Marcação dos estados não-equivalentes.
Passo 2: Marcação dos estados trivialmente não-equivalentes.
Passo 4: Unificação dos estados equivalentes.
Equivalência Transitiva;
Pares não-finais equivalentes podem ser unificados em outro não-final;
Da mesma forma os finais;
Se um dos estado equivalentes for inicial, então o unificado também será.
O passo 4 consiste apenas unificar os estados equivalentes, para isso, verifica-se a transitividade, ou seja, a partir de um estado X que consome algo chega em Y e de Y chega em Z, então X chega em Z.
Pares não finais equivalentes são unificados.
Da mesma forma os finais também devem ser unificados em caso de equivalência.
Se um dos estado equivalentes não final for inicial, então o unificado também será.
14
Algoritmo de minimização
Passo 1: Construção da Tabela
Passo 3: Marcação dos estados não-equivalentes.
Passo 2: Marcação dos estados trivialmente não-equivalentes.
Passo 4: Unificação dos estados equivalentes.
Passo 5: Exclusão dos estados inúteis.
Um estado q é inútil se é não-final e a partir dele não atinge um estado final.
E por fim, o passo 5 detém-se na exclusão dos estado inúteis, ou seja, um estado q é inútil se é não-final e a partir dele não atinge um estado final.
15
Minimização – Pré-requisitos
A - Deve ser determinístico.
B – Estados alcançáveis a partir do Inicial.
C – A Função Programa deve ser Total.
Pré-requisitos
Apresentação: Glevson
16
Minimização – Pré-requisitos
B – Estados alcançáveis a partir do Inicial.
C – A Função Programa deve ser Total.
Pré-requisitos
A - Deve ser determinístico.
17
Minimização – Pré-requisitos
C – A Função Programa deve ser Total.
Pré-requisitos
A - Deve ser determinístico.
B – Estados alcançáveis a partir do Inicial.
18
Minimização – Pré-requisitos
Pré-requisitos
A - Deve ser determinístico.
B – Estados alcançáveis a partir do Inicial.
C – A Função Programa deve ser Total.
19
Minimização – Processos
A – Gerar um AFD equivalente.
B – Eliminar os estados inaceitáveis.
C – Transformar a função programa em Total.
Processos
20
Minimização – Processos
A – Gerar um AFD equivalente.
B – Eliminar os estados inaceitáveis.
C – Transformar a função programa em Total.
Processos
21
Minimização – Processos
C – Transformar a função programa em Total.
Processos
A – Gerar um AFD equivalente.
B – Eliminar os estados inaceitáveis.
22
Minimização – Processos
Processos
A – Gerar um AFD equivalente.
B – Eliminar os estados inaceitáveis.
C – Transformar a função programa em Total.
23
Minimização
A - Deve ser determinístico.
B – Estados alcançáveis a partir do Inicial.
C – A Função Programa deve ser Total.
A – Gerar um AFD equivalente.
B – Eliminar os estados inaceitáveis.
C – Transformar a função programa em Total.
Pré-requisitos
Processos
24
q0
q1
q2
q3
b
b
a
a
b
b
q5
q4
a
a
a
a
b
b
A
B
→Q0
Q2
Q1
Q1
Q1
Q0
Q2
Q4
Q5
Q3
Q5
Q4
*Q4
Q3
Q2
*Q5
Q2
Q3
Exemplo
Apresentação: Jeorgiton
25
q0
q1
q2
q3
b
b
a
a
b
b
q5
q4
a
a
a
a
b
b
Exemplo
q1
q2
q3
q4
q5
X
X
X
X
q0
q1
q2
q3
q4
26
q0
q1
q2
q3
b
b
a
a
b
b
q5
q4
a
a
a
a
b
b
Exemplo
q1
q2
q3
q4
X
X
X
X
q5
X
X
X
X
q0
q1
q2
q3
q4
27
q0
q1
q2
q3
b
b
a
a
b
b
q5
q4
a
a
a
a
b
b
Exemplo
q1
q2
q3
q4
X
X
X
X
q5
X
X
X
X
O
q0
q1
q2
q3
q4
28
q0
q1
q2
q3
b
b
a
a
b
b
q5
q4
a
a
a
a
b
b
Exemplo
q1
X
q2
q3
q4
X
X
X
X
q5
X
X
X
X
O
q0
q1
q2
q3
q4
29
q0
q1
q2
q3
b
b
a
a
b
b
q5
q4
a
a
a
a
b
b
Exemplo
q1
X
q2
X
q3
q4
X
X
X
X
q5
X
X
X
X
O
q0
q1
q2
q3
q4
30
q0
q1
q2
q3
b
b
a
a
b
b
q5
q4
a
a
a
a
b
b
Exemplo
q1
X
q2
X
X
q3
q4
X
X
X
X
q5
X
X
X
X
O
q0
q1
q2
q3
q4
31
q0
q1
q2
q3
b
b
a
a
b
b
q5
q4
a
a
a
a
b
b
Exemplo
q1
X
q2
X
X
q3
X
q4
X
X
X
X
q5
X
X
X
X
O
q0
q1
q2
q3
q4
32
q0
q1
q2
q3
b
b
a
a
b
b
q5
q4
a
a
a
a
b
b
Exemplo
q1
X
q2
X
X
q3
X
X
q4
X
X
X
X
q5
X
X
X
X
O
q0
q1
q2
q3
q4
33
q0
q1
q2
q3
b
b
a
a
b
b
q5
q4
a
a
a
a
b
bExemplo
q1
X
q2
X
X
q3
X
X
O
q4
X
X
X
X
q5
X
X
X
X
O
q0
q1
q2
q3
q4
34
Macete
Q4,Q5
X
Q2,Q3
Y
A
B
→Q0
Q2
Q1
Q1
Q1
Q0
Q2
Q4
Q5
Q3
Q5
Q4
*Q4
Q3
Q2
*Q5
Q2
Q3
A
B
→Q0
Y
Q1
Q1
Q1
Q0
Y
X
X
Y
X
X
*X
Y
Y
*X
Y
Y
A
B
→Q0
Y
Q1
Q1
Q1
Q0
Y
X
X
*X
Y
Y
35
Autômato Reduzido
A
B
Q0
Y
Q1
Q1
Q1
Q0
Y
X
X
*X
Y
Y
q0
X
q1
Y
b
b
a
a
a, b
a, b
36
Exemplo 2
Com base na tabela a seguir:
Construa a tabela de distinções para esse autômato;
Construa o DFA com número mínimo de estados equivalentes.
0
1
→A
B
A
B
A
C
C
D
B
*D
D
A
E
D
F
F
G
E
G
F
G
H
G
D
Apresentação: Marcos
37
Tabela de Transição
1
A
B
E
F
G
H
D
C
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
1
→A
B
A
B
A
C
C
D
B
*D
D
A
E
D
F
F
G
E
G
F
G
H
G
D
38
Tabela de Distinção
B
X
C
X
X
D
X
X
X
E
X
X
O
X
F
X
O
X
X
X
G
O
X
X
X
X
X
H
X
X
X
X
X
X
X
A
B
C
D
E
F
G
39
Estados Equivalentes
(E,C)
X
(F,B)
Y
(G,A)
Z
0
1
A
B
A
B
A
C
C
D
B
*D
D
A
E
D
F
F
G
E
G
F
G
H
G
D
0
1
Z
Y
Z
Y
Z
X
X
D
Y
*D
D
Z
X
D
Y
Y
Z
X
Z
Y
Z
H
Z
D
0
1
Z
Y
Z
Y
Z
X
X
D
Y
*D
D
Z
X
D
Y
H
Z
D
40
Tabela de Transição
0
1
Z
Y
Z
Y
Z
X
X
D
Y
*D
D
Z
X
D
Y
H
Z
D
Z
D
Y
X
H
0
0
1
1
0
0
1
1
0
1
41
Tabela de Transição
0
1
Z
Y
Z
Y
Z
X
X
D
Y
*D
D
Z
X
D
Y
H
Z
D
42
Obrigado!
43