2021 Q1

MCTA015-13 - Linguagens Formais e Automata

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

🚨 Avisos importantes (fique atento sempre!)

📌 [07/06] Avisos finais:

Corrigi a prova de recuperação. Se você a fez, enviei por email com alguns comentários.
As notas finais estão na planilha na seção de notas.
Se você deseja solicitar revisão de nota, me envie mensagem pelo Discord ou por e-mail indicando qual questão você quer que eu reveja e o motivo de você achar que a minha correção foi errada.
Peço que isso seja feito até o dia 15/06.

[09/05] Avisos (semi-)finais importantes:

Corrigi a prova 2. Se você a fez, enviei por email com alguns comentários.
As notas finais (pré-rec) estão na planilha na seção de notas.
A prova de recuperação pode ser realizada por qualquer aluno que ficou com conceito D ou F.
Se você deseja fazê-la, me envie um email dizendo seu nome e O NOME DA DISCIPLINA no título, por favor.
A PROVA SERÁ ENVIADA APENAS PARA QUEM MANIFESTAR INTERESSE.
Fiz um formulário anônimo de fim de curso com perguntas específicas dessa modalidade à distância.
Peço que você gaste mais esses minutinhos com a disciplina para me ajudar a melhorar: clique aqui.
Se você deseja solicitar revisão de qualquer nota, me envie mensagem PELO DISCORD indicando qual questão você quer que eu reveja e o motivo de você achar que a minha correção foi errada.
Prefira fazer isso amanhã (10/05), pois as notas serão lançadas no dia 11/05.
Por fim, estarei disponível pelo Discord para tirar dúvidas sobre a recuperação a qualquer momento do recesso.

[25/abr] Liberei os bônus das listas 1 e 2. Qualquer dúvida, entrar em contato pelo chat do Discord.
[17/abr] Corrigi a prova 1. Se você a fez, enviei por email com alguns comentários. As notas e os critérios estão na planilha na seção de notas.
[29/mar] Com a manutenção dos calendários acadêmicos nesse período de antecipação de feriados, o cronograma de aulas e atendimentos está mantido. Veja mais no Discord.
[29/mar] Detalhes da prova 1 substitutiva na seção cronograma.
[25/mar] Atenção! Sobre o informe da reitoria, veja a seção de avisos no Discord.
[29/jan] O cronograma foi alterado para seguir o calendário de reposições. Com isso, as provas tiveram Duas datas adiadas em uma semana.
[26/jan] Leia a seção sobre 🔥🔥🔥 como será a disciplina 🔥🔥🔥 sem falta!
[26/jan] Apenas para matriculados e alunos especiais: 🔥🔥🔥 grupo no Discord 🔥🔥🔥 e formulário de início de curso.
[26/jan] Site no ar. Estude-o como se o seu conteúdo fosse ser cobrado na prova (Será que não vai? 🤔).

🙋 Como será a disciplina?

Nosso meio de comunicação principal será o grupo na ferramenta Discord.
Por favor, participe do grupo apenas se você está matriculado na disciplina ou é aluno especial (e falou comigo).
O site sempre será mantido atualizado, porém comunicados menores e atendimentos serão pelo Discord.

Aliás, o servidor no Discord pode e deve ser utilizado em qualquer horário, para atendimento assíncrono.

As videoaulas com os conteúdos da disciplina serão disponibilizadas na seção Cronograma, com antecedência de ao menos uma semana antes da data prevista.
Os conteúdos foram distribuídos da forma como eles seriam dados em um curso presencial.

Atenção! Três aulas serão dadas de forma síncrona, como pode ser visto no cronograma.
A sua participação é essencial nelas, mas elas serão gravadas e disponibilizadas logo em seguida, para quem não puder participar.

Nos horários previstos das aulas, estarei online pela ferramenta Google Meet:

Segundas-feiras, das 21h às 22h30.
Quartas-feiras, das 19h às 21h.

O link do Google Meet está disponível no servidor do Discord.
Esses horários devem ser usados para tirar dúvidas do conteúdo e também para discutir a solução de exercícios.

Sugestão de organização dos estudos: assista aos vídeos com atenção, sem fazer anotações. Depois, leia os materiais de apoio enquanto faz anotações. Existem mais exemplos nesses materiais e detalhes que podem passar despercebidos nos vídeos.

Idealmente, siga o cronograma: se no dia está previsto o conteúdo ×, então use o atendimento para tirar dúvidas sobre ×, mesmo que você tenha só aquele horário para assistir aos vídeos.
Mesmo que você não consiga seguir esse "comportamento ideal", não deixe de usar os horários de atendimento 🥺🙏!

Como estamos fazendo a disciplina à distância, eu preciso confiar no material que você vai me entregar.
Meu único pedido é: seja o autor das suas atividades.
Isso basicamente significa: não copie solução encontrada na internet ou feita por outra pessoa.
É claro que você pode e deve trocar ideias com os colegas, porque isso realmente ajuda no aprendizado.
Eventualmente, ver soluções já prontas também ajuda, mas apenas se você entendê-las tão bem que possa, depois, responder sozinho o mesmo problema.
Qualquer violação às regras descritas na seção sobre plágio 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. Veja detalhes sobre a avaliação na seção Avaliação.

Por fim, o site tem bastante informação, então leia-o com bastante cuidado.
Meu objetivo aqui é que você aprenda o conteúdo dessa disciplina da melhor forma possível.
Por isso, converse comigo sempre.
Qualquer dúvida e feedback são bem vindos, de verdade.
Acho que é isso, boas aulas!

Importante!

Todas as aulas, com e sem participação dos alunos, serão gravadas e disponibilizadas online segundo a Licença Creative Commons Atribuição-Não Comercial 4.0 Internacional (CC-BY-NC).
Todos os participantes do curso dão sua tácita e irrevogável autorização para que suas imagens e falas sejam transmitidas, gravadas e editadas segundo a licença acima pelo docente responsável, sem nenhuma cobrança, para uso em distintos canais de comunicação e peças publicitárias sem fins comerciais.

🧐 Ementa da disciplina

MCTA015-13 - Linguagens Formais e Automata

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.

🖖 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

[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.)
[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.
Grupo do Whatsapp criado e mantido pelos alunos.

📆 Cronograma

Sobre qualquer material feito por mim, participe do banco de informantes.
Cada aula é acompanhada de um quiz, que te ajudará a fixar o conteúdo da mesma.
Playlist completa dos vídeos.
O conteúdo de cada aula será atualizado durante o quadrimestre.

Aula 1 - 1/fev 🎥🎥 LIVE (aula síncrona) 🎥🎥

Sobre o curso e resolução de exercícios de revisão.

Quiz: 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 - 3/fev

Alfabetos e linguagens. Autômatos finitos determinísticos (AFDs). Linguagens regulares (LRs).
Vídeos (tempo total = 89min):
Quiz.
Referências: Seção 1.1 [S] e Seção 2.2 [HUM].
Material complementar: AFD (Vídeo-aulas prof. Lucrédio UFSCar).

Aula 3 - 8/fev

Projeto de AFDs. Simulação de AFDs. (no presencial, essa aula exige sua participação, então faça os exercícios pedidos nos vídeos antes de ver as respostas)
Vídeos (tempo total = 82min):
Quiz.
Referências: Seção 1.1 [S] e Seção 2.2 [HUM].
Material complementar: JFLAP.

Aula 4 - 10/fev

Autômatos finitos não determinísticos (AFNs). (fazer os exercícios da lista 1 após os vídeos)
Vídeos (tempo total = 65min):
Quiz.
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: AFN (Vídeo-aulas prof. Lucrédio UFSCar), Transições epsilon.
Exercícios resolvidos:

15/fev (Feriado carnaval 🎉)

Reposição em 27/04 (terça-feira).
Aproveite para fazer exercícios sobre criação de AFDs e AFNs!

17/fev (Feriado carnaval 🎉)

Reposição em 29/04 (terça-feira).
Aproveite para fazer exercícios sobre criação de AFDs e AFNs!

Aula 5 - 22/fev

AFDs vs AFNs. Simulando AFNs. Propriedades das LRs.
Vídeos (tempo total = 105min - calma, cada um é curtinho :D):
Quiz.
Referências: Seção 1.1, 1.2 [S] e Seção 4.2 [HUM].
Material complementar: AFN vs. AFD (Vídeo-aulas prof. Lucrédio UFSCar).
Exercícios resolvidos:

Aula 6 - 24/fev

Expressões regulares. (no presencial, essa aula exige sua participação, então faça os exercícios pedidos nos vídeos antes de ver as respostas)
Vídeos (tempo total = 38min)
Quiz.
Referências: Seção 1.3 [S] e Seção 3.1 [HUM].
Material complementar: Expressões regulares (Vídeo-aulas prof. Lucrédio UFSCar).

Aula 7 - 1/mar

Expressões regulares vs. autômatos. Algoritmos de conversão.
Vídeos (tempo total = 57min)
Quiz.
Referências: Seção 1.3 [S] e Seção 3.2 [HUM].
Material complementar: Expressões vs. autômatos, Expressões regulares na prática (Vídeo-aulas prof. Lucrédio UFSCar).
Exercícios resolvidos:

Aula 8 - 3/mar

Lema do bombeamento para LRs. Discussão final sobre LRs.
Vídeos (tempo total = 83min)
Quiz.
Referências: Seção 1.4 [S] e Seções 4.1 e 4.3 [HUM].

Aula 9 - 8/mar

Gramáticas livres de contexto (GLC). Linguagens livres de contexto (LLCs).
Vídeos (tempo total = 87min):
Quiz.
Referências: Seção 2.1 [S] e Seções 5.1 e 5.2 [HUM].

Aula 10 - 10/mar

Mais exemplos com GLCs. Autômatos com pilha (APs).
Vídeos (tempo total = 78min):
Quiz.
Referências: Seções 2.1 e 2.2 [S] e Seções 6.1 e 6.2 [HUM].

Aula 11 - 15/mar

APs vs GLCs. Simulação de GLCs e APs. Propriedades das LLCs.
Vídeos (tempo total = 38min):
Quiz.
Referências: Seção 2.2 [S] e Seções 6.3 e 7.3 [HUM].

Aula 12 - 17/mar

Lema do bombeamento para LLCs. Discussão final sobre LLCs.
Vídeos (tempo total = 51min):

Quiz.
Referências: Seção 2.3 [S] e Seções 7.2 e 7.4 [HUM].

Aula 13 - 22/mar 🎥🎥 LIVE (aula síncrona) 🎥🎥

Checkpoint: revisão e dúvidas para prova.
Vídeo (tempo total = 110min):

Aula 14 - 💥💥PROVA 1💥💥 - 24/mar

Das 20h do dia 24/mar às 21h do dia 27/mar - Detalhes serão enviados por e-mail
Lembre-se de entregar as suas respostas das listas 1 e 2 até as 20h do dia 24/mar.

Aula 15 - 29/mar

Máquinas de Turing (MTs).
Vídeos (tempo total = 93min):
Quiz.
Referências: Seção 3.1 [S].

Aula 16 - 31/mar

Variações de MTs. MTs e algoritmos. Tese Church-Turing.
Vídeos (tempo total = 70min):
Quiz.
Referências: Seções 3.2, 3.3 [S], Seção 8.6 [HUM].

Aula 17 - 5/abr

Decidibilidade. O problema da Parada.
Vídeos (tempo total = 40min):
Quiz.
Referências: Capítulo 4 [S].
Extras: A história da indecidibilidade (inglês).

Aula 18 - 7/abr

Problemas Turing-Reconhecíveis e Turing-irreconhecíveis. O método da diagonalização.
Vídeos (tempo total = 56min):
Quiz.
Referências: Seção 4.2 [S].

Aula 19 - 12/abr

Redução: introdução informal e formal.
Vídeos (tempo total = 49min):
O quiz dessa aula está junto com o da aula 20.
Referências: Capítulo 5 [S].

Aula 20 - 14/abr

Exemplos de redução para provar indecidibilidade e irreconhecibilidade.
Vídeos (43min):
Quiz.
Referências: Capítulo 5 [S].

Aula 21 - 19/abr

Teoria da complexidade: tempo de execução e notação assintótica.
Vídeos (tempo total = 68min):
Quiz.
Referências: Capítulo 7 [S].

21/abr (Feriado Tiradentes 🦷)

Reposição em 7/05.

Aula 22 - 27/abr (na terça-feira às 21h, por ser reposição)

Teoria da complexidade: classes P, NP, NP-completo. Problemas NP-completos.
Vídeos (tempo total = 53min):
Quiz.
Referências: Capítulo 7 [S].

Aula 23 - 29/abr 🎥🎥 LIVE (aula síncrona) 🎥🎥 (na quinta-feira às 19h, por ser reposição)

Checkpoint: revisão e dúvidas para prova.
Vídeo (tempo total = 123min):

💥💥PROVA 1 SUB💥💥 - 30/abr

Das 20h do dia 30/abr às 21h do dia 3/mai - Detalhes serão enviados por e-mail
Para os alunos que indicaram interesse em fazê-la via e-mail, quando houve o informe da reitoria sobre antecipação de feriados e proibição de atividades avaliativas entre 27/março a 4/abril.

Aula 24 - 💥💥PROVA 2💥💥 - 4/mai

Das 20h do dia 4/mai às 21h do dia 7/mai - Detalhes serão enviados por e-mail
Lembre-se de entregar as suas respostas das listas 3 e 4 até as 20h do dia 4/mai.

RECUPERAÇÃO - 26/mai (quadrimestre seguinte)

Das 18h do dia 26/mai às 20h do dia 29/mai - Detalhes serão enviados por e-mail

👎 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 estão disponibilizados abaixo.
Elas não valem nota, mas podem ser entregues até os dias das avaliações e serão consideradas como um bônus.
- As listas 1 e 2 podem ser entregues até o horário de liberação da prova 1. Elas valerão até 1 ponto extra na nota da prova 1.
- As listas 3 e 4 podem ser entregues até o horário de liberação da prova 2. Elas valerão até 1 ponto extra na nota da prova 2.
- Soluções entregues depois desses prazos não serão consideradas.
As soluções das listas deverão ser feitas à mão em papel ou algum dispositivo como um tablet ou mesa digitalizadora (capriche na letra!), escaneadas (caso feitas em papel) em um único arquivo PDF e entregues pelo Google Forms nos links disponibilizados abaixo.
- Se algo te impossibilita de fazer as listas à mão, converse comigo antes de enviar em outro formato, pois caso contrário sua nota naquela lista será zero.
- Sugestão de aplicativo para escanear a lista: CamScanner (disponível para Android e iPhone).
Certifique-se de que o resultado final está legível.
Não entregue sua primeira solução! Passe a limpo antes.
Procure atendimento sempre que tiver dúvidas nos exercícios.
- Nem todos são fáceis, mas eu não espero que você consiga fazer tudo sozinho.
- Também é recomendável que você me envie suas soluções antes, por mensagem privada no Discord, para que eu possa verificar como está a apresentação delas.
Faça o maior número de exercícios que puder, sempre.
- Os exercícios destacados abaixo, após cada lista, representam um mínimo de cobertura do conteúdo.
- O bônus que você receberá será diretamente proporcional à quantidade desses exercícios que forem entregues.
Finalmente:
- Lista 1 (linguagens regulares - Aulas 2 a 8)
  Exercícios em destaque: 2, 3, 7, 8, 12, 13 (apenas os relacionados ao 14), 14, 15, 16, 17, 18, 19, 20 (em exercícios com ℓ itens, escolha ⎣ℓ/2⎦ deles)
  Entrega: AQUI
- Lista 2 (linguagens livres de contexto - Aulas 9 a 12)
  Exercícios em destaque: 2, 3, 4, 6, 7, 8 (em exercícios com ℓ itens, escolha ⎣ℓ/2⎦ deles)
  Entrega: AQUI
- Lista 3 (máquinas de Turing - Aulas 15 a 18)
  Exercícios em destaque: 2, 3, 4, 6, 8 (em exercícios com ℓ itens, escolha ⎣ℓ/2⎦ deles)
  Entrega: AQUI
- Lista 4 (redutibilidade, complexidade e intratabilidade - Aulas 19 a 22)
  Exercícios em destaque: 1 a 4.
  Entrega: AQUI
Acompanhe aqui a entrega das listas.

🎓 Critérios de avaliação

A avaliação da disciplina constituirá da nota de duas provas, denotadas P₁ e P₂.

A prova 1 vale 50% da nota.
A prova 2 vale 50% da nota.

As provas serão enviadas por e-mail, juntamente com o link para entrega e instruções, no dia e horário especificados na seção Cronograma.
O conteúdo das provas englobará todos os temas vistos até a data das mesmas.
Ainda sobre avaliação, leia a seção sobre as listas de exercícios.

Sua média final (MF) antes da recuperação, portanto, será

MF = 0.5 × P₁ + 0.5 × P₂

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
O, se nenhuma prova for entregue

💯 Notas

Acompanhe aqui a entrega das atividades.
Acompanhe aqui as notas das atividades.
Essas planilhas são atualizadas automaticamente, então se detectar qualquer problema, me avise o quanto antes, por favor.

💪 Mecanismo de recuperação

A recuperação será aplicada apenas aos alunos que tiverem conceito final D ou F e que manifestarem interesse em realizá-la.
Pode ser cobrada a entrega de outros exercícios das listas.
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}
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

Uma prova substitutiva poderá ser aplicada ao aluno que possuir justificativa que o impeça de realizar alguma prova no período normal.
A data para realização da mesma 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