290 );l Theory of Computer Science
9.6.2 STORAGE IN THE STATE
Weare using a state, whether it is of a FA or pda or TM, to 'remember' things.
We can use a state to store a symbol as well. So the state becomes a pair
(q, a) where q is the state (in the usual sense) and a is the tape symbol stored
in (q, a). So the new set of states becomes Q x r.
EXAMPLE 9.9
Construct a TM that accepts the language 0 1* + 1 0*.
Solution
We have to construct a TM that remembers the first symbol and checks that it
does not appear afterwards in the input string. So we require two states, qa, qj.
The tape symbols are 0, 1 and b. So the TM, having the 'storage facility in
state'. is
M = ({qa, qd x {O. L b}, {O, I}, {O, 1, b}, 0, [cIa, b], {[Cf], bJ})
We desClibe 0 by its implementation description.
L In the initial state, M is in qa and has b in its data portion. On seeing
the first symbol of the input sting w, M moves right, enters the state
Cft and the first symbol. say a, it has seen.
2. M is now in [q], a). (i) If its next symbol is b, M enters [cIt- b), an
accepting state. (ii) If the next symbol is a, M halts without reaching
the final state (i.e. 0 is not defined). (iii) If the next symbol is a
(a =°if a = 1 and a = 1 if a =0), M moves right without changing
state.
3. Step 2 is repeated until M reaches [qj, b) or halts (0 is not defined for
an input symbol in vv).
9.6.3 MULTIPLE TRACK TURING MACHINE
In the case of TM defined earlier, a single tape was used. In a multiple track
TM. a single tape is assumed to be divided into several tracks. Now the tape
alphabet is required to consist of k-tuples of tape symbols, k being the number
of tracks. Hence the only difference between the standard TM and the TM with
multiple tracks is the set of tape symbols. In the case of the standard Turing
machine, tape symbols are elements of r; in the case of TM with multiple track,
it is r
k . The moves are defined in a similar way.
9.6.4 SUBROUTINES
We know that subroutines are used in computer languages, when some task has
to be done repeatedly. We can implement this facility for TMs as well.
9.6.2 STORAGE IN THE STATE
Weare using a state, whether it is of a FA or pda or TM, to 'remember' things.
We can use a state to store a symbol as well. So the state becomes a pair
(q, a) where q is the state (in the usual sense) and a is the tape symbol stored
in (q, a). So the new set of states becomes Q x r.
EXAMPLE 9.9
Construct a TM that accepts the language 0 1* + 1 0*.
Solution
We have to construct a TM that remembers the first symbol and checks that it
does not appear afterwards in the input string. So we require two states, qa, qj.
The tape symbols are 0, 1 and b. So the TM, having the 'storage facility in
state'. is
M = ({qa, qd x {O. L b}, {O, I}, {O, 1, b}, 0, [cIa, b], {[Cf], bJ})
We desClibe 0 by its implementation description.
L In the initial state, M is in qa and has b in its data portion. On seeing
the first symbol of the input sting w, M moves right, enters the state
Cft and the first symbol. say a, it has seen.
2. M is now in [q], a). (i) If its next symbol is b, M enters [cIt- b), an
accepting state. (ii) If the next symbol is a, M halts without reaching
the final state (i.e. 0 is not defined). (iii) If the next symbol is a
(a =°if a = 1 and a = 1 if a =0), M moves right without changing
state.
3. Step 2 is repeated until M reaches [qj, b) or halts (0 is not defined for
an input symbol in vv).
9.6.3 MULTIPLE TRACK TURING MACHINE
In the case of TM defined earlier, a single tape was used. In a multiple track
TM. a single tape is assumed to be divided into several tracks. Now the tape
alphabet is required to consist of k-tuples of tape symbols, k being the number
of tracks. Hence the only difference between the standard TM and the TM with
multiple tracks is the set of tape symbols. In the case of the standard Turing
machine, tape symbols are elements of r; in the case of TM with multiple track,
it is r
k . The moves are defined in a similar way.
9.6.4 SUBROUTINES
We know that subroutines are used in computer languages, when some task has
to be done repeatedly. We can implement this facility for TMs as well.