2022 Q1

MCTA015-13 - Linguagens Formais e Automata

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

🚨 Avisos importantes (fique atento sempre!)

📌 [20/06] Avisos finais:

Corrigi a prova de recuperação. Se você a fez, enviei no Moodle sua prova com 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 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 25/06.

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

Corrigi a prova 2 e a lista 4. Alguns comentários foram enviados no Discord.
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.
A prova ficará disponível no Moodle na data e horário descritos no cronograma.
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.
Faça isso até o final desta semana.
Por fim, estarei disponível pelo Discord para tirar dúvidas sobre a recuperação a qualquer momento do recesso.

[05/05] Aumentei o prazo de entrega da lista 4. Por causa da prova, ainda é no dia 12.
[22/04] A lista 4 está disponível.
[18/04] Corrigi a prova 1. Se você a fez, veja os comentários no seu PDF, que estão disponíveis no Moodle. As notas e os critérios estão na planilha na seção de notas. Em caso de problemas ou dúvidas, mande mensagem privada no Discord!
[06/04] A lista 3 está disponível.
[28/03] Corrigi a lista 1 e enviei as anotações no Moodle. As notas estão na planilha na seção de notas. Veja o Discord se você não enviou a lista, também deixei informações lá.
[01/03] A lista 2 está disponível.
[17/02] Atenção! Você deve marcar horário de atendimento individual com pelo menos 4 (quatro) horas de antecedência! Organize-se para não perder as oportunidades.
[05/fev] Leia a seção sobre 🔥🔥🔥 COMO SERÁ A DISCIPLINA 🔥🔥🔥 sem falta e com atenção!
[05/fev] Apenas para matriculados: 🔥🔥🔥 servidor no Discord 🔥🔥🔥 e formulário de início de curso.
[05/fev] Site no ar. Estude-o como se o seu conteúdo fosse ser cobrado na prova.

🙋 Como será a disciplina?

Nosso meio de comunicação principal será pelo servidor na ferramenta Discord (baixe o aplicativo e crie uma conta).
Por favor, participe do grupo apenas se você está matriculado na disciplina.
O site sempre será atualizado com avisos, 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.
Eu certamente responderei dentro de 24h, exceto talvez pelos finais de semana.

Usaremos também o Moodle, mas apenas para entrega das atividades.

As videoaulas com os conteúdos da disciplina serão disponibilizadas apenas aqui no site, na seção Cronograma.
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.

Em vários dias, estarei online pela ferramenta Google Meet para atendimento:

nos primeiros 40 minutos comentarei o conteúdo da semana, resolverei algum exercício, darei dicas de exercícios e explicarei enunciados (o link fica disponível no Discord);
nas duas horas seguintes, farei atendimentos síncronos individuais: cada aluno terá até 10 minutos de atendimento, e a inscrição deve ser feita por um link específico (disponível no Discord).

A maioria desses encontros são às sextas-feiras, porém em abril teremos um em uma quarta-feira.
As datas exatas estão no cronograma.

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: veja o conteúdo no dia previsto e tire dúvidas naquela mesma semana.
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.

📆 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.
Você já tem acesso à playlist completa dos vídeos, porém tente seguir o cronograma: o conteúdo está bem distribuído.
O conteúdo de cada aula será atualizado durante o quadrimestre.

Acesse aqui um calendário resumido das atividades.

Aula 1 - 15/fev

Conteúdo: Sobre o curso.
Formato: aula síncrona (link no Discord).
Vídeo (tempo total = 84min):
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 - 18/fev

Conteúdo: Alfabetos e linguagens. Autômatos finitos determinísticos (AFDs). Linguagens regulares (LRs).
Formato: videoaulas (aula assíncrona); atendimento para todos das 10h às 10h40 (link no Discord); atendimento individual das 10h40 às 12h30 (inscrição pelo link disponível no Discord).
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 - 22/fev

Conteúdo: 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)
Formato: videoaulas (aula assíncrona)
Vídeos (tempo total = 82min):
Quiz.
Referências: Seção 1.1 [S] e Seção 2.2 [HUM].
Material complementar: JFLAP.

Aula 4 - 25/fev

Conteúdo: Autômatos finitos não determinísticos (AFNs). (fazer os exercícios da lista 1 após os vídeos)
Formato: videoaulas (aula assíncrona); atendimento para todos das 10h às 10h40 (link no Discord); atendimento individual das 10h40 às 12h30 (inscrição pelo link disponível no Discord).
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:

01/mar (Feriado Carnaval)

Reposição em 11/mai (quarta-feira).

Aula 5 - 04/mar

Conteúdo: AFDs vs AFNs. Simulando AFNs. Propriedades das LRs.
Formato: videoaulas (aula assíncrona); atendimento para todos das 10h às 10h40 (link no Discord); atendimento individual das 10h40 às 12h30 (inscrição pelo link disponível no Discord).
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 - 08/mar

Conteúdo: Expressões regulares. (ATENÇÃO! No presencial, essa aula exige sua participação, então faça os exercícios pedidos nos vídeos antes de ver as respostas)
Formato: videoaulas (aula assíncrona)
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 - 11/mar

Conteúdo: Expressões regulares vs. autômatos. Algoritmos de conversão.
Formato: videoaulas (aula assíncrona); atendimento para todos das 10h às 10h40 (link no Discord); atendimento individual das 10h40 às 12h30 (inscrição pelo link disponível no Discord).
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 - 15/mar

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

Aula 9 - 18/mar

Conteúdo: Gramáticas livres de contexto (GLC). Linguagens livres de contexto (LLCs).
Formato: videoaulas (aula assíncrona); atendimento para todos das 10h às 10h40 (link no Discord); atendimento individual das 10h40 às 12h30 (inscrição pelo link disponível no Discord).
Vídeos (tempo total = 87min):
Quiz.
Referências: Seção 2.1 [S] e Seções 5.1 e 5.2 [HUM].

21/mar: Data de entrega da Lista 1.

Aula 10 - 22/mar

Conteúdo: Mais exemplos com GLCs. Autômatos com pilha (APs).
Formato: videoaulas (aula assíncrona)
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 - 25/mar

Conteúdo: APs vs GLCs. Simulação de GLCs e APs. Propriedades das LLCs.
Formato: videoaulas (aula assíncrona); atendimento para todos das 10h às 10h40 (link no Discord); atendimento individual das 10h40 às 12h30 (inscrição pelo link disponível no Discord).
Vídeos (tempo total = 38min):
Quiz.
Referências: Seção 2.2 [S] e Seções 6.3 e 7.3 [HUM].

Aula 12 - 29/mar

Conteúdo: Lema do bombeamento para LLCs. Discussão final sobre LLCs.
Formato: videoaulas (aula assíncrona)
Vídeos (tempo total = 51min):

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

Aula 13 - 01/abr

Checkpoint: revisão e dúvidas para prova.
Formato: aula síncrona das 10h às 12h.
Vídeo (tempo total = 101min):

04/abr: Data de entrega da Lista 2.

Aula 14 - 05/abr

Prova 1
Das 08h do dia 04/abr às 10h do dia 07/abr
Detalhes no Moodle.

Aula 15 - 08/abr

Conteúdo: Máquinas de Turing (MTs).
Formato: videoaulas (aula assíncrona)
Vídeos: em breve
Vídeos (tempo total = 93min):
Quiz.
Referências: Seção 3.1 [S].

Aula 16 - 12/abr

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

15/abr (Feriado Sexta-Feira Santa)

Reposição em 16/mai (segunda-feira).

Aula 17 - 19/abr

Conteúdo: Decidibilidade. O problema da Parada.
Formato: videoaulas (aula assíncrona); atendimento para todos das 8h às 8h40 (link no Discord); atendimento individual das 8h40 às 10h30 (inscrição pelo link disponível no Discord).
Vídeos (tempo total = 40min):
Quiz.
Referências: Capítulo 4 [S].
Extras: A história da indecidibilidade (inglês).

Aula 18 - 22/abr

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

Aula 19 - 26/abr

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

Aula 20 - 29/abr

Conteúdo: Exemplos de redução para provar indecidibilidade e irreconhecibilidade.
Formato: videoaulas (aula assíncrona); atendimento para todos das 10h às 10h40 (link no Discord); atendimento individual das 10h40 às 12h30 (inscrição pelo link disponível no Discord).
Vídeos (43min):
Quiz.
Referências: Capítulo 5 [S].

02/mai: Data de entrega da Lista 3.

Aula 21 - 03/mai

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

Aula 22 - 06/mai

Conteúdo: Teoria da complexidade: classes P, NP, NP-completo. Problemas NP-completos.
Formato: videoaulas (aula assíncrona); atendimento para todos das 10h às 10h40 (link no Discord); atendimento individual das 10h40 às 12h30 (inscrição pelo link disponível no Discord).
Vídeos (tempo total = 53min):
Quiz.
Referências: Capítulo 7 [S].

Aula 23 - 11/mai (na quarta-feira às 8h, por ser reposição)

Checkpoint: revisão e dúvidas para prova.
Formato: aula síncrona - das 8h às 10h.

12/mai: Data de entrega da Lista 4.

Aula 24 - 13/mai

Prova 2
Das 10h do dia 13/mai às 12h do dia 16/mai
Detalhes no Moodle.

RECUPERAÇÃO - 10/jun (quadrimestre seguinte)

Prova de recuperação para os alunos que ficaram com conceito D ou F.
Das 8h do dia 10/jun às 10h do dia 13/jun
Detalhes no Moodle.

👎 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.
Usaremos o Moodle para a entrega de todas as atividades da disciplina.
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 Moodle.
- 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.
Faça o maior número de exercícios que puder, sempre.
- Os exercícios destacados abaixo, após cada lista, são os que serão corrigidos e valem nota.
Finalmente:
- Lista 1 - peso 5 (linguagens regulares - Aulas 2 a 8)
  Exercícios: 2 (letras c, d, e, f, g), 3, 7 (letras a, d, e, f, g), 8 (apenas N₅), 9, 17 (letras a, c, d), 18 (letras c, d, f) 19 (letra b), 20 (apenas N₇) e 21 (letras d, e).
  Entrega até 12h do dia 21 de março, pelo Moodle
- Lista 2 - peso 5 (linguagens livres de contexto - Aulas 9 a 12)
  Exercícios: 2, 4 (letras b, d, f), 5, 7 (letras b, e) e 8 (letra f).
  Entrega até 12h do dia 4 de abril, pelo Moodle
- Lista 3 - peso 5 (máquinas de Turing - Aulas 15 a 18)
  Exercícios: 2 (letras a, f), 3 (letra d), 4 (letra d), 6 e 7.
  Entrega até 12h do dia 2 de maio, pelo Moodle
- Lista 4 - peso 5 (redutibilidade, complexidade e intratabilidade - Aulas 19 a 22)
  Exercícios: 1, 2, 4.
  Entrega até ~~12h~~23h50 do dia 12 de maio, pelo Moodle

🎓 Critérios de avaliação

A avaliação da disciplina constituirá da nota de duas provas, denotadas P₁ e P₂, e da média ponderada das notas das listas, denotada L.

A prova 1 vale 40% da nota e 0 ≤ P₁ ≤ 10.
A prova 2 vale 40% da nota e 0 ≤ P₂ ≤ 10.
As listas valem 20% da nota e 0 ≤ L ≤ 10.

O conteúdo das provas englobará todos os temas vistos até a data das mesmas.
Os pesos de cada lista estão na seção sobre as listas de exercícios.

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

MF = 0.4 × P₁ + 0.4 × P₂ + 0.2 × L

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 atividade for entregue

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