MCTA015-13 - Linguagens Formais e Automata (2020 Q1) Primeiro Quadrimestre de 2020

Avisos importantes

🚨🔥 alerta: entrem no grupo do Discord 🔥🚨

Objetivos

  1. Apresentar os conceitos fundamentaisda 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.
  2. 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.

Ementa da disciplina

Linguagens regulares: autômatos determinísticose 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.

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

Recomendação

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

Para facilitar o acompanhamento do curso, é recomendado que você já 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 seguir argumentos lógicos em uma demonstração matemática

Materiais de apoio para esses tópicos:

Bibliografia

Livro texto

  1. SIPSER, M. Introduction to the Theory of Computation. 2nd edition. Boston, Massachusetts: Thomson, 2006.
    • Errata
    • Tradução: SIPSER, M. Introdução à teoria da computação. 2 ed. São Paulo, SP: Thomson Learning, 2007.

Livros auxiliares

  1. HOPCROFT, J. E.; ULLMAN, D. J.; MOTWANI, R. Introdução à teoria de autômatos, linguagens e computação. 2. ed. Rio de Janeiro, RJ: Campus, 2003.
  2. Vieira, N. J.. Introdução aos Fundamentos da Computação: Linguagens e Máquinas. 1a edição. Cengage Learning. 2006.

Plano de Aula

No plano de aula você encontrará informações sobre a dinâmica do curso, cronograma, critério de avaliação e recuperação e etc.

Dias, horários e locais das aulas

  • Os links para as videoaulas da semana serão disponibilidados nesta página as segundas-feiras.

Atendimento

Para nos comunicarmos de maneira mais eficiente, criei um servidor no aplicativo Discord. Ele será nosso canal primário de comunicação, então peço a todos que se cadastrem e acessem o servidor criado.

O Discord também será utilizado para a realização de atendimentos, de forma assíncrona e síncrona. O atendimento síncrono ocorrerá no seguinte horário:

  • Terças-feiras, das 19h às 21h, no Discord

Aulas

ECE - Apresentação

Sobre o curso e conhecimentos necessários

Alfabetos e linguagens, Autômatos finitos determinísticos e

Linguagens Regulares

:CUSTOMID: alfabetos-e-linguagens-autômatos-finitos-determinísticos-e-linguagens-regulares

Autômatos finitos não determinísticos

Gramática Livre de Contexto (GLC) - Parte 2

Máquinas de Turing (MT)

Decidibilidade

Decidibilidade (Cont.)

Listas de exercícios

Ao todo teremos 4 listas, que serão liberadas em pequenas partes. O objetivo principal é prover problemas representativos dos conceitos vistos, equivalentes aos que serão cobrados nas avaliações.

🚨 Instruções para elaboração e apresentação das listas de exercício

Link para entrega da lista 1 - partes 1-2-3: [entrega até as 23h59 de 05/06]

Notas

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. Sempre consulte o documento completo ou converse com o seu professor em caso de dúvidas!

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