• Document: Autômatos, Linguagens Formais e Computabilidade. S. C. Coutinho & Luis Menasché Schechter
  • Size: 1.33 MB
  • Uploaded: 2019-07-16 16:05:05
  • Status: Successfully converted


Some snippets from your converted document:

Autômatos, Linguagens Formais e Computabilidade S. C. Coutinho & Luis Menasché Schechter Versão 0.9 Universidade Federal do Rio de Janeiro c by S. C. Coutinho & Luis Menasché Schechter, 2016 Agradecimentos Agradecemos ao professor João Carlos Pereira da Silva e aos ex-alunos abaixo pelas sugestões, revisões e correções a esta apostila. • André Reis de Brito • Carlos Eduardo da Silva Martins • Christian da Silva Cabral Cardozo • Daniel Artine • Daniel Atkinson Oliveira • David Boechat • Fabiano de Paula Martins • Gabriel de Sá Rodrigues • Gabriel Pires da Silva • Gabriel Rosário • Giancarllo Alves Rojas • Hugo Siqueira Gomes • Igor Carpanese Figueiredo • Igor da Fonseca Ramos • Ingrid Pacheco • Lenise Maria de Vasconcelos Rodrigues • Luiz Guilherme Ribeiro • Pedro Carvalho da Silva • Rodrigo Ming Zhou • Ygor Luis Mesquita Pereira da Hora • Yuri de Jesus Lopes Abreu iii Sumário Agradecimentos iii Capítulo 0. Introdução 1 1. Tópicos Centrais de Estudo 1 2. Conceitos Básicos 2 3. Operações sobre Linguagens 3 4. Exercícios 5 Parte 1. Linguagens Regulares 9 Capítulo 1. Linguagens Regulares e Autômatos Finitos Determinísticos 11 1. Autômatos Finitos Determinísticos (AFD’s) 11 2. Exercícios 15 Capítulo 2. Expressões Regulares 19 1. Breve Motivação 19 2. Expressões Regulares 20 3. Exercícios 25 Capítulo 3. Relação entre AFD’s e Expressões Regulares 27 1. Introdução 27 2. Lema de Arden 31 3. O Algoritmo de Substituição 34 4. Análise Formal do Algoritmo de Substituição 37 5. Último Exemplo 40 6. Exercícios 41 Capítulo 4. Autômatos Finitos Não-Determinísticos 45 v vi SUMÁRIO 1. Autômatos Finitos Não-Determinísticos (AFND’s) 45 2. Algoritmo de Construção de Subconjuntos 52 3. Exercícios 59 Capítulo 5. Operações com Autômatos Finitos e Linguagens Regulares 61 1. Considerações Gerais 61 2. União 62 3. Concatenação 65 4. Estrela 67 5. Exemplo Mais Extenso 71 6. Propriedades de Fechamento das Linguagens Regulares 72 7. Exercícios 75 Capítulo 6. Lema do Bombeamento para Linguagens Regulares 79 1. Propriedade do Bombeamento 79 2. Lema do Bombeamento 82 3. Aplicações do Lema do Bombeamento 86 4. Exercícios 95 Capítulo 7. Gramáticas Regulares 99 1. Gramáticas 99 2. Gramáticas Regulares 101 3. Gramáticas Regulares e Autômatos Finitos 103 4. Exercícios 106 Parte 2. Linguagens Livres de Contexto 109 Capítulo 8. Linguagens Livres de Contexto e Gramáticas Livres de Contexto111 1. Gramáticas e Linguagens Livres de Contexto 111 2. Gramáticas que Não São Livres de Contexto 116 3. Mais Exemplos

Recently converted files (publicly available):