Vídeo 8 de 8

Introdução à Teoria da Computação

Licença de uso

Sobre a aula

Este vídeo apresenta a prova de equivalência entre gramáticas regulares e autômatos finitos

Disciplina

ACH2043-2 Introdução à Teoria da Computação

EMENTA

Autômatos Finitos e Linguagens Regulares: sistemas de estados finitos, autômatos finitos, linguagens regulares, expressões regulares, gramáticas regulares. Autômatos de Pilha e Linguagens Livres de Contexto: autômatos com pilha, linguagens livres de contexto, gramáticas livres de contexto e hierarquia de Chomsky. Conceitos básicos das teorias da computabilidade e da complexidade: Máquinas de Turing, problema da parada, decidibilidade, as classes de problemas P e NP e NP-completude.

Objetivo

Introduzir os conceitos de linguagens formais e autômatos e suas relações com linguagens de programação. Introduzir os conceitos básicos de computabilidade e complexidade, discutindo as limitações da ciência da computação.

Índice de vídeos da disciplina

1. ACH2043 - ITC - Aula 14: Seção 2.2 - Autômato com Pilha (Parte 1)
2. ACH2043 - ITC - Aula 13: Algoritmo CYK (Cocke–Younger–Kasami)
3. ACH2043 - ITC - Aula 12: Seção 2.1 - Gramáticas Livres-do-Contexto (Parte 3)
4. ACH2043 - ITC - Aula 11: Seção 2.1 - Gramáticas Livres-do-Contexto (Parte 2)
5. Aula 8 - vídeo 1: Introdução a gramáticas e hierarquia de Chomsky
6. Aula 8 - vídeo 2: Gramáticas regulares
7. Aula 7 - continuação
8. Aula 8 - vídeo 3: Equivalência entre gramáticas regulares e autômatos finitos

Vídeos relacionados