An Introduction to Formal Languages and Automata

by Linz, Peter

• ISBN13: 9780763714222
• ISBN10: 0763714224
• Edition: 3rd
• Format: Hardcover
• Copyright: 2000-10-01
• Publisher: Jones & Bartlett

Summary

The prospective audience for this book consists primarily of sophomores and juniors majoring in computer science or computer engineering.-Theory of Computation-CS355 Automata and Computability Theory-CSC 520 Theory of Computation-C341 Survey of Theory-Automata Theory-Formal Languages and Automata Theory-Foundations of Computing-Concepts of Formal Languages and Algorithms

Table of Contents

Introduction to the Theory of Computation	1	(35)
Mathematical Preliminaries and Notation	3	(12)
Sets	3	(2)
Functions and Relations	5	(2)
Graphs and Trees	7	(2)
Proof Techniques	9	(6)
Three Basic Concepts	15	(14)
Languages	15	(4)
Grammars	19	(6)
Automata	25	(4)
Some Applications	29	(6)
Finite Automata	35	(36)
Deterministic Finite Accepters	36	(11)
Deterministic Accepters and Transition Graphs	36	(2)
Languages and Dfas	38	(4)
Regular Languages	42	(5)
Nondeterministic Finite Accepters	47	(8)
Definition of a Nondeterministic Accepter	48	(4)
Why Nondeterminism?	52	(3)
Equivalence of Deterministic and Nondeterministic Finite Accepters	55	(7)
Reduction of the Number of States in Finite Automata	62	(9)
Regular Languages and Regular Grammars	71	(28)
Regular Expressions	71	(7)
Formal Definition of a Regular Expression	72	(1)
Languages Associated with Regular Expressions	73	(5)
Connection Between Regular Expressions and Regular Languages	78	(11)
Regular Expressions Denote Regular Languages	78	(3)
Regular Expressions for Regular Languages	81	(4)
Regular Expressions for Describing Simple Patterns	85	(4)
Regular Grammars	89	(10)
Right- and Left-Linear Grammars	89	(2)
Right-Linear Grammars Generate Regular Languages	91	(2)
Right-Linear Grammars for Regular Languages	93	(2)
Equivalence Between Regular Languages and Regular Grammars	95	(4)
Properties of Regular Languages	99	(26)
Closure Properties of Regular Languages	100	(11)
Closure under Simple Set Operations	100	(3)
Closure under Other Operations	103	(8)
Elementary Questions about Regular Languages	111	(3)
Identifying Nonregular Languages	114	(11)
Using the Pigeonhole Principle	114	(1)
A Pumping Lemma	115	(10)
Context-Free Languages	125	(24)
Context-Free Grammars	126	(10)
Examples of Context-Free Languages	127	(2)
Leftmost and Rightmost Derivations	129	(1)
Derivation Trees	130	(2)
Relation Between Sentential Forms and Derivation Trees	132	(4)
Parsing and Ambiguity	136	(10)
Parsing and Membership	136	(5)
Ambiguity in Grammars and Languages	141	(5)
Context-Free Grammars and Programming Languages	146	(3)
Simplification of Context-Free Grammars	149	(26)
Methods for Transforming Grammars	150	(15)
A Useful Substitution Rule	150	(2)
Removing Useless Productions	152	(4)
Removing λ-Productions	156	(2)
Removing Unit-Productions	158	(7)
Two Important Normal Forms	165	(7)
Chomsky Normal Form	165	(3)
Greibach Normal Form	168	(4)
A Membership Algorithm for Context-Free Grammars	172	(3)
Pushdown Automata	175	(30)
Nondeterministic Pushdown Automata	176	(8)
Definition of a Pushdown Automaton	176	(3)
A Language Accepted by a Pushdown Automaton	179	(5)
Pushdown Automata and Context-Free Languages	184	(11)
Pushdown Automata for Context-Free Languages	184	(5)
Context-Free Grammars for Pushdown Automata	189	(6)
Deterministic Pushdown Automata and Deterministic Context-Free Languages	195	(5)
Grammars for Deterministic Context-Free Languages	200	(5)
Properties of Context-Free Languages	205	(16)
Two Pumping Lemmas	206	(7)
A Pumping Lemma for Context-Free Languages	206	(4)
A Pumping Lemma for Linear Languages	210	(3)
Closure Properties and Decision Algorithms for Context-Free Languages	213	(8)
Closure of Context-Free Languages	213	(5)
Some Decidable Properties of Context-Free Languages	218	(3)
Turing Machines	221	(28)
The Standard Turing Machine	222	(16)
Definition of a Turing Machine	222	(7)
Turing Machines as Language Accepters	229	(3)
Turing Machines as Transducers	232	(6)
Combining Turing Machines for Complicated Tasks	238	(6)
Turing's Thesis	244	(5)
Other Models of Turing Machines	249	(26)
Minor Variations on the Turing Machine Theme	250	(8)
Equivalence of Classes of Automata	250	(1)
Turing Machines with a Stay-Option	251	(2)
Turing Machines with Semi-Infinite Tape	253	(2)
The Off-Line Turing Machine	255	(3)
Turing Machines with More Complex Storage	258	(5)
Multitape Turing Machines	258	(3)
Multidimensional Turing Machines	261	(2)
Nondeterministic Turing Machines	263	(3)
A Universal Turing Machine	266	(4)
Linear Bounded Automata	270	(5)
A Hierarchy of Formal Languages and Automata	275	(24)
Recursive and Recursively Enumerable Languages	276	(7)
Languages That Are Not Recursively Enumerable	278	(1)
A Language That Is Not Recursively Enumerable	279	(2)
A Language That Is Recursively Enumerable But Not Recursive	281	(2)
Unrestricted Grammars	283	(6)
Context-Sensitive Grammars and Languages	289	(6)
Context-Sensitive Languages and Linear Bounded Automata	290	(2)
Relation Between Recursive and Context-Sensitive Languages	292	(3)
The Chomsky Hierarchy	295	(4)
Limits of Algorithmic Computation	299	(24)
Some Problems That Cannot Be Solved By Turing Machines	300	(8)
The Turing Machine Halting Problem	301	(3)
Reducing One Undecidable Problem to Another	304	(4)
Undecidable Problems for Recursively Enumerable Languages	308	(4)
The Post Correspondence Problem	312	(6)
Undecidable Problems for Context-Free Languages	318	(5)
Other Models of Computation	323	(20)
Recursive Functions	325	(9)
Primitive Recursive Functions	326	(4)
Ackermann's Function	330	(4)
Post Systems	334	(3)
Rewriting Systems	337	(6)
Markov Algorithms	339	(1)
L-Systems	340	(3)
An Introduction to Computational Complexity	343	(14)
Efficiency of Computation	344	(2)
Turing Machines and Complexity	346	(4)
Language Families and Complexity Classes	350	(3)
The Complexity Classes P and NP	353	(4)
Answers to Selected Exercises	357	(48)
References	405	(2)
Index	407