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, 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.