Referências - Livros

Referências: os dois livros da disciplina

Voltar ao mapa.

Como os livros foram usados

As notas foram complementadas a partir dos PDFs dos livros que estão na pasta Linguage. Os dois PDFs são digitalizações (imagens), então extraí o texto com reconhecimento óptico (OCR) e li os capítulos que correspondem aos slides. Nas notas, o conteúdo dos livros aparece resumido e explicado com minhas palavras, com a página de origem, e não copiado. Quando algo é conclusão minha e não do livro, está marcado como “minha resposta” ou “complemento”.

Alguns símbolos e figuras não saíram bem no OCR. Nesses pontos preferi não afirmar nada que eu não tenha conseguido conferir.

Menezes, Linguagens Formais e Autômatos

• Edição da sua pasta: Paulo Blauth Menezes, 3ª edição, Editora Sagra Luzzatto / Instituto de Informática da UFRGS, 2000 (Série Livros Didáticos, número 3). 178 páginas digitalizadas.
• Atenção: a capa que você mostrou é da 6ª edição (Bookman). O conteúdo dos capítulos 1 e 2 é o mesmo em linhas gerais, mas os números de página podem mudar. As páginas citadas nas notas são da 3ª edição.
• Relação com a disciplina: os slides do professor seguem de perto este livro. Vários exemplos e exercícios são os mesmos (a gramática de números naturais, o AFND de aa/bb, o exercício de aa/bb com sufixo cccc, o do “quinto símbolo da direita para a esquerda”).

Seção (3ª ed.)	Páginas	Nota do vault
1.1 Introdução	1 a 4	01 - Introdução e Conceitos Básicos
1.2 Conjuntos, Relações e Funções	5 a 13	02 - Matemática Discreta
1.3 Lógica	13 a 16	02 - Matemática Discreta
1.4 Técnicas de Demonstração	16 a 21	02 - Matemática Discreta
1.5 Alfabetos, Palavras, Linguagens e Gramáticas	21 a 26	01 - Introdução e Conceitos Básicos, 03 - Gramáticas Regulares
1.6 Exercícios	27 a 30	notas 01 a 03
2.1 Sistema de Estados Finitos	32	04 - Autômatos Finitos Determinísticos
2.2 Autômato Finito	33 a 38	04 - Autômatos Finitos Determinísticos
2.3 Autômato Finito Não-Determinístico	39 a 44	05 - Autômatos Finitos Não Determinísticos, 06 - Equivalência AFD e AFND
2.4 Autômato Finito com Movimentos Vazios	44 a 50	08 - Tópicos Complementares dos Livros
2.5 Expressão Regular	50 a 55	03b - Expressões Regulares
2.6 Gramática Regular	55 a 60	03 - Gramáticas Regulares, 07 - Equivalência AF e GR
2.7 Propriedades das Linguagens Regulares	60 a 66	08 - Tópicos Complementares dos Livros
2.8 Minimização	66 a 72	08 - Tópicos Complementares dos Livros
2.9 Autômato Finito com Saída (Mealy, Moore)	72 a 79	08 - Tópicos Complementares dos Livros
2.10 Exercícios	80 a 84	notas 03b a 08
5 Hierarquia de Classes de Linguagens	153 a 158	03 - Gramáticas Regulares

Capítulos 3 (livres de contexto) e 4 (Máquina de Turing, sensíveis ao contexto) ficam para as próximas aulas.

Ramos, José Neto e Vega, Linguagens Formais: Teoria, Modelagem e Implementação

• Marcus Vinícius Midena Ramos, João José Neto e Ítalo Santiago Vega. Bookman. 648 páginas digitalizadas no PDF.
• O autor mantém uma página do livro com sumário, prefácio, errata e slides por capítulo.
• Estilo: mais formal e detalhado que o Menezes, com muitos exemplos resolvidos, algoritmos passo a passo e seções de “Modelagem e Implementação” com código.

Seção	Páginas	Nota do vault
1.1 Conjuntos	31 a 35	02 - Matemática Discreta
1.2 Relações	35 a 38	02 - Matemática Discreta
1.3 Funções	38 a 42	02 - Matemática Discreta
1.6 Teoremas e Demonstrações	47 a 51	02 - Matemática Discreta
1.7 Conjuntos Enumeráveis	51 a 56	02 - Matemática Discreta
2.1 Símbolos e Cadeias	77 a 79	01 - Introdução e Conceitos Básicos
2.2 Linguagens	79 a 90	01 - Introdução e Conceitos Básicos
2.3 Gramáticas	90 a 94	03 - Gramáticas Regulares
2.4 Linguagens, Gramáticas e Conjuntos	94 a 96	03 - Gramáticas Regulares
2.5 Reconhecedores	96 a 105	01 - Introdução e Conceitos Básicos
2.6 Hierarquia de Chomsky	105 a 110	03 - Gramáticas Regulares
3.1 Gramáticas Regulares	141 a 145	03 - Gramáticas Regulares
3.2 Conjuntos e Expressões Regulares	145 a 150	03b - Expressões Regulares
3.3 Autômatos Finitos	150 a 192	04 - Autômatos Finitos Determinísticos, 05 - Autômatos Finitos Não Determinísticos, 06 - Equivalência AFD e AFND
3.4 Gramáticas Regulares e Conjuntos Regulares	192 a 202	07 - Equivalência AF e GR
3.5 Gramáticas Regulares e Autômatos Finitos	202 a 206	07 - Equivalência AF e GR
3.6 Conjuntos Regulares e Autômatos Finitos	206 a 216	03b - Expressões Regulares, 08 - Tópicos Complementares dos Livros
3.7 Minimização	216 a 230	08 - Tópicos Complementares dos Livros
3.8 Transdutores Finitos	230 a 233	08 - Tópicos Complementares dos Livros
3.9 Linguagens que não são Regulares	233 a 239	08 - Tópicos Complementares dos Livros

Qual livro usar para quê

Objetivo	Melhor escolha
Acompanhar os slides	Menezes: os slides seguem a mesma ordem e os mesmos exemplos
Entender uma definição com rigor	Ramos: define tudo com cuidado e discute as variações de notação
Ver algoritmos passo a passo (conversões, minimização)	Ramos
Treinar com exercícios	os dois: Menezes no fim de cada capítulo (sem respostas); Ramos com muitos exemplos resolvidos no meio do texto
Ligar a teoria à programação	Ramos, seções “Modelagem e Implementação”

Principais diferenças de notação entre slides e livros

Conceito	Slides	Menezes	Ramos
Alfabeto	$V$	$\Sigma$	$\Sigma$
Autômato	$(K,V,T,i,F)$	$(\Sigma ,Q,\delta ,q_0,F)$	$(Q,\Sigma ,\delta ,q_0,F)$
Gramática	$(V_n,V_t,S,P)$	$(V,T,P,S)$, $V$ = variáveis	$(V,\Sigma ,P,S)$, $V$ = vocabulário todo
União em ER	$\mid$	$+$	$\mid$ ou $+$
Composição $R\circ S$	primeiro $R$	$g\circ f$ = primeiro $f$

Detalhes e exemplos de cada diferença estão nas seções “Aprofundamento com os livros” de cada nota.