Equivalência entre DFA e NFA
25 Setembro 2019, 09:30 • André Souto
Recapitulação de definição formal de NFA e computação num NFA.
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.
Exemplos de construção.
Algoritmo de simplificação do processo de equivalência.
Exemplo.
Estudar secção 1.2 do Sipser.