Here we introduce a convenient shorthand notation in which several production
rules with the same left-hand sides are written on the same line, with alternative
right-hand sides separated by |. In this notation S → aAb|λ stands for the two
productions S → aAb and S → λ.
This grammar is equivalent to the grammar G in Example 1.11. The
equivalence is easy to prove by showing that
We leave this as an exercise.
Automata
An automaton is an abstract model of a digital computer. As such, every
automaton includes some essential features. It has a mechanism for reading
input. It will be assumed that the input is a string over a given alphabet, written
on an input file, which the automaton can read but not change. The input file is
divided into cells, each of which can hold one symbol. The input mechanism can
read the input file from left to right, one symbol at a time. The input mechanism
can also detect the end of the input string (by sensing an end-of-file condition).
The automaton can produce output of some form. It may have a temporary
storage device, consisting of an unlimited number of cells, each capable of
holding a single symbol from an alphabet (not necessarily the same one as the
input alphabet). The automaton can read and change the contents of the storage
cells. Finally, the automaton has a control unit, which can be in any one of a
finite number of internal states, and which can change state in some defined
manner. Figure 1.4 shows a schematic representation of a general automaton.
An automaton is assumed to operate in a discrete timeframe. At any given
time, the control unit is in some internal state, and the input mechanism is
scanning a particular symbol on the input file. The internal state of the control
unit at the next time step is determined by the next-state or transition function.
This transition function gives the next state in terms of the current state, the
current input symbol, and the information currently in the temporary storage.
rules with the same left-hand sides are written on the same line, with alternative
right-hand sides separated by |. In this notation S → aAb|λ stands for the two
productions S → aAb and S → λ.
This grammar is equivalent to the grammar G in Example 1.11. The
equivalence is easy to prove by showing that
We leave this as an exercise.
Automata
An automaton is an abstract model of a digital computer. As such, every
automaton includes some essential features. It has a mechanism for reading
input. It will be assumed that the input is a string over a given alphabet, written
on an input file, which the automaton can read but not change. The input file is
divided into cells, each of which can hold one symbol. The input mechanism can
read the input file from left to right, one symbol at a time. The input mechanism
can also detect the end of the input string (by sensing an end-of-file condition).
The automaton can produce output of some form. It may have a temporary
storage device, consisting of an unlimited number of cells, each capable of
holding a single symbol from an alphabet (not necessarily the same one as the
input alphabet). The automaton can read and change the contents of the storage
cells. Finally, the automaton has a control unit, which can be in any one of a
finite number of internal states, and which can change state in some defined
manner. Figure 1.4 shows a schematic representation of a general automaton.
An automaton is assumed to operate in a discrete timeframe. At any given
time, the control unit is in some internal state, and the input mechanism is
scanning a particular symbol on the input file. The internal state of the control
unit at the next time step is determined by the next-state or transition function.
This transition function gives the next state in terms of the current state, the
current input symbol, and the information currently in the temporary storage.