A Introdução a Teoria da Computação

[pic 1]

[pic 2][pic 3]

Universidade Federal Rural de Pernambuco[pic 4]

Reitor: Prof. Valmar Corrêa de Andrade Vice-Reitor: Prof. Reginaldo Barros

Pró-Reitor de Administração: Prof. Francisco Fernando Ramos Carvalho Pró-Reitor de Extensão: Prof. Paulo Donizeti Siepierski

Pró-Reitor de Pesquisa e Pós-Graduação: Prof. Fernando José Freire Pró-Reitor de Planejamento: Prof. Rinaldo Luiz Caraciolo Ferreira

Pró-Reitora de Ensino de Graduação: Profª. Maria José de Sena Coordenação de Ensino a Distância: Profª Marizete Silva Santos

Produção Gráfica e Editorial

Capa e Editoração: Alesanco Andrade Azevedo, Allyson Vila Nova, Italo Amorim e Rafael Lira

Revisão Ortográfica: Ivanda Martins

Ilustrações: Allyson Vila Nova

Coordenação de Produção: Marizete Silva Santos

[pic 5][pic 6]

Sumário

Plano da Disciplina        4

Ementa da Disciplina        4

Objetivos        4

Cronograma de Atividades        5

Capítulo 1 – Autômatos Finitos Determinísticos        7

1. Conceitos Iniciais        7
2. Definição Formal        13

Capítulo 2 – Autômatos Finitos Não-Determinísticos        23

1. Uma Visão Informal        23
2. Definição Formal        25
3. A função de transição estendida        26
4. Relação entre AFD e AFND        29
5. Um novo tipo de transição (ε)        34

[pic 7][pic 8]

Plano da Disciplina

Carga horária: 60h

Ementa da Disciplina

• Autômatos: Finitos, a Pilha e Máquina de Turing (linearmente limitada). Linguagens Formais: Regular, Livre e Sensível ao Contexto, Estrutura de Frases. Hierarquia de Chomsky. Aplicações em compiladores. Computabilidade: modelos computacionais (funções recursivas, linguagens de programação), funções não computáveis, problema da parada, decidibilidade.

Objetivos

Gerais

• Tem como objetivo dar aos cursistas noção formal de algoritmo, computabilidade e do problema de decisão, de modo a deixá-lo consciente das limitações da Ciência da Computação. Aparelhá-los com as ferramentas de modo a habilitá-lo a melhor enfrentar a solução de problemas com o auxílio do computador. Dar subsídios para os cursistas poderem definir linguagens de programação, isto é, sua sintaxe e semântica, através do estudo das gramáticas formais.

Específicos

• Habilitar o cursista aos conhecimentos básicos de autômatos e máquina de Turing, além de um estudo geral sobre a hierarquia dos principais modelos computacionais existentes.

[pic 9][pic 10]

Cronograma de Atividades

1º Módulo Fascículo I Autômatos I	Aula 1 Motivação ao estudo da disciplina Conceitos centrais da teoria de autômatos Introdução ao estudo de autômatos Autômatos finitos determinísticos (AFD) Atividade virtual: entrega da 1ª lista de exercícios
2º Módulo Fascículo I Autômatos II	Aula 2 Autômatos finitos não determinísticos (AFND) Autômatos finitos com epsílon-transições Aula 3 Equivalência entre AFD e AFND Atividade virtual: entrega da 2ª lista de exercícios
3º Módulo Fascículo II Expressões Regulares	Aula 4 Expressões regulares Aula 5 Autômatos finitos e expressões regulares Leis algébricas para expressões regulares Avaliação presencial: Prova escrita
4º Módulo Fascículo II Linguagens Regulares	Aula 6 Propriedades das linguagens regulares Lema do bombeamento Homomorfismo Aula 7 Equivalência e minimização de autômatos Atividade virtual: entrega da 3ª lista de exercícios

5

[pic 11][pic 12]

5º Módulo Fascículo III Gramáticas e Autômatos a Pilha	Aula 8 Gramáticas livres de contexto Ambigüidade em gramáticas e linguagens Aula 9 Autômatos à Pilha Atividade virtual: entrega da 4ª lista de exercícios
6º Módulo Fascículo III Máquina de Turing	Aula 10 Breve histórico sobre teoria da computação A Máquina de Turing Aula 11 Indecidibilidade Problema da Parada Problemas indecidíveis Atividade presencial 2ª VA: Prova Escrita Atividade presencial 3ª VA: Prova Escrita Atividade presencial Final: Prova Escrita