دانلود کتاب A Concise Introduction to Languages and Machines

فهرست مطالب :

Undergraduate Topics in Computer Science
Contents
Preface
Introduction
1.2 What this Book is About
1.3 What this Book Tries to Do
1.4 What this Book Tries Not to Do
1.5 The Exercises
1.6 Further Reading
1.7 Some Advice
Elements of Formal Languages
2.1 Overview
2.2 Alphabets
2.3 Strings
2.3.1 Functions that Apply to Strings
2.3.2 Useful Notation for Describing Strings
2.4 Formal Languages
2.5 Methods for Defining Formal Languages
2.5.1 Set Definitions of Languages
2.5.2 Decision Programs for Languages
2.5.3 Rules for Generating Languages
2.6 Formal Grammars. 2.6.1 Grammars, Derivations and Languages2.6.2 The Relationship between Grammars and Languages
2.7 Phrase Structure Grammars and the Chomsky Hierarchy
2.7.1 Formal Definition of Phrase Structure Grammars
2.7.2 Derivations, Sentential Forms, Sentences and \'\'L(G)\'\'
2.7.3 The Chomsky Hierarchy
2.8 A Type 0 Grammar: Computation as Symbol Manipulation
Syntax, Semantics and Ambiguity
3.1 Overview
3.2 Syntax vs. Semantics
3.3 Derivation Trees
3.4 Parsing
3.5 Ambiguity
Regular Languages and Finite State Recognisers
4.1 Overview
4.2 Regular Grammars
4.3 Some Problems with Grammars. 4.4 Finite State Recognisers and Finite State Generators4.4.1 Creating an FSR
4.4.2 The Behaviour of the FSR
4.4.3 The FSR as Equivalent to the Regular Grammar
4.5 Non-determinism in Finite State Recognisers
4.5.1 Constructing Deterministic FSRs
4.5.2 The Deterministic FSR as Equivalent to the Non-deterministic FSR
4.6 A Simple Deterministic Decision Program
4.7 Minimal FSRs
4.7.1 Constructing a Minimal FSR
4.7.2 Why Minimisation Works
4.8 The General Equivalence of Regular Languages and FSRs
4.9 Observations on Regular Grammars and Languages. Context Free Languages and Pushdown Recognisers5.1 Overview
5.2 Context Free Grammars and Context Free Languages
5.3 Changing G without Changing L(G)
5.3.1 The Empty String (repsiv)
5.3.2 Chomsky Normal Form
5.4 Pushdown Recognisers
5.4.1 The Stack
5.4.2 Constructing a Non-deterministic PDR
5.4.3 Example NPDRs, M3 and M10
5.5 Deterministic Pushdown Recognisers
5.5.1 M3d, a Deterministic Version of M3
5.5.2 More Deterministic PDRs
5.6 Deterministic and Non-deterministic Context Free Languages
5.6.1 Every Regular Language is a Deterministic CFL
5.6.2 The Non-deterministic CFLs. 5.6.3 A Refinement to the Chomsky Hierarchy in the Case of CFLs5.7 The Equivalence of CFGs and PDRs
5.8 Observations on Context Free Grammars and Languages
Important Features of Regular and Context Free Languages
6.1 Overview
6.2 Closure Properties of Languages
6.3 Closure Properties of the Regular Languages
6.3.1 Complement
6.3.2 Union
6.3.3 Intersection
6.3.4 Concatenation
6.4 Closure Properties of the Context Free Languages
6.4.1 Union
6.4.2 Concatenation
6.4.3 Intersection
6.4.4 Complement
6.5 Chomsky\'s Hierarchy is Indeed a Proper Hierarchy.