Minimização
1770 palavras
8 páginas
Curso: Ciência da Computação Aspectos Teóricos da Computação Aula 10 Minimização de um Autômato FinitoNotas de Aula
Aspectos Teóricos da Computação
2/19
Minimização de um Autômato Finito
●
A implementação de um AFD consiste basicamente em um algoritmo que controla a mudança de estado do autômato a cada símbolo lido da entrada. O tempo necessário par aceitar ou rejeitar é diretamente proporcional ao tamanho da entrada. Em termos de complexidade de algoritmos, AF pertencem à classe de algoritmos mais eficientes em termos de tempo de processamento. (Supondo que toda a a fita de entrada necessita ser lida)
Aspectos Teóricos da Computação 3/19
●
●
Minimização de Autômatos
Exercício: Seja a palavra w = ababababa Qual autômato abaixo é mais eficiente em termos de processamento para reconhecer essa palavra?
1) 2)
q0
a
q1
a,b
q2
a,b
qf
a,b
q0
a
q1
a,b
Aspectos Teóricos da Computação
4/19
Minimização de Autômatos
Exercício: Seja a palavra w = ababababa Qual autômato abaixo é mais eficiente em termos de processamento para reconhecer essa palavra?
1) 2)
q0
a
q1
a,b
q2
a,b
qf
a,b
q0
a
q1
a,b
São iguais. O tempo de processamento não depende do autômato de reconhecimento considerado e sim do tamanho da palavra. Ou seja, qualquer autômato finito determinístico que reconheça a linguagem terá a mesma eficiência. Computação 5/19 Aspectos Teóricos da
Minimização de Autômatos
●
O tempo de processamento não depende do autômato de reconhecimento considerado e sim do tamanho da palavra. Ou seja, qualquer autômato finito determinístico que reconheça a linguagem terá a mesma eficiência. No entanto podemos trabalhar para minimizar o número de estados de um autômato se isso for possível. Dado um AFD qualquer, o objetivo da minimização é gerar o AF equivalente com o menor número de estados possíveis denominado Autômato Finito Determinístico Mínimo ou simplesmente