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:

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

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:

Aulas

ECE - Apresentação

Sobre o curso e conhecimentos necessários

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

Autômatos finitos não determinísticos

Função de transição estendida e Propriedade das linguagens regulares

Expressões regulares

Lema do Bombeamento

Gramática Livre de Contexto (GLC)

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

Autômato com Pilha (AP)

Lema do Bombeamento para LLC

Máquinas de Turing (MT)

Máquina de Turing (MT) (Cont) 🆕

Decidibilidade

Decidibilidade (Cont.)

Redutibilidade (Cont.)

Tratabilidade

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]

Provas

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!