Licença de cópia, reuso e redistribuição
A licença deste vídeo permite ao usuário utilizar uma cópia do conteúdo do e-Aulas USP como matéria-prima para a elaboração de novos conteúdos educacionais sem fins comerciais, desde que se atribua o devido crédito ao autor original e que as novas criações sejam licenciadas sob os mesmos termos desta.
Sobre a aula
Este vídeo apresenta a prova de equivalência entre gramáticas regulares e autômatos finitos
Disciplina
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
- ACH2043 - ITC - Aula 14: Seção 2.2 - Autômato com Pilha (Parte 1)
- ACH2043 - ITC - Aula 13: Algoritmo CYK (Cocke–Younger–Kasami)
- ACH2043 - ITC - Aula 12: Seção 2.1 - Gramáticas Livres-do-Contexto (Parte 3)
- ACH2043 - ITC - Aula 11: Seção 2.1 - Gramáticas Livres-do-Contexto (Parte 2)
- Aula 8 - vídeo 1: Introdução a gramáticas e hierarquia de Chomsky
- Aula 8 - vídeo 2: Gramáticas regulares
- Aula 7 - continuação
- Aula 8 - vídeo 3: Equivalência entre gramáticas regulares e autômatos finitos