Information Technology Reference
In-Depth Information
qaδ
(
σ
,
q
)
q
1
qaδ
(
σ
,
q
)
q
1
q
1
R
q
2
β
0
0
q
1
q
1
R
q
1
q
3
β
1
1
q
1
β
hβ
q
1
β
hβ
q
2
q
4
R
0
q
2
q
4
R
1
q
2
β
q
4
R
q
3
q
5
R
0
q
3
q
5
R
1
q
3
β
q
5
R
q
4
0
q
2
0
q
4
1
q
3
0
q
4
β
h
0
q
5
0
q
2
1
q
5
1
q
3
1
q
5
β
h
1
(a)
(b)
Figure 5.3
The transition functions of two Turing machines, one (a) that moves across the
non-blank symbols on its tape and halts over the first blank symbol, and a second (b) that moves
the input string right one position and inserts a blank to its left.
it moves right. If it is the blank symbol, it halts. This TM can be extended to replace the
rightmost character in a string of non-blank characters with a blank. After finding the blank
on the right of a non-blank string, it backs up one cell and replaces the character with a blank.
Both TMs compute functions that map strings to strings.
A second example is a TM that replaces the first letter in its input string with a blank and
shifts the remaining letters right one position. (See Fig.
5.3
(b).) In its initial state
q
1
this TM,
which is assumed to be given a non-blank input string, records the symbol under the tape head
by entering
q
2
if the letter is 0 or
q
3
if the letter is 1 and writing the blank symbol. In its
current state it moves right and enters a corresponding state. (It enters
q
4
if its current state
is
q
2
and
q
5
if it is
q
3
.
)
In the new state it prints the letter originally in the cell to its left and
enters either
q
2
or
q
3
depending on whether the current cell contains 0 or 1. This TM can
be used to insert a special end-of-tape marker instead of a blank to the left of a string written
initially on a tape. This idea can generalized to insert a symbol anyplace in another string.
AthirdexampleofaTM
M
is one that accepts strings in the language
L
=
a
n
b
n
c
n
{
|
n
≥
1
.
M
inserts an end-of-tape marker to the left of a string
w
placed on its tape and uses a
computation denoted
C
(
x
,
y
)
, in which it moves right across zero or more
x
's followed by
zero or more “pseudo-blanks” (a symbol other than
a
,
b
,
c
,or
β
) to an instance of
y
,entering
a non-accepting halt state
f
if some other pattern of letters is found. Starting in the first cell,
if
M
discovers that the next letter is not
a
, it exits to state
f
.Ifitis
a
,itreplaces
a
by a
pseudo-blank. It then executes
C
(
a
,
b
)
.
M
then replaces
b
by a pseudo-blank and executes
C
(
b
,
c
)
, after which it replaces
c
by a pseudo-blank and executes
C
(
c
,
β
)
.Itthenreturnsto
the beginning of the tape. If it arrives at the end-of-tape marker without encountering any
}
Search WWH ::
Custom Search