Teoria da computação

Universidade Federal Rural de Pernambuco 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

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.1 Conceitos Iniciais ..........................................................................7 1.2 Definição Formal.........................................................................13 Capítulo 2 – Autômatos Finitos Não-Determinísticos .....................23 2.1 Uma Visão Informal ....................................................................23 2.2 Definição Formal.........................................................................25 2.3 A função de transição estendida .................................................26 2.4 Relação entre AFD e AFND ........................................................29 2.5 Um novo tipo de transição (e) ....................................................34

Plano da Disciplina
Carga horária: 60h

Ementa da