Information Technology Reference
In-Depth Information
pushdown stack can be simulated by a tape in which the cell to the right of the tape head is
always blank. If the tape moves right from a cell, it writes a non-blank symbol in the cell. If it
moves left, it writes a blank in that cell before leaving it.
Some computers are serial: they execute one operation on a fixed amount of data per time
step. Others are parallel; that is, they have multiple (usually communicating) subcomputers
that operate simultaneously. They may operate synchronously or asynchronously and they may
be connected via a simple or a complex network. An example of a simple network is a wire
between two computers. An example of a complex network is a crossbar switch consisting of
25 switches at the intersection of five columns and five rows of wires; closing the switch at the
intersection of a row and a column connects the two wires and the two computers to which
they are attached.
We close this section by emphasizing the importance of models of computers. Good mod-
els provide a level of abstraction at which important facts and insights can be developed without
losing so much detail that the results are irrelevant to practice.
1.4.5 Formal Languages
In Chapters
4
and
5
the finite-state machine, pushdown automaton, and Turing machine are
characterized by their language recognition capability. Formal methods for specifying lan-
guages have led to efficient ways to parse and recognize programming languages. This is il-
lustrated by the finite-state machine of Fig.
1.8
. Its initial state is
q
0
, its final state is
q
1
and
its inputs can assume values 0 or 1. An output of 0 is produced when the machine is in state
q
0
and an output of 1 is produced when it is in state
q
1
. The output before the first input is
received is 0.
After the first input the output of the FSM of Fig.
1.8
is equal to the input. After multiple
inputs the output is the
EXCLUSIVE OR
of the 1 's and 0 's among the input s , a s we show by
induction. The inductive hypothesis is clearly true after one input. Suppose it is true after
k
inputs; we show that it remains true after
k
+
1 inputs, and therefore for all inputs. The output
uniquely determines the state. There are two cases to consider: after
k
inputs either the FSM is
in state
q
0
or it is in state
q
1
. For each state, there are two cases to consider based on the value
of the
k
+
1st input. In all four cases it is easy to see that after the
k
+
1st input the output is
the
EXCLUSIVE OR
of the first
k
+
1inputs.
1
0
q
0
/
0
q
1
/
1
0
1
Initial
Figure 1.8
A state diagram for a finite-state machinewhosecircuitmodelisgiveninFig.
1.5
(b).
q
0
istheinitialstateofthemachineand
q
1
is its final state. If the machine is in
q
0
,ithasreceived
an even number of 1 inputs, whereas if it is in
q
1
, it has received an odd number of 1's.
Search WWH ::
Custom Search