MCTA015-13 - Linguagens Formais e Automata (2020 Q1)

Professora: Carla Negri Lintzmayer, Sala 508-2, carla.negri@ufabc.edu.br

🚨 Avisos importantes (fique atento sempre!)

🆕 [25/03] Atenção: [23/03] A suspensão das aulas continua até 29 de março, por enquanto (veja portaria).
[20/03] Existe um grupo de Whatsapp da disciplina (mantido pelos alunos, eu não faço parte).
[17/03] Criei um grupo no Discord para nos comunicarmos melhor durante essa pausa.
[15/03] Sobre a paralisação das aulas entre 16 e 22 de março: [10/03] Liberada parte 4 da lista 1.
[06/03] A parte 3 da lista 1 foi levemente alterada.
[05/03] Atenção! A data da Prova 1 foi adiada em uma semana (veja o cronograma). Em caso de qualquer problema, me avise o quanto antes.
[03/03] Liberada parte 3 da lista 1.
[29/02] Disponibilizado material extra sobre processamento de AFNs.
[28/02] Liberada parte 2 da lista 1.
[18/02] Liberada parte 1 da lista 1.
[05/02] Página da disciplina no ar.

Conteúdo dessa página

piadinha

🕐 Dias, horários e local das aulas (voltar ao topo)

Terças-feiras, das 19h às 21h, sala S-301-2.
Sextas-feiras, das 21h às 23h, sala S-301-2.

🆘 Dias, horários e local de atendimento (voltar ao topo)

Neste quadrimestre o conteúdo da disciplina será unificado com a turma do Prof. Maycon Sambinelli.

Assim, vocês podem escolher livremente entre os horários abaixo:

Nesse horários não é preciso confirmar ou marcar, apenas apareça!

Horários para aqueles que não podem nos acima (favor enviar e-mail até as 18h para confirmar):

Se não puder, me mande um e-mail para combinarmos outro horário.
Algumas dúvidas (mais simples) podem ser tiradas por e-mail.

🤓 Ementa da disciplina (voltar ao topo)

Conceitos básicos. Linguagens regulares: autômatos determinísticos e não-determinísticos, expressões regulares. Linguagens livres de contexto: gramática, autômatos a pilha. Linguagens recursivamente enumeráveis: máquinas de Turing determinísticas e não-determinísticas. Indecidibilidade: o problema da parada. Complexidade: definição das classes P e NP.

Objetivos: (i) Apresentar os conceitos fundamentais da teoria da computação. (ii) Familiarizar o aluno com modelos teóricos de um computador e o tratamento formal de tais modelos. (iii) Apresentar ao aluno as diferentes classes de linguagens. (iv) Preparar o aluno para o posterior estudo de técnicas de construção de Compiladores e processamento de Linguagem Natural. (v) Refinar a habilidade do aluno para tratar com conceitos formais abstratos.

(Disponível na pg. 63 do projeto pedagógico.)

🤯 Recomendação (voltar ao topo)

Disciplinas: Programação Estruturada; Matemática Discreta; Algoritmos e Estruturas de Dados I.

Para facilitar o acompanhamento do curso, é recomendado que você possua: Materiais de apoio para esses tópicos:

📖 Bibliografia e outros materiais (voltar ao topo)

[S] Sipser, M.. Introdução à teoria da computação. 2a edição. Thomson Learning. 2007.
[HUM] Hopcroft, J. E.; Ullman, D. J.; Motwani, R.. Introdução à teoria de autômatos, linguagens e computação. 2a edição. Editora Campus. 2003.
[V] Vieira, N. J.. Introdução aos Fundamentos da Computação: Linguagens e Máquinas. 1a edição. Cengage Learning. 2006.

📆 Cronograma (voltar ao topo)

As referências utilizadas nas aulas serão atualizadas durante o curso.

Aula Data Tópicos
1 11/02 Objetivo do curso. Revisão de conceitos importantes para o curso.
✏️ Referências: veja materiais na seção de recomendação.
✏️ Slides usados em sala: introdução ao curso e revisão.
2 14/02 Alfabetos e linguagens. Autômatos finitos determinísticos.
✏️ Referências: Seção 1.1 [S].
✏️ Extras: Slides do prof. Maycon. Programa para brincar com autômatos. Introdução, AFD (Vídeo-aulas prof. Lucrédio UFSCar).
3 18/02 🌧️ Construção de autômatos finitos determinísticos. Linguagens regulares.
✏️ Referências: Seção 1.1 [S].
✏️ Extras: Slides do prof. Maycon. AFD (Vídeo-aulas prof. Lucrédio UFSCar).
4 21/02 Construção de autômatos finitos determinísticos. Linguagens regulares.
✏️ Referências: Seção 1.1 [S].
✏️ Extras: Slides do prof. Maycon. AFD (Vídeo-aulas prof. Lucrédio UFSCar).
🛀 25/02 Feriado: Carnaval (reposição em 06/05)
5 28/02 Autômatos finitos não determinísticos.
✏️ Referências: Seção 1.2 [S].
✏️ Extras: Slides com detalhes de como um AFN processa cadeias. Slides do prof. Maycon. AFN (Vídeo-aulas prof. Lucrédio UFSCar).
6 03/03 Autômatos finitos determinísticos vs. não determinísticos. Propriedades de linguagens regulares.
✏️ Referências: Seção 1.1, 1.2 [S].
✏️ Extras: Slides sobre AFN e propriedades dados em sala. Transições epsilon, AFN vs. AFD (Vídeo-aulas prof. Lucrédio UFSCar).
7 06/03 Autômatos finitos determinísticos e não determinísticos.
✏️ Referências: Seção 1.1, 1.2 [S].
✏️ Extras: Slides dados em sala.
8 10/03 Expressões regulares.
✏️ Referências: Seção 1.3 [S].
✏️ Extras: Slides com o conteúdo dado em sala. Expressões regulares, Expressões vs. autômatos, Expressões regulares na prática (Vídeo-aulas prof. Lucrédio UFSCar).
9 13/03 Expressões regulares.
✏️ Referências: Seção 1.3 [S].
✏️ Extras: Slides com o conteúdo dado em sala.
17/03 Aula cancelada devido ao surto do COVID-19.
20/03 Aula cancelada devido ao surto do COVID-19.
10 ?? Lema do bombeamento.
11 ?? Gramáticas livres de contexto e linguagens livres de contexto.
12 ?? Autômatos com pilha.
13 ?? Propriedades de linguagens livres de contexto. Lema do bombeamento.
14 ?? Solução de exercícios.
15 ?? 📝 Prova 1
16 ?? Solução P1. Máquinas de Turing.
17 ?? Máquinas de Turing e algoritmos. Tese Church-Turing.
18 ?? Linguagens recursivas. Decidibilidade.
19 ?? Indecidibilidade. Linguagens recursivamente enumeráveis.
20 ?? Redutibilidade. Complexidade.
21 ?? Intratabilidade.
22 ?? Solução de exercícios.
23 ?? 📝 Prova 2
24 ?? 📝 Prova de recuperação (sala e horário a definir)

👎 Plágio (voltar ao topo)

🎓 Critérios de avaliação (voltar ao topo)

🏋 Listas de exercícios (voltar ao topo)

Lista 1 - linguagens regulares (disponível em 18/02): parte 1 (AFD), parte 2 (AFN), parte 3 (propriedades), parte 4 (ERs).
Lista 2: linguagens livres de contexto (disponível em 20/03)
Lista 3: máquinas de Turing (disponível em 10/04)
Lista 4: redutibilidade, complexidade e intratabilidade (disponível em 24/04)

💪 Mecanismo de recuperação (voltar ao topo)

🤒 Mecanismos de avaliação substitutivos (voltar ao topo)

A prova substitutiva será aplicada ao aluno que possuir justificativa de ausência em uma das provas. A listagem dos documentos aceitos como justificativa consta na resolução ConsEPE n° 181.
A nota obtida na prova substitutiva necessariamente substituirá a prova para a qual o aluno tem justificativa.

A data para realização da prova substitutiva deverá ser combinada com a professora por e-mail o quanto antes, assim que o aluno estiver em condições de realizá-la.
Carla Negri Lintzmayer - carla.negri@ufabc.edu.br