Não determinismos em autómatos. Equivalência com os DFA's

22 Setembro 2021, 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 construção de um DFA equivalente a um NDFA dado e respetiva simplificação.

Os alunos devem estudar a secção 1.2. do livro do Sipser.