---

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

🚨 Avisos importantes (fique atento sempre!)

📌 [15/02/23] Atenção! A prova de recuperação será na sala S-209-0 (mesma sala que estávamos usando para as aulas).
[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

🙋 Dias, horários e locais dos atendimentos

🧐 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:

• conhecimentos de programação (em qualquer linguagem imperativa)
• familiaridade com estruturas de dados básicas (vetores, pilhas),
• familiaridade com linguagem matemática (conjuntos, sequências, relações, funções),
• capacidade para reconhecer argumentos lógicos em uma demonstração matemática.

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:

• Livro de Bases Matemáticas, dos profs. Armando Caputi e Daniel Miranda, da UFABC.
• Fundamentos da matemática para computação, (videoaulas) do prof. Cláudio Possani, da USP.
• Meus vídeos com definição e exemplos de indução.
• Notas de aula da disciplina de Estruturas de Dados do prof. Rafael Schouery, da Unicamp (introdução à programação em C, recursão, listas, pilhas e filas, árvores).
• Notas de aula da disciplina de Programação Estruturada (introdução à programação em C, recursão, vetores e listas).

📚 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

• Sobre qualquer material feito por mim, participe do banco de informantes.

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 Conteúdo: Sobre o curso. Formulário de início de curso. Referências: veja seção de recomendação. Material complementar: slides de introdução ao curso e revisão; vídeos sobre indução:

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 Simulando AFDs. Autômatos finitos não determinísticos (AFNs). AFDs vs AFNs. Referências: Seção 1.2 [S] e Seção 2.3 (2.3.1 a 2.3.4 apenas) e 2.5 [HUM]. Material complementar: Slides de simulação de AFDs, funcionamento de afn e AFD vs. AFN. Sobre o JFLAP (outro link para download).

Aula 5 - 05/out AFDs vs AFNs. Simulando AFNs. Propriedades das LRs. Expressões regulares. Referências: Seção 1.1, 1.2, 1.3 [S] e Seção 3.1, 4.2 [HUM]. Material complementar: slides de simulação de AFNs e propriedades das LRs.

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 Conteúdo: Lema do bombeamento para LRs. Referências: Seção 1.4 [S] e Seções 4.1 e 4.3 [HUM]. Material complementar: demonstrações usando o lema do bombeamento para LRs.

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 Conteúdo: Mais exemplos de APs. APs vs GLCs. Propriedades das LLCs. Referências: Seção 2.2 [S] e Seções 6.3 e 7.3 [HUM]. Material complementar: slides da equivalência de APs e LLCs, e das propriedades de fechamento das LLCs.

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 Conteúdo: MTs e algoritmos. Tese Church-Turing. Decidibilidade. Referências: Capítulo 4 [S]. Material complementar: slides com mais exemplos de descrições intermediárias/alto nível de MTs, com representações de objetos com cadeias, com a Tese Church-Turing, e com MUITOS exemplos de decidibilidade.

Aula 17 - 25/nov Conteúdo: O problema da Parada. O método da diagonalização. Problemas Turing-Reconhecíveis e Turing-irreconhecíveis. Referências: Seção 4.2 [S]. Material complementar: slides com as demonstrações completas de conjuntos contáveis e incontáveis. Extras: A história da indecidibilidade (inglês).

Aula 18 - 30/nov Conteúdo: Redução: introdução informal e formal. Referências: Capítulo 5 [S].

02/dez Aula cancelada devido aos jogos da seleção na copa do mundo, conforme Ato Decisório da ConSEPE 233/2022. Reposição no dia 03/dez, Sábado, às 10h

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 Conteúdo: Teoria da complexidade: tempo de execução, notação assintótica, classes P, NP e NP-completo. Referências: Capítulo 7 [S]. Material complementar: slides com as máquinas cujos tempos foram analisados.

Aula 21 - 09/dez Aula cancelada devido aos jogos da seleção na copa do mundo, conforme Ato Decisório da ConSEPE 233/2022. Não haverá reposição dessa aula 😢.

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 na sala S-209-0 (mesma sala das aulas).

👎 Plágio

• Entre outros, o código de ética da UFABC estabelece em seu artigo 25 que é eticamente inaceitável que os discentes:
  1. fraudem avaliações,
  2. fabriquem ou falsifiquem dados,
  3. plagiem ou não creditem devidamente autoria,
  4. aceitem autoria de material acadêmico sem participação na produção,
  5. vendam ou cedam autoria de material acadêmico próprio a pessoas que não participaram da produção.
  
  
• Muitos ainda têm dúvidas sobre a interpretação das regras definidas pelo Código de Ética da UFABC.
• Por esta razão, diversos professores elaboraram um documento (disponível aqui) com vários exemplos e esclarecendo a interpretação das regras acima.
• Abaixo uma versão resumida, que não substitui de modo algum sua leitura:
• Regra 1: Você não pode enviar para avaliação um trabalho que não seja de sua própria autoria ou que seja derivado/baseado em soluções elaboradas por outros.
• Regra 2: Você não pode compartilhar a sua solução com outros alunos nem pedir aos seus colegas que compartilhem as soluções deles com você.
• Regra 3: Nos trabalhos enviados para avaliação você deve indicar eventuais assistências que você tenha recebido.
• Nós encorajamos fortemente que você procure outras pessoas quando houver a necessidade. Discuta o problema e possíveis ideias para soluções, mas elabore sua própria solução, por conta própria.
• Qualquer violação às regras descritas acima implicará em descarte dos conceitos atribuídos a TODAS as tarefas avaliativas regulares de TODOS os envolvidos, causando assim suas reprovações automáticas com conceito F.
• Possível denúncia à Comissão de Transgressões Disciplinares Discentes da Graduação, a qual decidirá sobre a punição adequada à violação que pode resultar em advertência, suspensão ou desligamento, de acordo com os artigos 78-82 do Regimento Geral da UFABC.
• Sempre consulte o documento completo ou converse com o seu professor em caso de dúvidas!

🏋 Listas de exercícios

• Ao todo teremos 4 listas, cujos enunciados serão disponibilizados nessa seção, em breve.
• O objetivo principal é prover problemas representativos dos conceitos vistos, equivalentes aos que serão cobrados nas avaliações.
• Elas não valem nota, mas podem ser entregues nos dias das avaliações (em papel e feitas à mão - capriche na letra!) para serem consideradas como bônus, caso seja necessário.
• Quanto mais exercícios feitos sobre conteúdos diferentes, melhor.
• Resoluções referentes às listas 1 e 2 podem ser entregues no dia da prova 1.
• Resoluções referentes às listas 3 e 4 podem ser entregues no dia da prova 2.
• Você pode reaver suas soluções das listas ao final do curso.
• Se algo te impossibilita de fazer as listas à mão, converse comigo antes de entregar em outro formato.
• Não entregue sua primeira solução! Passe a limpo antes.
• Procure atendimento sempre que tiver dúvidas nos exercícios.
• Finalmente, as listas:
  
  
  • Lista 1 (linguagens regulares - Aulas 2 a 7)
    Essenciais: 4, 7, 8, 9, 14, 17, 18, 19, 20, 21.
  
  
  • Lista 2 (linguagens livres de contexto - Aulas 8 a 11)
    Essenciais: 2, 3, 4, 7, 8.
  
  
  • Lista 3 (máquinas de Turing - Aulas 14 a 17)
  
  
  • Lista 4 (redutibilidade, complexidade e intratabilidade - Aulas 18 a 21)

🎓 Critérios de avaliação

• A avaliação da disciplina constituirá da nota de duas provas, denotadas P₁ e P₂, respectivamente.
• A prova 1 vale 50% da nota e 0 ≤ P₁ ≤ 10.
• A prova 2 vale 50% da nota e 0 ≤ P₂ ≤ 10.
• O conteúdo das provas englobará todos os temas vistos até a data das mesmas.


• Sua média final (MF) antes da recuperação, portanto, será
  
  MF = 0.5 x P1 + 0.5 x P2
• Se você é aluno da pós-graduação, seu conceito final será
  
  A, se MF ≥ 8.5
  B, se 7.0 ≤ MF < 8.5
  C, se 5.0 ≤ MF < 7.0
  F, se MF < 5.0
  
• Se você é aluno da graduação, seu conceito final será
  
  A, se MF ≥ 8.5
  B, se 7.0 ≤ MF < 8.5
  C, se 6.0 ≤ MF < 7.0
  D, se 5.0 ≤ MF < 6.0
  F, se MF < 5.0
  

💯 Notas

Acompanhe aqui as notas das atividades.

💪 Mecanismo de recuperação

• A recuperação será aplicada apenas aos alunos que tiverem conceito final D ou F e que enviarem e-mail confirmando interesse.
• O conteúdo da prova englobará todos os temas vistos durante o quadrimestre.
• A nota obtida na prova de recuperação (NR) será usada obter a nota final com recuperação (NFR), que consiste na média a seguir:
  NFR = max {MF, (MF + NR) / 2}
• Se você é aluno da pós-graduação, o conceito final obtido na recuperação substituirá o conceito original e será
  C, se NFR ≥ 5.0
  F, se NFR < 5.0
  
• Se você é aluno da graduação, o conceito final obtido na recuperação substituirá o conceito original e será
  C, se NFR ≥ 6.0
  D, se 5.0 ≤ NFR < 6.0
  F, se 0.0 ≤ NFR < 5.0
  

🤒 Mecanismos de avaliação substitutivos

• 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.

---