Informações

  • Curso: Linguagens Formais e Autômatos
  • Código: 2ECOM.035
  • Departamento: DECOM
  • Lista de discussão: decom035@googlegroups.com
  • Termo:
  • Encontros:
    • Sala: 414, Prédio 20 (Teórica)
      Horários:
      Terça-feira: 
      13:00 às 14:50
      Quinta-feira: 
      13:00 às 14:50

Regras

  • Gerais
    • Todas as entregas são feitas no SIGAA em formato PDF
    • Cópias, de qualquer natureza, são penalizadas com nota zero
    • Entregas atrasadas não são consideradas
    • Toda a comunicação é feita exclusivamente via twitter (avisos) e lista de discussão (conteúdo)
    • Dúvidas da matéria somente pela lista de discussão (ignorados em outros e-mails)
  • Provas
    • Individual
    • Sem consulta
    • Esperar pelo menos 30 minutos antes de entregar a prova
  • Listas
    • Individual
    • Entregar na semana posterior ao conteúdo dado
  • Trabalhos
    • Individual ou em dupla (de dois, ok?)
  • Extras
    • No máximo 5 pontos extras
    • Erros nos slides valem 0,5pts (postar na lista de discussão)
    • Resenha do filme O Jogo da Imitação vale 2pts

Pontuação

Aluno(a): 
- /
75 pts
- /
15 pts
Trabalho
- /
10 pts
Extras
- /
5 pts
Total
- /
100 pts

Prova especial
- /
100 pts
Total
- /
100 pts

Ementa

  • Conceitos básicos das linguagens formais
  • Linguagens regulares: livres de contexto, sensíveis ao contexto e irrestritas
  • Introdução ao parsing
  • Autômatos finitos e expressões regulares
  • Autômatos de pilha
  • Máquinas de Turing
  • Hierarquia das classes de linguagens

Aulas

aula vídeo lista descrição
Apresentação da disciplina: ...
Conceitos preliminares: ...
Autômatos finitos determinísticos (AFD): ...
Minimização de AFD's: ...
Propriedades de AFD's: ...
Autômatos finitos não determinísticos (AFN): ...
LR's: Lema do bombeamento e propriedades de fechamento: ...
Expressões regulares: ...
Gramáticas regulares: ...
Autômatos de pilha (AP): ...
Gramática livre de contexto (GLC): ...
Formas Normais sobre GLC's: ...
LLC's: Lema do bombeamento e propriedades de fechamento: ...
Máquinas de Turing (MT): ...
Variações de máquinas de Turing: ...
Decidibilidade: ...

Trabalhos

tp vídeo data descrição
24/06 Máquina de Turing Não-Determinística:  Implementar um programa de computador que receba uma especificação de uma Máquina de Turing (MT) não-determinística e uma palavra de entrada e verifique se essa palavra pertence ou não a linguagem descrita por essa máquina.

Calendário

Março 2024

dia sem. tipo descrição
05 ter
teoria
Apresentação da disciplina
07 qui
teoria
Conceitos preliminares: representações, provas de teoremas, conjuntos
12 ter
teoria
Conceitos preliminares: relações, funções, conjuntos enumeráveis
14 qui
teoria
Conceitos preliminares: definições recursivas, indução, grafos
19 ter
teoria
Conceitos preliminares: linguagens formais, gramáticas, problemas de decisão
21 qui
teoria
Autômatos finitos determinísticos (AFD)
26 ter
teoria
Minimização de AFD's
28 qui
feriado
Recesso escolar: Paixão de Cristo

Abril 2024

dia sem. tipo descrição
02 ter
teoria
Propriedades de AFD's
04 qui
teoria
Autômatos finitos não determinísticos (AFN) e equivalência entre AFD's e AFN's
09 ter
teoria
AFN estendido e AFN λ
11 qui
exercício
Resolução de exercícios
16 ter
prova
Prova 1
18 qui
teoria
LR's: Lema do bombeamento e propriedades de fechamento
23 ter
teoria
Gramáticas regulares
25 qui
teoria
Expressões regulares
30 ter
teoria
Autômatos de pilha determinístico (APD)

Maio 2024

dia sem. tipo descrição
02 qui
teoria
Autômatos de pilha não determinístico (APN)
07 ter
teoria
Gramáticas livres de contexto (GLC)
09 qui
teoria
Derivação, ambiguidade e manipulação de GLC’s
14 ter
teoria
Formas normais sobre GLC's
16 qui
exercício
Resolução de exercícios
21 ter
prova
Prova 2
23 qui
teoria
LLC's: Lema do bombeamento e propriedades de fechamento
28 ter
teoria
Máquinas de Turing
30 qui
feriado
Feriado nacional: Corpus Christi

Junho 2024

dia sem. tipo descrição
04 ter
teoria
Propriedades de Máquinas de Turing
06 qui
teoria
Variações de máquinas de Turing: cabeçote imóvel, múltiplas trilhas, fita ilimitada em ambas as direções
11 ter
teoria
Variações de máquinas de Turing: múltiplas fitas, não determinística
13 qui
teoria
Decidibilidade: tese de Church-Turing, MT's e PD's, MT Universal
18 ter
teoria
Decidibilidade: problema da parada, redução e teorema de Rice
20 qui
exercício
Resolução de exercícios
25 ter
prova
Prova 3
27 qui
exercício
Resolução de exercícios

Julho 2024

dia sem. tipo descrição
02 ter
prova
Prova suplementar
04 qui
exercício
Resolução de exercícios
09 ter
prova
Prova especial