Equivalência DFA e NDA
23 Setembro 2020, 09:30 • André Souto
Recapitulação de definição formal de NDFA e computação num NDFA.
Exemplos de NFA's e exemplos de linguagens reconhecidas por NFA's.
Comparação DFA vs NFA.
Noção de equivalência entre autómatos.
Prova que um DFA tem um NFA equivalente.
Noção de fecho-epsilon de um NFA.
Exemplos.
Prova que um NFA tem um DFA equivalente.
Exemplo de aplicação.
Algoritmo de simplificação do processo de equivalência.
Exemplo.
Os alunos devem estudar a secção 1.2. do livro do Sipser.
(Aula dada em regime síncono não presencial transmitida via Zoom)