Informations
- Course: Linguagens Formais e Autômatos
- Code: G00LFAU0.01
- Departament: DECOM
- Discussion list: decom035@googlegroups.com
- Term:
- Meetings:
-
Room: 120, Prédio 1 (Principal) (Theory)Schedules:Tuesday:10:40 to 12:20Thursday:10:40 to 12:20
-
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
- A comunicação é feita via SIGAA (avisos) e lista de discussão (conteúdo)
- Dúvidas da matéria somente pela lista de discussão (ignoradas 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
-
Extras
- No máximo 5 pontos extras
- Erros nos slides valem 0,25pts (postar na lista de discussão até antes da terceira prova)
Grading
Student:
- /
75 pts
- /
24 pts
- /
1 pt
- /
5 pts
- /
100 pts
- /
100 pts
- /
100 pts
Syllabus
- Gramáticas
- Linguagens formais
- Expressões regulares
- Linguagens regulares
- Autômatos finitos determinísticos
- Autômatos finitos não determinístico
- Gramáticas livres de contexto
- Autômatos de pilha
- Linguagens recursivas
- Máquinas de Turing
- Decidibilidade
Lessons
Calendar
March 2025
| day | week | type | description |
|---|---|---|---|
| 27 | thu | theory |
Apresentação da disciplina |
April 2025
| day | week | type | description |
|---|---|---|---|
| 01 | tue | theory |
Conceitos preliminares: representações, provas de teoremas, conjuntos |
| 03 | thu | theory |
Conceitos preliminares: relações, funções, conjuntos enumeráveis |
| 08 | tue | theory |
Conceitos preliminares: definições recursivas, indução, grafos |
| 10 | thu | theory |
Conceitos preliminares: linguagens formais, gramáticas, problemas de decisão |
| 15 | tue | theory |
Autômatos finitos determinísticos (AFDs) |
| 17 | thu | holiday |
Recesso escolar: Paixão de Cristo |
| 22 | tue | theory |
Minimização de AFDs |
| 24 | thu | theory |
Propriedades de AFDs |
| 29 | tue | theory |
Autômatos finitos não determinísticos (AFNs) |
May 2025
| day | week | type | description |
|---|---|---|---|
| 01 | thu | holiday |
Feriado nacional: Dia do Trabalhador |
| 06 | tue | theory |
Equivalência entre AFDs e AFNs e AFN estendido |
| 08 | thu | exercise |
Resolução de exercícios |
| 13 | tue | exam |
Prova 1 |
| 15 | thu | theory |
LRs: lema do bombeamento e propriedades de fechamento |
| 20 | tue | theory |
Expressões regulares (ERs) |
| 22 | thu | theory |
Gramáticas regulares (GRs) |
| 27 | tue | theory |
Autômatos de pilha determinístico (APDs) |
| 29 | thu | theory |
Autômatos de pilha determinístico (APNs) |
June 2025
| day | week | type | description |
|---|---|---|---|
| 03 | tue | theory |
Gramáticas livres de contexto (GLCs), derivaçoes, ambiguidade e manipulações |
| 05 | thu | exercise |
Resolução de exercícios |
| 10 | tue | exam |
Prova 2 |
| 12 | thu | theory |
Forma normal de Chomsky e Greibach |
| 17 | tue | theory |
LLCs: lema do bombeamento e propriedades de fechamento |
| 19 | thu | holiday |
Feriado nacional: Corpus Christi |
| 24 | tue | theory |
Máquinas de Turing e propriedades de máquinas de Turing |
| 26 | thu | theory |
Variações de máquinas de Turing: cabeçote imóvel, múltiplas trilhas, fita ilimitada em ambas as direções |
July 2025
| day | week | type | description |
|---|---|---|---|
| 01 | tue | theory |
Variações de máquinas de Turing: múltiplas fitas e não determinística |
| 03 | thu | theory |
Decidibilidade: tese de Church-Turing, MTs e PDs, MT universal |
| 08 | tue | theory |
Decidibilidade: problema da parada, redução de um problema a outro e teorema de Rice |
| 10 | thu | exercise |
Resolução de exercícios |
| 15 | tue | exam |
Prova 3 |
| 17 | thu | exercise |
Resolução de exercícios |
| 22 | tue | exam |
Prova suplementar |
| 24 | thu | exercise |
Resolução de exercícios |
| 29 | tue | exam |
Prova especial |