Carregando

Aula 4 - vídeo 2: Equivalência entre AFD e AFN - Parte 1

por Ariane Machado Lima

Incorporar
Recomendar
Download
     
Gostei (0)

Formatos disponíveis

Assista a esse vídeo em: MP4 (1280 X 720 px) | MP4 (640 X 360 px)

Licença de uso

Acesso Aberto (Verde)
Esta licença permite ao usuário copiar o conteúdo do e-Aulas USP, porém veta qualquer alteração e/ou sua utilização para fins comerciais ou não educacionais, autorizando seu compartilhamento sob licença com as mesmas características, desde que se atribua crédito aos autores. Esta licença permite o download do vídeo para usuários logados no sistema.

Sobre a aula

Este vídeo mostra a primeira parte da prova de equivalência entre AFDs e AFNs.

Disciplina

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

EMENTA

Computabilidade: noção intuitiva, modelos computacionais, equivalência entre modelos e tese de Church, funções não-computáveis e o problema da parada. Enumerabilidade e decidibilidade: problemas não-decidíveis e semi-decidíveis. Linguagens formais e autômatos: sistemas de estados finitos, autômatos finitos, linguagens regulares, expressões regulares, gramáticas regulares, autômatos com pilha, linguagens livres de contexto e gramáticas livres de contexto, hierarquia de chomsky.

Objetivo

Introduzir o conceito de complexidade dos algoritmos e conscientiza-lo das limitações da ciência da computação, habilitando-o a melhor resolver problemas com o auxílio do computador. Introduzir os conceitos de linguagem formal e autômatos, para auxiliar a resolver outra classe de problemas relacionados às linguagens de programação.

Índice de vídeos da disciplina

  1. ACH2043 - ITC - Aula 04: Seção 1.2 - Não-Determinismo (Parte 1)
  2. ACH2043 - ITC - Aula 03: Seção 1.1 - Autômatos Finitos e Linguagens Regulares (Parte 2)
  3. ACH2043 - ITC - Aula 02: Seção 1.1 - Autômatos Finitos e Linguagens Regulares
  4. ACH2043 - Tutorial JFLAP - AFD V01
  5. ACH2043 - Projetando autômatos finitos: exemplos
  6. Aula 01: fim da aula de introdução
  7. ACH2043 - ITC 2020 T04 - Aula 01: Apresentação da disciplina
  8. Aula 02 - vídeo 1: Formalização de conceitos básicos para autômatos
  9. Aula 02 - vídeo 2: Definição formal de Autômatos Finitos Determinísticos (AFDs)
  10. Aula 02 - vídeo 3: Definição de computação por um autômato
  11. Aula 4 - vídeo 1: Equivalência entre AFD e AFN - Introdução
  12. Aula 02 - vídeo 4: Linguagem Regular e Projeto de Autômato
  13. Aula 4 - vídeo 2: Equivalência entre AFD e AFN - Parte 1
  14. Aula 4 - vídeo 3: Equivalência entre AFD e AFN - Parte 2
  15. Aula 4 - vídeo 4: Equivalência entre AFD e AFN - Exemplo de Conversão
  16. Aula 4 - vídeo 5: Equivalência entre AFD e AFN - Últimos comentários
  17. Aula 6 - vídeo 1: Definição de Expressões Regulares
  18. Aula 6 - vídeo 2: Autômatos Finitos Não-Determinísticos Generalizados
  19. Aula 6 - vídeo 3: Equivalência entre expressões regulares e autômatos finitos (Parte 1)
  20. Aula 6 - vídeo 4: Equivalência entre expressões regulares e autômatos finitos (Parte 2)
Pró-Reitoria de Graduação
Telefone: +55 11 3091-9942