686
Modeling Arithmetic, Computation, and Languages
686
Modeling Arithmetic, Computation, and Languages
A mathematical structure, as discussed in Chapter 8, is a formal model intended
to capture common properties or behavior found in different contexts. A structure
consists of an abstract set of objects, together with operations on or relationships
among those objects that obey certain rules. The Boolean algebra structure of
Chapter 8 is a model of the properties and behavior common to both propositional
logic and set theory. As a formal model, it is an abstract entity, an idea; propositional logic and set theory are two instances, or realizations, of this idea.
In this chapter we study other structures. In Section 9.1, algebraic structures
are defined that model various types of arithmetic such as addition of integers and
multiplication of positive real numbers. As an aside, section 9.2 looks at coding
theory, an important application of one of these algebraic structures. This type of
encoding (and decoding) is not about secrecy but about detecting and perhaps correcting bit errors in data transmission or storage.
The “arithmetics” of Section 9.1 represent a limited form of computation, but
we will see models of much broader forms of computation in Sections 9.3 and 9.4.
Our initial choice for such a model, the finite-state machine, is a useful device for
certain tasks, such as the lexical analysis task facing your team at Babel. But the
finite-state machine is ultimately too limited to model computation in the general
sense. For a model that captures the notion of computation in all its generality, we
turn to the Turing machine. Using the Turing machine as a model of computation
will reveal that some well-defined tasks are not computable at all.
Finally, Section 9.5 discusses formal grammars and languages, which were
developed as attempts to model natural languages such as English. While less
than completely successful in this regard, formal grammars and languages do
serve to model many constructs in programming languages and play an important
role in compiler theory.
S e c t i o n 9 . 1 Algebr AiC StruCtureS
Definitions and Examples
We begin by analyzing a simple form of arithmetic, namely the addition of integers. There is a set Z of objects (the integers) and a binary operation on those
objects (addition). Recall from Section 4.1 that a binary operation on a set must be
well defined (giving a unique answer whenever it is applied to any two members
of the set) and that the set must be closed under the operation (the answer must
be a member of the set). The notation 3Z, + 4 will denote the set together with the
binary operation on that set.
In 3Z, + 4, an equation such as
2 + (3 + 5) = (2 + 3) + 5
is true. On each side of the equation the integers remain in the same order, but the
grouping of those integers, which indicates the order in which the additions are
performed, changes. Changing the grouping has no effect on the answer. Another
type of equation that holds in 3Z, + 4 is
2 + 3 = 3 + 2
Modeling Arithmetic, Computation, and Languages
686
Modeling Arithmetic, Computation, and Languages
A mathematical structure, as discussed in Chapter 8, is a formal model intended
to capture common properties or behavior found in different contexts. A structure
consists of an abstract set of objects, together with operations on or relationships
among those objects that obey certain rules. The Boolean algebra structure of
Chapter 8 is a model of the properties and behavior common to both propositional
logic and set theory. As a formal model, it is an abstract entity, an idea; propositional logic and set theory are two instances, or realizations, of this idea.
In this chapter we study other structures. In Section 9.1, algebraic structures
are defined that model various types of arithmetic such as addition of integers and
multiplication of positive real numbers. As an aside, section 9.2 looks at coding
theory, an important application of one of these algebraic structures. This type of
encoding (and decoding) is not about secrecy but about detecting and perhaps correcting bit errors in data transmission or storage.
The “arithmetics” of Section 9.1 represent a limited form of computation, but
we will see models of much broader forms of computation in Sections 9.3 and 9.4.
Our initial choice for such a model, the finite-state machine, is a useful device for
certain tasks, such as the lexical analysis task facing your team at Babel. But the
finite-state machine is ultimately too limited to model computation in the general
sense. For a model that captures the notion of computation in all its generality, we
turn to the Turing machine. Using the Turing machine as a model of computation
will reveal that some well-defined tasks are not computable at all.
Finally, Section 9.5 discusses formal grammars and languages, which were
developed as attempts to model natural languages such as English. While less
than completely successful in this regard, formal grammars and languages do
serve to model many constructs in programming languages and play an important
role in compiler theory.
S e c t i o n 9 . 1 Algebr AiC StruCtureS
Definitions and Examples
We begin by analyzing a simple form of arithmetic, namely the addition of integers. There is a set Z of objects (the integers) and a binary operation on those
objects (addition). Recall from Section 4.1 that a binary operation on a set must be
well defined (giving a unique answer whenever it is applied to any two members
of the set) and that the set must be closed under the operation (the answer must
be a member of the set). The notation 3Z, + 4 will denote the set together with the
binary operation on that set.
In 3Z, + 4, an equation such as
2 + (3 + 5) = (2 + 3) + 5
is true. On each side of the equation the integers remain in the same order, but the
grouping of those integers, which indicates the order in which the additions are
performed, changes. Changing the grouping has no effect on the answer. Another
type of equation that holds in 3Z, + 4 is
2 + 3 = 3 + 2