Informações
- Curso: Linguagens Formais e Autômatos
- Código: G00LFAU0.01
- Departamento: DECOM
- Lista de discussão: decom035@googlegroups.com
- Termo:
- Encontros:
-
Sala: 407 (Prédio 20) (Teórica)Horários:Terça-feira:10:40 às 12:20Quinta-feira:10:40 às 12:20
-
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
- 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
- Fazer de forma individual, manuscrita e digitalizada para PDF
- Fazer mais que 50% para ser considerada
- 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)
Pontuação
Aluno(a):
- /
90 pts
- /
10 pts
- /
5 pts
- /
100 pts
- /
100 pts
- /
100 pts
Ementa
- Gramáticas
- Linguagens formais
- Expressões regulares
- Linguagens regulares
- Autômatos finitos determinísticos
- Autômatos finitos não determinísticos
- Gramáticas livres de contexto
- Autômatos com pilha
- Linguagens recursivas
- Máquinas de Turing
- Decidibilidade
Aulas
Calendário
Agosto 2026
| dia | sem. | tipo | descrição |
|---|---|---|---|
| 06 | qui | teoria |
Apresentação da disciplina |
| 11 | ter | teoria |
Conceitos preliminares: representações, provas de teoremas, conjuntos |
| 13 | qui | teoria |
Conceitos preliminares: relações, funções, conjuntos enumeráveis |
| 18 | ter | teoria |
Conceitos preliminares: definições recursivas, indução, grafos |
| 20 | qui | teoria |
Conceitos preliminares: linguagens formais |
| 25 | ter | teoria |
Conceitos preliminares: gramáticas, problemas de decisão |
| 27 | qui | teoria |
Autômatos finitos determinísticos (AFDs) |
Setembro 2026
| dia | sem. | tipo | descrição |
|---|---|---|---|
| 01 | ter | teoria |
Minimização e propriedades de AFDs |
| 03 | qui | teoria |
Autômatos finitos não determinísticos (AFNs) |
| 08 | ter | teoria |
Equivalência entre AFDs e AFNs e AFN estendido |
| 10 | qui | exercício |
Resolução de exercícios |
| 15 | ter | prova |
Prova 1 |
| 17 | qui | teoria |
LRs: lema do bombeamento e propriedades de fechamento |
| 22 | ter | teoria |
Gramáticas regulares (GRs) |
| 24 | qui | teoria |
Expressões regulares (ERs) |
| 29 | ter | teoria |
Autômatos com pilha determinísticos (APDs) |
Outubro 2026
| dia | sem. | tipo | descrição |
|---|---|---|---|
| 01 | qui | teoria |
Autômatos com pilha não determinísticos (APNs) |
| 06 | ter | teoria |
Gramáticas livres de contexto (GLCs), derivações e ambiguidade |
| 08 | qui | teoria |
Manipulações de GLCs |
| 13 | ter | exercício |
Resolução de exercícios |
| 15 | qui | prova |
Prova 2 |
| 20 | ter | teoria |
Forma normal de Chomsky |
| 22 | qui | teoria |
Forma normal de Greibach |
| 27 | ter | teoria |
LLCs: lema do bombeamento e propriedades de fechamento |
| 29 | qui | teoria |
Máquinas de Turing (1/2) |
Novembro 2026
| dia | sem. | tipo | descrição |
|---|---|---|---|
| 03 | ter | teoria |
Máquinas de Turing (2/2) |
| 05 | qui | teoria |
Propriedades de máquinas de Turing |
| 10 | ter | teoria |
Variações de máquinas de Turing: cabeçote imóvel, múltiplas trilhas, fita ilimitada em ambas as direções |
| 12 | qui | teoria |
Variações de máquinas de Turing: múltiplas fitas e não determinísticas |
| 17 | ter | teoria |
Decidibilidade: tese de Church-Turing, MTs e PDs, MT universal |
| 19 | qui | teoria |
Decidibilidade: problema da parada, redução de um problema a outro e teorema de Rice |
| 24 | ter | exercício |
Resolução de exercícios |
| 26 | qui | prova |
Prova 3 |
Dezembro 2026
| dia | sem. | tipo | descrição |
|---|---|---|---|
| 01 | ter | exercício |
Resolução de exercícios |
| 03 | qui | prova |
Prova suplementar |
| 08 | ter | feriado |
Feriado regional: Nossa Senhora da Conceição |
| 10 | qui | prova |
Prova especial |