2022 Q3

CCM-104 - Teoria da Computação (Pós)

COMPARTILHADA: MCTA015-13 - Linguagens Formais e Automata

Professora: Carla Negri Lintzmayer, carla.negri@ufabc.edu.br

piadinha


🚨 Avisos importantes (fique atento sempre!)

📌 [19/12] Avisos (semi-)finais importantes:
  1. Corrigi a prova 2 e calculei os conceitos finais, já acrescentando um bônus devido às listas.
  2. As notas finais (pré-rec) estão na planilha na seção de notas.
  3. A prova de recuperação pode ser realizada por qualquer aluno que ficou com conceito D ou F E QUE me envie um e-mail até o dia 28 de fevereiro avisando.
  4. Por fim, estarei disponível pelo Discord para tirar dúvidas sobre a recuperação a qualquer momento do recesso.
  5. No dia 1 de março, entre 13h e 19h, estarei na minha sala para fazer atendimento (tirar dúvidas para a prova de recuperação ou mesmo revisão da P2). Basta aparecer!
[08/dez] As listas 3 e 4 tinham pequenos errinhos e foram atualizadas.
[06/dez] Atenção! A aula do dia 9/12 está cancelada devido aos jogos da seleção na copa do mundo, conforme Ato Decisório da ConSEPE 233/2022. Não haverá reposição. Portanto, aula do dia 7/12 é a última aula de conteúdo antes da prova 2.
[20/nov] A lista 4 está liberada.
[20/nov] Corrigi a prova 1 e as notas estão na planilha na seção de notas. A vista das provas poderá ser feita em qualquer horário de atendimento, que sempre ocorre logo após as aulas.
[16/nov] Atenção! A prova 2 estava com a data errada. O dia correto é 14 de dezembro.
[16/nov] A lista 3 está liberada.
[19/out] A lista 2 está liberada. Também houve mudança no horário de atendimento do dia 4/11.
[18/ago] Site no ar. Estude-o como se o seu conteúdo fosse ser cobrado em prova.


📝 Dias, horários e locais das aulas

Quartas-feiras, das 16h às 18h, na sala S-209-0.

Sextas-feiras, das 16h às 18h, na sala S-209-0.



🙋 Dias, horários e locais dos atendimentos

Quartas-feiras, das 18h às 19h, na sala de aula ou na sala da docente.

Sextas-feiras, das 18h às 19h, na sala de aula ou na sala da docente.



🧐 Ementa da disciplina

CCM-104

Linguagens Regulares; Autômato finito; Não-determinismo; Aplicações de autômato finito; Expressões regulares; Aplicações de expressões regulares; Linguagens que não são regulares; Linguagens livres de contexto; Gramáticas livres de contexto; Aplicações de gramáticas livres de contexto; Autômato de pilha; Linguagens que não são livres de contexto; Máquinas de Turing; Decidibilidade; Linguagens decidíveis; O problema da parada; Linguagens indecidíveis.



🖖 Recomendação

Para facilitar o acompanhamento do curso, é recomendado que você possua:

Preparei esse material de 🔥revisão🔥 que contém tudo que precisamos na disciplina. Também tenho vídeos com definição e exemplos de indução.

Outros materiais de apoio:



📚 Bibliografia e outros materiais

  1. [S] Sipser, M.. Introdução à teoria da computação. 2a edição. Thomson Learning. 2007. (ERRATA da versão em inglês. Tanto em inglês quanto em português, existem vários errinhos.)
  2. [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.
  3. [V] Vieira, N. J.. Introdução aos Fundamentos da Computação: Linguagens e Máquinas. 1a edição. Cengage Learning. 2006.


📆 Cronograma



ATENÇÃO! O conteúdo exato e materiais de apoio de cada aula são atualizados durante o quadrimestre.
As aulas que já foram ministradas estão coloridas.


Aula 1 - 21/set
Aula 2 - 23/set
  • Conteúdo: Alfabetos e linguagens. Autômatos finitos determinísticos (AFDs).
  • Referências: Seção 1.1 [S] e Seção 2.2 [HUM].
Aula 3 - 28/set
  • Conteúdo: Linguagens Regulares (LR). Demonstração de linguagem de AFD. Projeto de AFDs.
  • Referências: Seção 1.1, 1.2 [S] e Seção 2.2, 2.3 (2.3.1 a 2.3.4) [HUM].
  • Material complementar: slides da demonstração.
Aula 4 - 30/set
Aula 5 - 05/out
Aula 6 - 07/out
  • Conteúdo: Expressões regulares vs. autômatos. Algoritmos de conversão.
  • Referências: Seção 1.3 [S] e Seção 3.2 [HUM].
  • Material complementar: slides de expressões regulares.
12/out (Feriado Padroeira do Brasil)
  • Reposição em 12/dez (segunda-feira).
Aula 7 - 14/out
Aula 8 - 19/out
  • Conteúdo: Gramáticas livres de contexto (GLC). Linguagens livres de contexto (LLCs).
  • Referências: Seção 2.1 [S] e Seções 5.1 e 5.2 [HUM].
  • Material complementar: slides da demonstração e do resumo da demonstração da linguagem de uma GLC, e prova completa de que toda LR é LLC.
Aula 9 - 21/out
  • Conteúdo: Mais exemplos com GLCs. Autômatos com pilha (APs).
  • Referências: Seções 2.1 e 2.2 [S] e Seções 6.1 e 6.2 [HUM].
Aula 10 - 26/out
28/out (Feriado Servidor Público)
  • Reposição em 13/dez (terça-feira).
02/nov (Feriado Finados)
  • Reposição em 14/dez (quarta-feira).
Aula 11 - 04/nov
  • Conteúdo: Lema do bombeamento para LLCs.
  • Referências: Seção 2.3 [S] e Seções 7.2 e 7.4 [HUM].
  • ATENÇÃO! O horário de atendimento neste dia será a partir das 14h30, na sala de aula (S-209-0). NÃO haverá atendimento após a aula.
  • Material EXTRA: demonstração do lema do bombeamento para LLCs.
Aula 12 - 09/nov
  • Checkpoint: aula extra / revisão e dúvidas para prova.
  • ATENÇÃO! NÃO haverá atendimento após a aula.
Aula 13 - 11/nov
  • Prova 1
  • ATENÇÃO! NÃO haverá atendimento após a prova.
Aula 14 - 16/nov
  • Conteúdo: Máquinas de Turing (MTs).
  • Referências: Seção 3.1 [S].
Aula 15 - 18/nov
  • Conteúdo: Mais exemplos de MTs. Variações de MTs.
  • Referências: Seções 3.2, 3.3 [S], Seção 8.6 [HUM].
Aula 16 - 23/nov
Aula 17 - 25/nov
Aula 18 - 30/nov
  • Conteúdo: Redução: introdução informal e formal.
  • Referências: Capítulo 5 [S].
02/dez
Aula 19 - 03/dez (no sábado, às 10h, por ser reposição)
  • Conteúdo: Exemplos de redução para provar indecidibilidade e irreconhecibilidade.
  • Referências: Capítulo 5 [S].
Aula 20 - 07/dez
Aula 21 - 09/dez
Aula 22 - 12/dez (na segunda-feira, às 16h, por ser reposição)
  • Checkpoint: aula extra / revisão e dúvidas para prova.
  • ATENÇÃO! NÃO haverá atendimento após essa aula.
Aula 23 - 13/dez (na terça-feira às 16h, por ser reposição)
  • Conteúdo (extra): Teorema Cook-Levin.
  • Referências: Seção 7.4 [S].
Aula 24 - 14/dez (na quarta-feira às 16h, por ser reposição)
  • Prova 2
  • ATENÇÃO! NÃO haverá atendimento após a prova.
RECUPERAÇÃO - 04/mar (quadrimestre seguinte)
  • Prova de recuperação para os alunos que ficaram com conceito D ou F ***E QUE*** enviarem e-mail indicando interesse.
  • Das 10h às 12h em uma sala a definir (veja esse site novamente quando estivermos mais próximos da data).


👎 Plágio



🏋 Listas de exercícios



🎓 Critérios de avaliação



💯 Notas

Acompanhe aqui as notas das atividades.



💪 Mecanismo de recuperação



🤒 Mecanismos de avaliação substitutivos




Carla Negri Lintzmayer - carla.negri@ufabc.edu.br