Informações

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

Regras

  • Gerais
    • Cópias, de qualquer natureza, serão penalizadas com nota zero
    • Entregas atrasadas não serão consideradas
    • Toda a comunicação será 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 manuscrita 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
04/07 Greibach:  Implementar um programa que recebe uma gramática livre de contexto (GLC) G e a transforme em uma GLC G' equivalente na forma normal de Greibach.

Calendário

Março 2022

dia sem. tipo descrição
22 ter
feriado
Semana de acolhimento
24 qui
feriado
Semana de acolhimento
29 ter
teoria
Conceitos preliminares: representações, provas de teoremas, conjuntos, relações, funções, conjuntos enumeráveis
31 qui
teoria
Conceitos preliminares: definições recursivas, indução, grafos, linguagens formais, gramáticas, problemas de decisão

Abril 2022

dia sem. tipo descrição
05 ter
teoria
Autômatos finitos determinísticos (AFD)
07 qui
teoria
Minimização de AFD's
12 ter
teoria
Propriedades de AFD's
14 qui
feriado
Recesso escolar: Paixão de Cristo
19 ter
teoria
Autômatos finitos não determinísticos (AFN)
21 qui
feriado
Feriado nacional: Tiradentes
26 ter
teoria
Equivalência entre AFD's e AFN's, AFN estendido e AFN λ
28 qui
exercício
Resolução de exercícios

Maio 2022

dia sem. tipo descrição
03 ter
prova
Prova 1
05 qui
teoria
LR's: Lema do bombeamento e propriedades de fechamento
10 ter
teoria
Expressões regulares
12 qui
teoria
Gramáticas regulares
17 ter
teoria
Autômatos de pilha determinístico (APD)
19 qui
teoria
Autômatos de pilha não determinístico (APN)
24 ter
teoria
Gramáticas livres de contexto (GLC)
26 qui
teoria
Derivação, ambiguidade e manipulação de GLC’s
31 ter
teoria
Formas normais sobre GLC's

Junho 2022

dia sem. tipo descrição
02 qui
exercício
Resolução de exercícios
07 ter
prova
Prova 2
09 qui
teoria
LLC's: Lema do bombeamento e propriedades de fechamento
14 ter
teoria
Máquinas de Turing e propriedades
16 qui
feriado
Feriado nacional: Corpus Christi
21 ter
teoria
Variações de máquinas de Turing: cabeçote imóvel, múltiplas trilhas e fita ilimitada em ambas as direções
23 qui
teoria
Variações de máquinas de Turing: múltiplas fitas e não determinística
28 ter
teoria
Decidibilidade: tese de Church-Turing, MT's e PD's, MT Universal
30 qui
teoria
Decidibilidade: problema da parada, redução e teorema de Rice

Julho 2022

dia sem. tipo descrição
05 ter
exercício
Resolução de exercícios
07 qui
prova
Prova 3
12 ter
exercício
Resolução de exercícios
14 qui
prova
Prova suplementar
19 ter
prova
Prova especial