Linguagens Formais e Automata (MCTA015-13) -- 2019-Q1

Primeiro quadrimestre de 2019

Turmas: A1 e A2 diurno, Santo André

Período letivo: 11/02/2019 a 13/05/2019

Horários e salas: segundas 8:00 - 10:00, quintas 10:00 - 12:00, sala S-301-1.

Atendimento: segunda 14:00 a 16:00, na sala 805 do bloco B.

Professor: Jerônimo C. Pellegrini

Sala do professor: S 805 (bloco B)

Email do professor: jeronimo.pellegrini ufabc edu br

Novidades

13/05 -- Conceitos após exame disponíveis
06/05 -- Listas contabilizadas
05/05 -- Conceitos da P3 disponíveis
03/05 -- Data da vista e revisão: 06/05, 10:00
30/04 -- Conceitos da P2 disponíveis
03/04 -- P2 adiada para 18/04
28/03 -- Conceitos da P1 disponíveis
01/03 -- Matéria da P1 descrita
18/02 -- SOMENTE NESTA SEMANA, horário de atendimento será sexta 14-60
14/02 -- Nova vresão das notas de aula disponíveis, com *muitas* melhorias.
         (nem sempre avisarei sobre novas versões -- verifiquem periodicamente)
11/02 -- Primeiro rascunho de notas de aula disponível
11/02 -- Início das aluas

Ementa

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

Objetivo

A disciplina tem grande importância e seus objetivos existem em várias dimensões.

Em uma dimensão prática, linguagens formais são usadas na descrição de linguagens de programação, e portanto o conhecimento delas é essencial ao trabalho em Compiladores, Interpretadores e outros programas similares; usam-se autômatos em descrições formais dos mais variados tipos -- de dispositivos eletrônicos a protocolos abstratos; autômatos são objetos fundamentais em verificação de modelos, e descrevem convenientemente cadeias de Markov, usadas para modelar uma vasta quantidade de processos probabilísticos.

A disciplina também aborda os fundamentos teóricos da Computação, uma vez que identifica o modelo abstrato que descreve tudo o que pode ser efetivamente realizado por computadores; permite compreender estruturas descrevendo-as como linguagens, sendo por isso de grande valor.

Há também outro aspecto da disciplina que não pode ser ignorado: o treinamento em abstração e raciocínio rigoroso, trabalhado também nas disciplinas de Matemática Discreta e Teoria dos Grafos.
A habilidade de implementar algoritmos já definidos tem característica operacional, trabalha o concreto. Já a habilidade de modelar e demonstrar fatos relaciona-se com o abstrato, e permite reusar soluções de problemas e encontrar outras, mais simples do que as já conhecidas.

Além disso, para qualquer assunto pode haver aplicações inusitadas. Vejam, por exemplo, o programa Context Free Art, que constrói imagens a partir de gramáticas livres de contexto.

Os objetivos específicos são dados a seguir.

  • Construir autômatos, gramáticas e expressões regulares para linguagens
  • Provar que linguagens são, ou que não são, regulares, livres de contexto e recursivamente enumeráveis
  • Demonstrar propriedades simples de linguagens
  • Compreender conceitos básicos relacionados a computabilidade

Requisitos

Oficialmente a Universidade recomenda Programação Estruturada, mas deve-se dar atenção também à posição da disciplina na grade curricular do Bacharelado em Computação -- NÃO se trata de disciplina introdutória!

Avaliação

O conceito final da disciplina poderá ser:

  • F - Reprovado. O aluno deve cursar novamente a disciplina.
  • C - Desempenho mínimo satisfatório, demonstrando capacidade de uso adequado dos conceitos da disciplina, habilidade para enfrentar problemas relativamente simples e prosseguir em estudos avançados.
  • B - Bom desempenho, demonstrando boa capacidade de uso dos conceitos da disciplina.
  • A - Desempenho excepcional, demonstrando excelente compreensão da disciplina e do uso da matéria.

Faremos três avaliações escritas com duas horas de duração: P1, P2 e P3. Cada avaliação vale exatamente 0, 1, 2 ou 3. A nota final é a soma das notas das provas, com mais um ponto para quem fizer as listas de exercícios (direi mais sobre isto depois).

AS AVALIAÇÕES SERÃO REALIZADAS SEM CONSULTA A QUALQUER MATERIAL!

COLA/PLÁGIO RESULTAM EM F NA DISCIPLINA

As notas serão convertidas em conceito de acordo com a seguinte regra: seja n a soma das notas das provas e do ponto de exercícios. Então o conceito final será:

  • n ∈ [0, 5)→F
  • n ∈ [5, 7)→C
  • n ∈ [7, 9)→B
  • n ∈ [9, 10]→A

Datas das avaliações

  • P1: 14/03 21/03
  • P2: 11/04 18/04
  • P3: 02/05
  • Subtitutiva: 06/05
  • Exame: 09/05

EXAME:

Calcule (n + E)/2 e aplique a tabela novamente.

Exercícios

São os das notas de aula. Podem começar os dos Capítulos 1 e 2.

Matéria das provas

  • P1: tudo que está nas notas de aula, até autômatos com pilha não-determinísticos (os determinísticos não entram)

Conceitos

Estão aqui!

Programa

Este programa está sujeito a mudanças simples. Grandes mudanças não devem acontecer.

Tentaremos seguir de perto a abordagem no livro do Michael Sipser, mas em alguns momentos teremos que recorrer a outras referências.

No programa a seguir há indicação de trechos de livros indicados para cada tópico.

I - LINGUAGENS REGULARES

  1. Expressões regulares :: Sipser 1.3 | Hopcroft 3
  2. Autômatos finitos :: Sipser 1.1 | Hopcroft 2.1, 2.2
  3. Autômatos finitos não-determinísticos :: Sipser 1.2 | Hopcroft 2.3, 2.5
  4. Gramáticas regulares :: notas de aula
  5. Propriedades de linguagens regulares :: Hopcroft 4.2, 4.3
  6. Lema do bombeamento :: Sipser 1.4 | Hopcroft 4.1

II - LINGUAGENS LIVRES DE CONTEXTO

  1. Gramáticas livres de contexto :: Sipser 2.1 | Hopcroft 5.1
  2. Ambiguidade :: Sipser 2.1 | Hopcroft 5.2, 5.4
  3. Autômatos com pilha :: Sipser 2.2 | Hopcroft 6
  4. Propriedades de linguagens livres de contexto :: Hopcroft 7.3-7.4
  5. Lema do bombeamento :: Sipser 2.3 | Hopcroft 7.2

III - LINGUAGENS RECURSIVAMENTE ENUMERÁVEIS

  1. Máquinas de Turing :: Sipser 3.1 | Hopcroft 8
  2. Agoritmos, linguagens recursivas e recursivamente enumeráveis :: Sipser 3 | Hopcroft 8
  3. Modelos de computação: funções recursivas e λ-Cálculo :: Jung | Rojas
  4. Decidibilidade e problema da parada :: Sipser 4 | Hopcroft 9
  5. Reduções e indecidibilidade :: Sipser 5

IV - CLASSES DE COMPLEXIDADE

  1. Noções de complexidade computacional. Classes P e NP :: Notas de Criptografia, Apêndice C: [ C.1 antes de C.1.1 ]; C.4; [ C.6 excetp classes BPP e PSPACE]; [ C.7 até antes de C.7.1 ] | Papadimitriou-Steiglitz 8.1-8.5, 15

Bibliografia

Principal

  • Notas de aula
  • SIPSER, M. "Introdução à Teoria da Computação." Thomson, 2007. 59 exemplares em SA, 30 em SBC [ 511.3 SIPi2 ]
  • J.E. HOPCROFT, R. MOTWANI, J.D. ULLMAN. "Introdução à teoria de autômatos, linguagens e computação". Campus, 2003. 7 exemplares em SA, 1 em SBC [ 511.3 HOPi2 ]
  • H. R. LEWIS, C. H. PAPADIMITRIOU. "Elementos de Teoria da Computação" (2ª ed.) Bookman, reimpressão de 2008 13 exemplares em SA, alguns em SBC [ 511.3 LEWe2 ]
  • S. DASGUPTA; C. PAPADIMITRIOU; U. V. VAZIRANI "Algoritmos" McGraw-Hill, 2009. 25 exemplares em SA, 1 em SBC [ 518.1 DASa ]
  • A. JUNG "A Short Introduction to the λ-Calculus"
  • R. ROJAS "A Tutorial Introduction to the λ-Calculus"
  • Notas de Álgebra Linear (o Apêndice sobre indução pode ajudar a entender as demonstrações em autômatos)
  • Notas de matemática discreta (leia o Capítulo dois; se precisar, o Capítulo um também pode ser útil)
  • Notas de Criptografia.

Secundária

  • YAN, S. Y. "An Introduction to Formal Languages and Machine Computation", World Scientific Publishing Company, 1998. [ 004.0151 YANin ]
  • RICH, E. A. "Automata, Computability and Complexity: Theory and Applications", Prentice Hall; 1st edition, 2007. [ 511.3 RICHau ]
  • ANDERSON, J. "Automata Theory with Modern Applications", Cambridge University Press, 2006. [ 511.3 ANDEau ]
  • SHALLIT, J. "A Second Course in Formal Languages and Automata Theory", Cambridge University Press, 1st edition, 2008. [ 005.131 SHAs ]
  • SALOMAA, Arto. "Computation and automata". Cambridge University Press, 1985. (Encyclopedia of mathematics and its applications, v. 25). [ 511.3 SALc ]
  • XAVIER, Eugene. "Theory of automata, formal languages and computation". New age, 2004. [ 511.3 XAVIth ]
  • C. H. PAPADIMITRIOU, K. STEIGLITZ. "Combinatorial Optimization: algorithms and complexity". Dover, 1998. 3 exemplares em SA [ 519 PAPAco ]
  • D. BRIDGES "Computability : a mathematical sketchbook". Springer, 1994 [ 511.3 BRIc ]
  • Notas de Semântica de Linguagens de Programação, Cap. 8 (sobre λ-Cálculo)