Sumários

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.

22 Setembro 2021, 08:00 • André Souto

Resolução de exercícios sobre DFA's da primeira folha de exercícios.

21 Setembro 2021, 10:30 • André Souto

Resolução de exercícios sobre DFA's da primeira folha de exercícios.

21 Setembro 2021, 09:30 • André Souto

Exemplos de DFA's e linguagens reconhecidas por DFA's.

Operações regulares com linguagens como motivação para o NDFA's.

Prova de que a união e intersecção de duas linguagens regulares ainda é uma linguagem regular.

O fecho de Kleene como operação regular que justifica a introdução do não determinismo.

Diferenças entre DFA e NDFA.

As diferentes formas que evidenciam o não determinismo.

Noção de computação num NFA.

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

20 Setembro 2021, 08:00 • Paulo Jorge Cunha Vaz Dias Urbano

Exercícios sobre autómatos finitos deterministas. (AFD)

Definição formal, em diagrama e em tabela dos AFDs.

Linguagens reconhecidas pelos AFDs.