Informations
- Course: Linguagens Formais e Autômatos
- Code: 2ECOM.035
- Departament: DECOM
- Discussion list: decom035@googlegroups.com
- Term:
- Meetings:
-
Room: 414, Prédio 20 (Theory)Schedules:Tuesday:13:00 to 14:50Thursday:13:00 to 14:50
-
Rules
-
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
Grading
Student:
- /
75 pts
- /
15 pts
- /
10 pts
- /
5 pts
- /
100 pts
- /
100 pts
- /
100 pts
Syllabus
- 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
Lessons
Homeworks
Calendar
March 2024
| day | week | type | description |
|---|---|---|---|
| 05 | tue | theory |
Apresentação da disciplina |
| 07 | thu | theory |
Conceitos preliminares: representações, provas de teoremas, conjuntos |
| 12 | tue | theory |
Conceitos preliminares: relações, funções, conjuntos enumeráveis |
| 14 | thu | theory |
Conceitos preliminares: definições recursivas, indução, grafos |
| 19 | tue | theory |
Conceitos preliminares: linguagens formais, gramáticas, problemas de decisão |
| 21 | thu | theory |
Autômatos finitos determinísticos (AFD) |
| 26 | tue | theory |
Minimização de AFD's |
| 28 | thu | holiday |
Recesso escolar: Paixão de Cristo |
April 2024
| day | week | type | description |
|---|---|---|---|
| 02 | tue | theory |
Propriedades de AFD's |
| 04 | thu | theory |
Autômatos finitos não determinísticos (AFN), equivalência entre AFD's e AFN's, AFN estendido e AFN λ. |
| 09 | tue | exercise |
Resolução de exercícios |
| 11 | thu | exam |
Prova 1 |
| 16 | tue | theory |
LR's: Lema do bombeamento e propriedades de fechamento |
| 18 | thu | theory |
Gramáticas regulares |
| 23 | tue | theory |
Expressões regulares |
| 25 | thu | theory |
Autômatos de pilha determinístico (APD) |
| 30 | tue | theory |
Autômatos de pilha não determinístico (APN) |
May 2024
| day | week | type | description |
|---|---|---|---|
| 02 | thu | theory |
Gramáticas livres de contexto (GLC) |
| 07 | tue | theory |
Derivação, ambiguidade e manipulação de GLC’s |
| 09 | thu | theory |
Forma normal de Chomsky |
| 14 | tue | theory |
Forma normal de Greibach |
| 16 | thu | exercise |
Resolução de exercícios |
| 21 | tue | exam |
Prova 2 |
| 23 | thu | theory |
LLC's: Lema do bombeamento e propriedades de fechamento |
| 28 | tue | theory |
Máquinas de Turing |
| 30 | thu | holiday |
Feriado nacional: Corpus Christi |
June 2024
| day | week | type | description |
|---|---|---|---|
| 04 | tue | theory |
Propriedades de Máquinas de Turing |
| 06 | thu | theory |
Variações de máquinas de Turing: cabeçote imóvel, múltiplas trilhas, fita ilimitada em ambas as direções |
| 11 | tue | theory |
Variações de máquinas de Turing: múltiplas fitas, não determinística |
| 13 | thu | theory |
Decidibilidade: tese de Church-Turing, MT's e PD's, MT Universal |
| 18 | tue | theory |
Decidibilidade: problema da parada, redução e teorema de Rice |
| 20 | thu | exercise |
Resolução de exercícios |
| 25 | tue | exam |
Prova 3 |
| 27 | thu | exercise |
Resolução de exercícios |
July 2024
| day | week | type | description |
|---|---|---|---|
| 02 | tue | exam |
Prova suplementar |
| 04 | thu | exercise |
Resolução de exercícios |
| 09 | tue | exam |
Prova especial |