book

An Introduction to Formal Languages and Automata, 6th Edition

by Peter Linz

January 2016

Beginner to intermediate

450 pages

10h 11m

English

Jones & Bartlett Learning

Read now

Unlock full access

1.1 Mathematical Preliminaries and NotationSetsFunctions and RelationsGraphs and TreesProof Techniques1.2 Three Basic ConceptsLanguagesGrammarsAutomata1.3 Some Applications*
2.1 Deterministic Finite AcceptersLanguages and Dfa’sRegular Languages2.2 Nondeterministic Finite AcceptersDefinition of a Nondeterministic AccepterWhy Nondeterminism?2.3 Equivalence of Deterministic and Nondeterministic Finite Accepters2.4 Reduction of the Number of States in Finite Automata*
3.1 Regular ExpressionsFormal Definition of a Regular ExpressionLanguages Associated with Regular Expressions3.2 Connection Between Regular Expressions and Regular LanguagesRegular Expressions Denote Regular LanguagesRegular Expressions for Regular LanguagesRegular Expressions for Describing Simple Patterns3.3 Regular GrammarsRight- and Left-Linear GrammarsRight-Linear Grammars Generate Regular LanguagesRight-Linear Grammars for Regular LanguagesEquivalence of Regular Languages and Regular Grammars
4.1 Closure Properties of Regular LanguagesClosure under Simple Set OperationsClosure under Other Operations4.2 Elementary Questions about Regular Languages4.3 Identifying Nonregular LanguagesUsing the Pigeonhole PrincipleA Pumping Lemma
5.1 Context-Free GrammarsExamples of Context-Free LanguagesLeftmost and Rightmost DerivationsDerivation TreesRelation Between Sentential Forms and Derivation Trees5.2 Parsing and AmbiguityParsing and MembershipAmbiguity in Grammars and Languages5.3 Context-Free Grammars and Programming Languages

6.1 Methods for Transforming GrammarsA Useful Substitution RuleRemoving Useless ProductionsRemoving λ-ProductionsRemoving Unit-Productions6.2 Two Important Normal FormsChomsky Normal FormGreibach Normal Form6.3 A Membership Algorithm for Context-Free Grammars*
7.1 Nondeterministic Pushdown AutomataDefinition of a Pushdown AutomatonThe Language Accepted by a Pushdown Automaton7.2 Pushdown Automata and Context-Free LanguagesPushdown Automata for Context-Free LanguagesContext-Free Grammars for Pushdown Automata7.3 Deterministic Pushdown Automata and Deterministic Context-Free Languages7.4 Grammars for Deterministic Context-Free Languages*
8.1 Two Pumping LemmasA Pumping Lemma for Context-Free LanguagesA Pumping Lemma for Linear Languages8.2 Closure Properties and Decision Algorithms for Context-Free LanguagesClosure of Context-Free LanguagesSome Decidable Properties of Context-Free Languages
9.1 The Standard Turing MachineDefinition of a Turing MachineTuring Machines as Language AcceptersTuring Machines as Transducers9.2 Combining Turing Machines for Complicated Tasks9.3 Turing’s Thesis
10.1 Minor Variations on the Turing Machine ThemeEquivalence of Classes of AutomataTuring Machines with a Stay-OptionTuring Machines with Semi-Infinite TapeThe Off-Line Turing Machine10.2 Turing Machines with More Complex StorageMultitape Turing MachinesMultidimensional Turing Machines10.3 Nondeterministic Turing Machines10.4 A Universal Turing Machine10.5 Linear Bounded Automata
11.1 Recursive and Recursively Enumerable LanguagesLanguages That Are Not Recursively EnumerableA Language That Is Not Recursively EnumerableA Language That Is Recursively Enumerable but Not Recursive11.2 Unrestricted Grammars11.3 Context-Sensitive Grammars and LanguagesContext-Sensitive Languages and Linear Bounded AutomataRelation Between Recursive and Context-Sensitive Languages11.4 The Chomsky Hierarchy
12.1 Some Problems That Cannot Be Solved by Turing MachinesComputability and DecidabilityThe Turing Machine Halting ProblemReducing One Undecidable Problem to Another12.2 Undecidable Problems for Recursively Enumerable Languages12.3 The Post Correspondence Problem12.4 Undecidable Problems for Context-Free Languages12.5 A Question of Efficiency
13.1 Recursive FunctionsPrimitive Recursive FunctionsAckermann’s Functionμ Recursive Functions13.2 Post Systems13.3 Rewriting SystemsMatrix GrammarsMarkov AlgorithmsL-Systems
14.1 Efficiency of Computation14.2 Turing Machine Models and Complexity14.3 Language Families and Complexity Classes14.4 The Complexity Classes P and NP14.5 Some NP Problems14.6 Polynomial-Time Reduction14.7 NP-Completeness and an Open Question
A.1 A General FrameworkA.2 Mealy MachinesA.3 Moore MachinesA.4 Moore and Mealy Machine EquivalenceA.5 Mealy Machine MinimizationA.6 Moore Machine MinimizationA.7 Limitations of Finite-State Transducers