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:50Quinta-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
- /
10 pts
- /
5 pts
- /
100 pts
- /
100 pts
- /
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
Trabalhos
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 |