792
Modeling Arithmetic, Computation, and Languages
This is a somewhat confusing point and worth repeating. Because a given
language can be generated by multiple grammars, if you find a grammar G for a
language L that is type x but not type y, that does not necessarily make L type x
but not type y. There might be a different grammar that also generates L and is a
type y grammar.
formal Languages and Computational Devices
The language L of Example 57 can be described by the regular expression
l ~ (000)(00)*, so L is a regular set. From Example 58, L is also a regular language.
It is not coincidental that a regular set turned out to be a regular language. It can be
shown that for any finite-state machine, the set it recognizes is a regular language. It
can also be shown that for any regular language, there is a finite-state machine that
recognizes exactly that language. (In the proofs of these results, the productions of a
regular grammar correspond to the state transitions of a finite-state machine.) Hence
those sets recognized by finite-state machines—the regular sets—correspond to
regular languages. Therefore the class of sets recognized by a computational device
of limited capacity coincides with the most restricted class of languages.
On the other end of the spectrum, the most general computational device is
the Turing machine and the most general language is a type 0 language. As it
happens, the sets recognized by Turing machines correspond to type 0 languages.
There are computational devices with capabilities midway between those of
finite-state machines and those of Turing machines. These devices recognize exactly the context-free languages and the context-sensitive languages, respectively.
The type of device that recognizes the context-free languages is called a
pushdown automaton, or pda. A pda consists of a finite-state unit that reads
input from a tape and controls activity in a stack. Symbols from some alphabet
can be pushed onto or popped off of the top of the stack. The finite-state unit in a
pda, as a function of the input symbol read, the present state, and the top symbol
on the stack, has a finite number of possible next moves. The moves are of the
following types:
1. Go to a new state, pop the top symbol off the stack, and read the next input
symbol.
2. Go to a new state, pop the top symbol off the stack, push a finite number
of symbols onto the stack, and read the next input symbol.
3. Ignore the input symbol being read, manipulate the stack as above, but do
not read the next input symbol.
A pda has a choice of next moves, and it recognizes the set of all inputs for which
some sequence of moves exists that causes it to empty its stack. It can be shown
that any set recognized by a pda is a context-free language, and conversely.
The type of device that recognizes the context-sensitive languages is called a
linear bounded automaton, or lba. An lba is a Turing machine whose read-write
head is restricted to a portion of the tape that is no longer than a constant multiple
of the length of the original input; in addition, at each step it has a choice of possible next moves. An lba recognizes the set of all inputs for which some sequence
PrACtiCe 65 Give the derivation of 00000 in G 1 , G 2 , and G 3 .
■
Modeling Arithmetic, Computation, and Languages
This is a somewhat confusing point and worth repeating. Because a given
language can be generated by multiple grammars, if you find a grammar G for a
language L that is type x but not type y, that does not necessarily make L type x
but not type y. There might be a different grammar that also generates L and is a
type y grammar.
formal Languages and Computational Devices
The language L of Example 57 can be described by the regular expression
l ~ (000)(00)*, so L is a regular set. From Example 58, L is also a regular language.
It is not coincidental that a regular set turned out to be a regular language. It can be
shown that for any finite-state machine, the set it recognizes is a regular language. It
can also be shown that for any regular language, there is a finite-state machine that
recognizes exactly that language. (In the proofs of these results, the productions of a
regular grammar correspond to the state transitions of a finite-state machine.) Hence
those sets recognized by finite-state machines—the regular sets—correspond to
regular languages. Therefore the class of sets recognized by a computational device
of limited capacity coincides with the most restricted class of languages.
On the other end of the spectrum, the most general computational device is
the Turing machine and the most general language is a type 0 language. As it
happens, the sets recognized by Turing machines correspond to type 0 languages.
There are computational devices with capabilities midway between those of
finite-state machines and those of Turing machines. These devices recognize exactly the context-free languages and the context-sensitive languages, respectively.
The type of device that recognizes the context-free languages is called a
pushdown automaton, or pda. A pda consists of a finite-state unit that reads
input from a tape and controls activity in a stack. Symbols from some alphabet
can be pushed onto or popped off of the top of the stack. The finite-state unit in a
pda, as a function of the input symbol read, the present state, and the top symbol
on the stack, has a finite number of possible next moves. The moves are of the
following types:
1. Go to a new state, pop the top symbol off the stack, and read the next input
symbol.
2. Go to a new state, pop the top symbol off the stack, push a finite number
of symbols onto the stack, and read the next input symbol.
3. Ignore the input symbol being read, manipulate the stack as above, but do
not read the next input symbol.
A pda has a choice of next moves, and it recognizes the set of all inputs for which
some sequence of moves exists that causes it to empty its stack. It can be shown
that any set recognized by a pda is a context-free language, and conversely.
The type of device that recognizes the context-sensitive languages is called a
linear bounded automaton, or lba. An lba is a Turing machine whose read-write
head is restricted to a portion of the tape that is no longer than a constant multiple
of the length of the original input; in addition, at each step it has a choice of possible next moves. An lba recognizes the set of all inputs for which some sequence
PrACtiCe 65 Give the derivation of 00000 in G 1 , G 2 , and G 3 .
■