Este vídeo formaliza alguns conceitos BEM básicos que mencionamos na aula 1 mas que cujas formalizações são importantes para as demais dessa aula.

Nesta aula, apresento a 1a parte da Seção 2.1 do Livro de Michael Sipser, "Introdução à Teoria da Computação". Mais especificamente, introduzo alguns conceitos, exemplos e definições formais relacionados às gramáticas livres-do-contexto.

Nesta aula, apresentamos a 2a parte da Seção 1.3 do Livro de Michael Sipser, "Introdução à Teoria da Computação". Mais especificamente, apresentamos a prova de que todo autômato finito pode ser convertido em uma expressão regular.

Nesta aula, apresentamos a 1a parte da Seção 1.3 do Livro de Michael Sipser, "Introdução à Teoria da Computação". Mais especificamente, apresentamos: a) A definição de expressões regulares; b) Uma ideia geral de suas aplicações; c) A prova de que toda expressão regular pode ser convertida em um autômato finito não determinístico.

Nesta aula, encerramos o estudo da Seção 1.2 do Livro de Michael Sipser, "Introdução à Teoria da Computação". Utilizamos o conceito de não-determinismo para mostrar que as linguagens regulares são fechadas sob as operações de união, concatenação e estrela.

Nesta aula, apresentamos um algoritmo para simulação de autômatos finitos não-determinísticos.

Este vídeo contém um breve tutorial sobre o uso do JFLAP para construção e simulação de autômatos finitos determinísticos

Neste vídeo, ilustramos a construção passo a passo de autômatos finitos através de três exemplos simples.

Nesta aula, continuamos o estudo da Seção 1.2 do Livro de Michael Sipser, "Introdução à Teoria da Computação". Apresentamos aqui a demonstração de que todo autômato finito não-determinístico (AFN) possui um autômato finito determinístico (AFN) equivalente.

Nesta aula iniciamos a Seção 1.2 do Livro de Michael Sipser, "Introdução à Teoria da Computação". Os tópicos abordados são: a) Definição formal de um autômato não determinístico (AFN) b) Computação de um AFN c) Exemplos de AFNs.