xii
Contents
SECTiOn 9.1 Review
708
ExErCiSES 9.1
708
9.2 CODING THEORY
714
Introduction
714
Background: Homomorphisms
and Cosets
715
Generating Group Codes
717
Decoding Group Codes
723
SECTiOn 9.2 Review
727
ExErCiSES 9.2
727
9.3 FINITE-STATE MACHINES
728
Definition
729
Examples of Finite-State Machines 729
Recognition
733
Regular Sets and Kleene’s Theorem 735
Machine Minimization
737
Unreachable States
737
Minimization Procedure
739
Sequential Networks and
Finite-State Machines
744
special interest page
FSMs Behind the Game
749
SECTiOn 9.3 Review
750
ExErCiSES 9.3
750
9.4 TURING MACHINES
759
Definition
760
Turing Machines as Set
Recognizers
764
Turing Machines as Function
Computers
767
Church–Turing Thesis
769
Decision Problems and
Uncomputability
771
Examples of Decision
Problems
772
Halting Problem
773
Computational Complexity
776
SECTiOn 9.4 Review
778
ExErCiSES 9.4
779
9.5 FORMAL LANGUAGES
782
Classes of Grammars
789
Formal Languages and
Computational Devices
792
Context-Free Grammars
793
SECTiOn 9.5 Review
795
ExErCiSES 9.5
795
Chapter 9 Review
799
On the Computer
800
Appendix A
Derivation Rules for
Propositional and Predicate
Logic
803
Appendix B
Summation and Product
Notation
805
Appendix C
The Logarithm Function
809
Answers to Practice Problems
813
Answers to Odd-Numbered
Exercises
851
Answers to Self-Tests
949
Index
959