propriedades-3

Prévia do material em texto

Linguagens Regulares – Propriedades
Linguagens Formais, Autômatos e Computabilidade
Filipe Saraiva
Filipe Saraiva | UFPA | 1 / 28
Conteúdo
Introdução
Minimização de Autômatos Finitos
Pré-Condições
Algoritmo de Minimização
Exemplo
Conclusões
Filipe Saraiva | UFPA | 2 / 28
Conteúdo
Introdução
Minimização de Autômatos Finitos
Pré-Condições
Algoritmo de Minimização
Exemplo
Conclusões
Filipe Saraiva | UFPA | 3 / 28
Introdução
Essa aula se dedicará exclusivamente à minimização de Autômatos
Finitos. Na próxima seção serão analisadas as pré-condições e
passos necessários para se efetuar essas operações.
Filipe Saraiva | UFPA | 4 / 28
Conteúdo
Introdução
Minimização de Autômatos Finitos
Pré-Condições
Algoritmo de Minimização
Exemplo
Conclusões
Filipe Saraiva | UFPA | 5 / 28
Conteúdo
Introdução
Minimização de Autômatos Finitos
Pré-Condições
Algoritmo de Minimização
Exemplo
Conclusões
Filipe Saraiva | UFPA | 6 / 28
Minimização – Pré-Condições
Um Autômato Finito pode ser reduzido ao menor número de estados
possíveis, e ainda assim conseguir reconhecer a linguagem original
que ele processava, sem perda de expressividade.
Filipe Saraiva | UFPA | 7 / 28
Minimização – Pré-Condições
A redução do número de estados permite um autômato mais
compacto, apesar de não necessariamente impactar na redução do
tempo de processamento computacional ou outra característica.
De fato, para algumas situações um autômato com mais estados é até
mais desejável que algum com menos (por exemplo, para facilitar
implementações).
Filipe Saraiva | UFPA | 8 / 28
Minimização – Pré-Condições
Para que um Autômato Finito possa ser minimizado é necessário
cumprir certas condições:
• O autômato deve ser um Autômato Determinístico;
• Todos os estados devem ser alcançáveis a partir do estado inicial;
• Função programa deve ser total (cada estado tem transições para
todos os símbolos da linguagem).
Filipe Saraiva | UFPA | 9 / 28
Conteúdo
Introdução
Minimização de Autômatos Finitos
Pré-Condições
Algoritmo de Minimização
Exemplo
Conclusões
Filipe Saraiva | UFPA | 10 / 28
Algoritmo de Minimização
Dada as pré-condições, os passos do algoritmo de minimização serão
os seguintes:
• Passo 1: Cria-se uma tabela com os estados distintos
relacionando-os apenas 1 vez;
• Passo 2: Marcam-se todos os estados trivialmente não
equivalentes (no caso, aqueles que são {final, não final} e
vice-versa;
• Passo 3: Marcam-se os estados não equivalentes. Fazendo para
cada par não marcado {qu, qv } e para cada símbolo a ∈
∑
,
suponha:
Filipe Saraiva | UFPA | 11 / 28
Algoritmo de Minimização
Passo 3: Marcam-se os estados não equivalentes. Fazendo para cada
par não marcado {qu, qv } e para cada símbolo a ∈
∑
, suponha:
δ(qu, a) = pu ; δ(qv , a) = pv
• Se pu = pv : então qu é equivalente a qv para a e portanto não
deve ser marcado;
• Se pu 6= pv e {pu, pv } não marcado: então {qu, qv } são incluídos
em uma lista a partir de {pu, pv } para posterior análise;
• Se pu 6= pv e {pu, pv } é marcado:
• {qu , qv } não é equivalente e deve ser marcado;
• Se {qu , qv } encabeça lista de pares, marcam-se todos os pares da
lista, recursivamente.
Filipe Saraiva | UFPA | 12 / 28
Algoritmo de Minimização
Dada as pré-condições, os passos do algoritmo de minimização serão
os seguintes (continuação):
• Passo 4: Unificar os estados equivalentes, no caso os pares não
marcados, de acordo com:
• Pares não finais são unificados em um novo estado não final;
• Pares finais são unificados em um novo estado final;
• Se algum dos estados a ser unificado for o inicial, o novo estado
será inicial;
• Todas as transições com origem/destino em um estado que foi
unificado passam a ter origem/destino no novo estado unificado.
Filipe Saraiva | UFPA | 13 / 28
Conteúdo
Introdução
Minimização de Autômatos Finitos
Pré-Condições
Algoritmo de Minimização
Exemplo
Conclusões
Filipe Saraiva | UFPA | 14 / 28
Exemplo
Utilizaremos como exemplo o seguinte autômato a ser minimizado:
M = ({a, b}, {q0, q1, q2, q3, q4, q5}, δ, q0, {q0, q4, q5})
δ a b
q0 q2 q1
q1 q1 q0
q2 q4 q5
q3 q5 q4
q4 q3 q2
q5 q2 q3
Filipe Saraiva | UFPA | 15 / 28
Exemplo
Passo 1 trata-se de criar uma tabela com os estados distintos
relacionando-os apenas 1 vez. A tabela é criada abaixo, removendo da
coluna o primeiro estado e removendo da linha o último estado.
Perceba que a tabela é triângular à esquerda/baixo – os cruzamentos
à direita/cima são descartados.
q1 - - - -
q2 - - -
q3 - -
q4 -
q5
q0 q1 q2 q3 q4
Filipe Saraiva | UFPA | 16 / 28
Exemplo
Passo 2 marcam-se os elementos trivialmente não equivalentes, ou
seja, aqueles pares que cruzam {estados finais, estados não finais} e
vice-versa.
q1 X - - - -
q2 X - - -
q3 X - -
q4 X X X -
q5 X X X
q0 q1 q2 q3 q4
Filipe Saraiva | UFPA | 17 / 28
Exemplo
Passo 3 Nesse passo devem ser marcados os estados não
equivalentes. Para tanto, é necessário verificar as transições nos pares
de estados não marcados na tabela.
{q0, q4}
δ(q0, a) = q2
δ(q4, a) = q3
δ(q0, b) = q1
δ(q4, b) = q2
{q1, q2} e {q2, q3} são não
marcados: {q0, q4} vão para as
listas encabeçadas por {q1, q2} e
{q2, q3}.
{q0, q5}
δ(q0, a) = q2
δ(q5, a) = q2
δ(q0, b) = q1
δ(q5, b) = q3
{q1, q3} é não marcados: {q0, q5}
vão para a lista encabeçadas por
{q1, q3}.
Filipe Saraiva | UFPA | 18 / 28
Exemplo
Passo 3 Tabela após as verificações realizadas:
q1 X - - - -
q2 X l1−2 - - -
q3 X l1−3 l2−3 - -
q4 X X X -
q5 X X X
q0 q1 q2 q3 q4
l1−2 – {q0, q4}
l1−3 – {q0, q5}
l2−3 – {q0, q4}
Filipe Saraiva | UFPA | 19 / 28
Exemplo
Passo 3 Nesse passo devem ser marcados os estados não
equivalentes. Para tanto, é necessário verificar as transições nos pares
de estados não marcados na tabela (continuação).
{q1, q2}
δ(q1, a) = q1
δ(q2, a) = q4
δ(q1, b) = q0
δ(q2, b) = q5
{q1, q4} é marcado: marca-se {q1,
q2}, que encabeça a lista e
portanto vai marcar o par {q0, q4}
também.
{q1, q3}
δ(q1, a) = q1
δ(q3, a) = q5
δ(q1, b) = q0
δ(q3, b) = q4
{q1, q5} e {q0, q4} são marcados:
marca-se {q1, q3}, que encabeça
uma lista que marcará {q0, q5}
também.
Filipe Saraiva | UFPA | 20 / 28
Exemplo
Passo 3 Tabela após as verificações realizadas:
q1 X - - - -
q2 X X - - -
q3 X X l2−3 - -
q4 X X X X -
q5 X X X X
q0 q1 q2 q3 q4
l2−3
Filipe Saraiva | UFPA | 21 / 28
Exemplo
Passo 3 Nesse passo devem ser marcados os estados não
equivalentes. Para tanto, é necessário verificar as transições nos pares
de estados não marcados na tabela (continuação).
{q2, q3}
δ(q2, a) = q4
δ(q3, a) = q5
δ(q2, b) = q5
δ(q3, b) = q4
{q4, q5} é não marcado: {q2, q3}
entram na lista encabeçada por
{q4, q5}.
{q4, q5}
δ(q4, a) = q3
δ(q5, a) = q2
δ(q4, b) = q2
δ(q5, b) = q3
{q2, q3} é não marcado: {q4, q5}
entra na lista encabeçada por {q2,
q3}.
Filipe Saraiva | UFPA | 22 / 28
Exemplo
Passo 3 Tabela após as verificações realizadas:
q1 X - - - -
q2 X X - - -
q3 X X l2−3 - -
q4 X X X X -
q5 X X X X l4−5
q0 q1 q2 q3 q4
l2−3 – {q4, q5}
l4−5 – {q2, q3}
Filipe Saraiva | UFPA | 23 / 28
Exemplo
Passo 4 Finalizada as verificações, chega o momento de unificar
estados. Da tabela, percebe-se que {q2, q3} e {q4, q5} são não
marcados, logo esses pares podem ser unificados:
• {q2, q3} será unificado em q23;
• {q4, q5} será unificado em q45.
Filipe Saraiva | UFPA | 24 / 28
Exemplo
O autômato minimizado, portanto, é o seguinte. Atente para as
transições que agora partem/chegam ao resultado dos estados
unificados.
M = ({a, b}, {q0, q1, q23, q45}, δ, q0, {q0, q45})
δ a b
q0 q2 q1
q1 q1 q0
q23 q45 q45
q45 q23 q23
Filipe Saraiva | UFPA | 25 / 28
Conteúdo
Introdução
Minimização de Autômatos Finitos
Pré-Condições
Algoritmo de Minimização
Exemplo
Conclusões
Filipe Saraiva | UFPA | 26 / 28
Conclusões
• Minimização de autômatos consiste na redução do número de
estados a partir da fusão de certos estados. O autômato
resultante tem a mesma expressividade do autômato original;
• Para que um autômato seja minimizado, ele deve ser um AFD,
conectado, e a função de transiçãodeve ser total/completa;
• O algoritmo de minimização vai comparando pares de autômatos
de forma a verificar se eles são possíveis de serem fundidos;
• Não necessariamente a minimização consiste em um autômato
mais simples de ser entendido.
Filipe Saraiva | UFPA | 27 / 28
Linguagens Regulares – Propriedades
Linguagens Formais, Autômatos e Computabilidade
Filipe Saraiva
Filipe Saraiva | UFPA | 28 / 28
	Introdução
	Minimização de Autômatos Finitos
	Pré-Condições
	Algoritmo de Minimização
	Exemplo
	Conclusões