SIN 131 - Introdução à Teoria da Computação

(2021-1 - PER 3)

Prof. João Fernando Mari

Universidade Federal de Viçosa - Campus Rio Paranaíba

SUMÁRIO:

Aula 01 - Introdução a Teoria da Computação - Conceitos Básicos

Aula 02 - Linguagens e Gramáticas

Aula 03 - Linguagens Regulares - Autômato Finito Deterministico

Aula 04 - LR - Autômato Finito Não Deterministico

Aula 05 - LR - Autômato Finito com Movimentos Vazios

Aula 06 - LR - Expressão Regular

Aula 07 - LR - Gramática Regular

Aula 08 - Propriedades das LR - Bombeamento Para LR

Aula 09 - Propriedades das LR - Minimização de AFD

Aula 10 - Autômatos Finitos com Saída (*)

* Este conteúdo não foi apresentado no PER. Os slides foram adaptados do semestre 2018-1.

Aula 11 - Linguagem Livre De Contexto - Gramática Livre De Contexto

Aula 12 - LLC - Simplificaçã de GLC

Aula 13 - LLC - Forma Normal de Chomsky

Aula 14 - LLC - Forma Normal de Greibach

Aula 15 - LLC - Autômato com Pilha

Aula 16 - Propriedade e Reconhecimento das LLCs

Aula 17 - Reconhecimento das LLC - Algoritmo de Early

Aula 18 - Máquina de Turing

Aula 19 - Máquina de Turing - Modelos Equivalentes

Aula 20 - Linguagem Sensível ao Contexto

Aula 21 - Máquina de Turing - Computabilidade

Bibliografia

  • MENEZES, P. B. Linguagens formais e autômatos, 6. ed., Bookman, 2011.

  • HOPCROFT J. E.; MOTWANI, R. ; ULLMAN, J. D. Introdução a teoria dos autômatos, linguagens e computação, 1. Ed., Campus, 2002

  • SIPSER, M. Introdução a Teoria da Computação, 1. Ed., Thomson Pioneira, 2007

  • AHO, A. V.; LAM, M. S.; SETHI, R.; ULLMAN, J. D. Compiladores: princípios, técnicas e ferramentas, 2ª edição. Editora Pearson, 2007.

    • Bibliografia complementar

  • VIEIRA, J. N. Introdução aos Fundamentos da Computação. Pioneira Thomson Learning, 2006.

  • LEWIS, H. R.; PAPADIMITRIOU, C. H. Elementos de Teoria da Computação, 2. Ed., Bookman, 2000.

  • DIVERIO, T. A.; MENEZES, P. B. Teoria da Computação: máquinas universais e computabilidade, 2. Ed., Bookman, 2008.

  • HOPCROFT J. E.; MOTWANI, R.; ULLMAN, J. D. Introduction to automata theory, languages, and computation. 3. Ed., Addison-Wesley, 2006.

  • SIPSER, M. Introduction to the Theory of Computation. 2. Ed., PWS Publishing Compan, 2005.

  • Susan H. Rodger and Thomas W. Finley. JFLAP: An Interactive Formal Languages and Automata Package. 2006(c) Jones & Bartlett Publishers, Sudbury, MA. ISBN 0763738344.

    • Ferramentas computacionais

  • JFLAP
    • HOME
    Última atualização: 2022/05/06