Linguagens Formais e Autômatos

Universidade LaSalle Canoas - 2024/2

Objetivos

São objetivos da disciplina:

Pré-requisitos

Embora os pré-requisitos não sejam obrigatórios, o seu domínio auxiliará muito na evolução do aprendizado:

Competências trabalhadas

As competências trabalhadas na disciplina são:

Unidades de Aprendizagem

As unidades de aprendizagem abordadas na disciplina são:

Estratégias metodológicas

Aulas expositivas, atividades de pesquisa relacionadas às unidades de aprendizagem, exemplos práticos e exercícios individuais ou em grupo.

Cronograma

AulaConteúdo ProgramadoData
01
  • Apresentação da disciplina.
  • Lingagens e Problemas.
  • Aplicação prática da Teoria da Computação.
  • Avaliações e logística da disciplina.
  • Revisão de conceitos básicos.
07/03
02
  • Revisão de conceitos básicos.
  • Demonstrações e Provas.
14/03
03
  • Demonstrações e Provas.
21/03
04
  • Feriado.
28/03
05
  • Gramáticas, Linguagens e Autômatos.
04/04
06
  • Liguagens Regulares e Autômatos Finitos.
11/04
07
  • Conversão de automatos finitos não-determinísticos em automatos finitos determinísticos.
  • Expressões regulares.
  • Especificação dos trabalhos T1 e T2..
18/04
08
  • Fecho das linguagens regulares.
  • Lema do Bombeamento.
  • Gramáticas Livres de Contexto.
  • Automatos de Pilha.
25/04
09
  • Exercícios de revisão (online devido a eventos climáticos).
02/05
10
  • Propriedades das linguagens Livres de Contexto.
  • Autômatos de Pilha.
09/05
11
  • Prova G1 (P1).
16/05
12
  • Máquinas universais.
  • Decidibilidade.
23/05
13
  • Feriado.
30/05
14
  • Redutibilididade.
06/06
15
  • Problema da Correspondência de Post.
  • Teorema de Rice.
13/06
16
  • Cálculo Lambda.
  • Teorema da Recursão.
20/06
17
  • Exercícios de Revisão.
27/06
18
  • Prova G2 (P2).
04/07
19
  • Divulgação de resultados.
  • Complexidade computacional.
  • Criptografia.
  • Linguagens de programação e compiladores.
  • Solução de problemas como reconhecimento de linguagens.
11/07
20
  • Prova de substituição de grau.
18/07

Procedimento e critérios de avaliação

A nota final será composta por trabalhos/exercícios e prova, que serão desenvolvidos durante as aulas e em atividades extraclasse.

O grau 1 será composto por G1 = T1(1.0) + T2(2.0) + T3(2.0) + P1(5.0)

O grau 2 será composto por G2 = T4(1.0) + T5(2.0) + T6(2.0) + P2(5.0)

A nota final será a média (M) dada pela regra M = (G1 + G2) / 2

A recuperação será realizada com a aplicação de uma prova escrita. A nota desta substituirá a nota mais baixa e a média (M) será recalculada.

Para obter a aprovação, o aluno deve obter uma média (M) igual ou superior a 6, com frequência igual ou superior à 75%. A frequência será medida a partir de chamada nominal, realizada em todas as aulas.

Recursos para a disciplina

Bibliografia

  1. SIPSER, Michael. Introdução a Teoria da Computação. Cengage Learning. 2015
  2. Menezes, Paulo Blath. Linguagens Formais e Autômatos. 6a ed. Bookman, 2011.
  3. HOPCROFT, John E.; ULLMAN, Jeffrey D.; MOTWANI, Rajeev. Introdução à Teoria de Autômatos, Linguagens e Computação. Tradução da 2a Ed. Elsevier, 2002.
  4. LEHMAN, Eric; LEIGHTON, F. Thomson; MAYER, Albert R. Mathematics for Computer Science. MIT. 2015
  5. AHO & ULLMAN. Foundations of Computer Science - fora de catálogo.

Recursos online

  1. MIT 18.040j Theory of Computation - Michael Sipser
  2. MIT 6.042j Mathematics for Computer Science - Unit 1 - Proofs (2019)
  3. MIT 6.042j Mathematics for Computer Science - Inclui video aulas (2010)
  4. Stanford CS154 - Introduction to the Theory of Computation - Omer Reingold (2020)
  5. Simulador de DFA, NFA e PDA

Posts Relacionados