another make extensive use of the ideas touched on in these examples.
Programming languages can be defined precisely through grammars, as in
Example 1.15, and both grammars and automata play a fundamental role in the
decision processes by which a specific piece of code is accepted as satisfying the
conditions of a programming language. The above example gives a first hint of
how this is done; subsequent examples will expand on this observation.
Transducers will be discussed briefly in Appendix A; the following example
previews this subject.
Example 1.17
A binary adder is an integral part of any general-purpose computer. Such an
adder takes two bit strings representing numbers and produces their sum as
output. For simplicity, let us assume that we are dealing only with positive
integers and that we use a representation in which
stands for the integer
This is the usual binary representation in reverse.
A serial adder processes two such numbers x = a 0 a 1 …a n , and y = b 0 b 1 …b n ,
bit by bit, starting at the left end. Each bit addition creates a digit for the sum as
well as a carry digit for the next higher position. A binary addition table (Figure
1.7) summarizes the process.
Figure 1.7