An Introduction to Formal Languages and Automata

Title
Copyright
CONTENTS
PREFACE
1 INTRODUCTION TO THE THEORY OF COMPUTATION
	1.1 Mathematical Preliminaries and Notation
		Sets
		Functions and Relations
		Graphs and Trees
		Proof Techniques
	1.2 Three Basic Concepts
		Languages
		Grammars
		Automata
	1.3 Some Applications*
2 FINITE AUTOMATA
	2.1 Deterministic Finite Accepters
		Languages and Dfa’s
		Regular Languages
	2.2 Nondeterministic Finite Accepters
		Definition of a Nondeterministic Accepter
		Why Nondeterminism?
	2.3 Equivalence of Deterministic and Nondeterministic Finite Accepters
	2.4 Reduction of the Number of States in Finite Automata*
3 REGULAR LANGUAGES AND REGULAR GRAMMARS
	3.1 Regular Expressions
		Formal Definition of a Regular Expression
		Languages Associated with Regular Expressions
	3.2 Connection Between Regular Expressions and Regular Languages
		Regular Expressions Denote Regular Languages
		Regular Expressions for Regular Languages
		Regular Expressions for Describing Simple Patterns
	3.3 Regular Grammars
		Right- and Left-Linear Grammars
		Right-Linear Grammars Generate Regular Languages
		Right-Linear Grammars for Regular Languages
		Equivalence of Regular Languages and Regular Grammars
4 PROPERTIES OF REGULAR LANGUAGES
	4.1 Closure Properties of Regular Languages
		Closure under Simple Set Operations
		Closure under Other Operations
	4.2 Elementary Questions about Regular Languages
	4.3 Identifying Nonregular Languages
		Using the Pigeonhole Principle
		A Pumping Lemma
5 CONTEXT-FREE LANGUAGES
	5.1 Context-Free Grammars
		Examples of Context-Free Languages
		Leftmost and Rightmost Derivations
		Derivation Trees
		Relation Between Sentential Forms and Derivation Trees
	5.2 Parsing and Ambiguity
		Parsing and Membership
		Ambiguity in Grammars and Languages
	5.3 Context-Free Grammars and Programming Languages
6 SIMPLIFICATION OF CONTEXT-FREE GRAMMARS AND NORMAL FORMS
	6.1 Methods for Transforming Grammars
		A Useful Substitution Rule
		Removing Useless Productions
		Removing λ-Productions
		Removing Unit-Productions
	6.2 Two Important Normal Forms
		Chomsky Normal Form
		Greibach Normal Form
	6.3 A Membership Algorithm for Context-Free Grammars*
7 PUSHDOWN AUTOMATA
	7.1 Nondeterministic Pushdown Automata
		Definition of a Pushdown Automaton
		The Language Accepted by a Pushdown Automaton
	7.2 Pushdown Automata and Context-Free Languages
		Pushdown Automata for Context-Free Languages
		Context-Free Grammars for Pushdown Automata
	7.3 Deterministic Pushdown Automata and Deterministic Context-Free Languages
	7.4 Grammars for Deterministic Context-Free Languages*
8 PROPERTIES OF CONTEXT-FREE LANGUAGES
	8.1 Two Pumping Lemmas
		A Pumping Lemma for Context-Free Languages
		A Pumping Lemma for Linear Languages
	8.2 Closure Properties and Decision Algorithms for Context-Free Languages
		Closure of Context-Free Languages
		Some Decidable Properties of Context-Free Languages
9 TURING MACHINES
	9.1 The Standard Turing Machine
		Definition of a Turing Machine
		Turing Machines as Language Accepters
		Turing Machines as Transducers
	9.2 Combining Turing Machines for Complicated Tasks
	9.3 Turing’s Thesis
10 OTHER MODELS OF TURING MACHINES
	10.1 Minor Variations on the Turing Machine Theme
		Equivalence of Classes of Automata
		Turing Machines with a Stay-Option
		Turing Machines with Semi-Infinite Tape
		The Off-Line Turing Machine
	10.2 Turing Machines with More Complex Storage
		Multitape Turing Machines
		Multidimensional Turing Machines
	10.3 Nondeterministic Turing Machines
	10.4 A Universal Turing Machine
	10.5 Linear Bounded Automata
11 A HIERARCHY OF FORMAL LANGUAGES AND AUTOMATA
	11.1 Recursive and Recursively Enumerable Languages
		Languages That Are Not Recursively Enumerable
		A Language That Is Not Recursively Enumerable
		A Language That Is Recursively Enumerable but Not Recursive
	11.2 Unrestricted Grammars
	11.3 Context-Sensitive Grammars and Languages
		Context-Sensitive Languages and Linear Bounded Automata
		Relation Between Recursive and Context-Sensitive Languages
	11.4 The Chomsky Hierarchy
12 LIMITS OF ALGORITHMIC COMPUTATION
	12.1 Some Problems That Cannot Be Solved by Turing Machines
		Computability and Decidability
		The Turing Machine Halting Problem
		Reducing One Undecidable Problem to Another
	12.2 Undecidable Problems for Recursively Enumerable Languages
	12.3 The Post Correspondence Problem
	12.4 Undecidable Problems for Context-Free Languages
	12.5 A Question of Efficiency
13 OTHER MODELS OF COMPUTATION
	13.1 Recursive Functions
		Primitive Recursive Functions
		Ackermann’s Function
		μ Recursive Functions
	13.2 Post Systems
	13.3 Rewriting Systems
		Matrix Grammars
		Markov Algorithms
		L-Systems
14 AN OVERVIEW OF COMPUTATIONAL COMPLEXITY
	14.1 Efficiency of Computation
	14.2 Turing Machine Models and Complexity
	14.3 Language Families and Complexity Classes
	14.4 The Complexity Classes P and NP
	14.5 Some NP Problems
	14.6 Polynomial-Time Reduction
	14.7 NP-Completeness and an Open Question
APPENDIX A: FINITE-STATE TRANSDUCERS
	A.1 A General Framework
	A.2 Mealy Machines
	A.3 Moore Machines
	A.4 Moore and Mealy Machine Equivalence
	A.5 Mealy Machine Minimization
	A.6 Moore Machine Minimization
	A.7 Limitations of Finite-State Transducers
APPENDIX B: JFLAP: A USEFUL TOOL
ANSWERS SOLUTIONS AND HINTS FOR SELECTED EXERCISES
REFERENCES FOR FURTHER READING
INDEX
	A
	B
	C
	D
	E
	F
	G
	H
	I
	J
	L
	M
	N
	O
	P
	R
	S
	T
	U
	V
	W
	Y
	Z