2016.1 Teoria da Computação

EMENTA

Conceitos Preliminares. Teoria de Linguagens Formais: gramáticas, linguagens e autômatos finitos. Hierarquia de Chomsky. Máquinas de Turing. Decidibilidade.

BIBLIOGRAFIA

• Básica

- MENEZES, P. F. B. Linguagens Formais e Autômatos. Porto Alegre: Sagra Luzzatto, 2004.

- VIEIRA, N. J. Introdução aos Fundamentos da Computação: linguagens e máquinas. São Paulo: Pioneira Thomson Learning, 2006.

• Complementar

- HOPCROFT, John E; ULLMAN, Jeffrey D. Formal Languages and their Relation to Automata. California: Addison Wesley, 1969.

- AHO, Alfred V.; ULLMAN, Jeffrey D.; SETHI, R. Compiladores: princípios, técnicas e ferramentas. Rio de Janeiro: LTC, 1995.

AULAS (acesse)

• 00TC - Apresentação da Disciplina

• 01TC - Fundamentos da Teoria da Computação

• 02TC - Conceitos Básicos - alfabeto, palavra, linguagem, gramática

• 03TC - Linguagens Regulares - AFD e AFND

• 04TC - Linguagens Regulares - expressão e gramática regular

• 05TC - Linguagens Regulares - minimização de autômatos

MATERIAL COMPLEMENTAR (acesse)

• Cap. 0 e 1 - Apostila (para o dia 13/04)

• Cap. 2 - Apostila (para o dia 20/04)

• Cap. 4 - Apostila (tópico 4.5 - Minimização de Autômatos)

• Questões_Soluções

SIMULADOR - AUTÔMATOS (acesse)

ATIVIDADES (acesse)

1ª Nota

- 01 Atividade - Conjuntos, Relações e Funções (sala de aula: 13/04)

- 02 Atividade - Conceitos Básicos (sala de aula: 20/04)

- 03 Atividade - Linguagens Regulares - AFD e AFND (sala de aula: 04/05)

3ª Nota

- Seminário - Tópicos Avançados (sala de aula: 22/06) (Vale 10.0 pontos)

* Autômato Finito com Saída (Máquina de Mealy, e Máquina de Moore)

* Árvore de derivação

* Forma Normal de Chomsky (FNC)

* Forma Normal de Greibach (FNG)

* Autômato com Pilha

* Algoritmo de Cocke-Younger-Kasami

* Algoritmo de Early

ATIVIDADES AVALIATIVAS (Notas)

• 1ª Nota - 1ª Avaliação (data: 18/05)

• 2ª Nota - 2ª Avaliação (data: 23/06) (Vale 10.0 pontos)

• REPOSIÇÃO/EXAME FINAL: (data: 06/07) (TODO CONTEÚDO DA DISCIPLINA)

  • Obs: Reposição (alunos que faltaram alguma avaliação); Exame Final (alunos que não atingiram a média 7.0)

APRESENTAÇÃO DO PROFESSOR (acesse)