Information Technology Reference
In-Depth Information
the second in one step. There is one configuration corresponding to the initial state of the machine
and one corresponding to the final state. (We assume without loss of generality that, after accepting
an input string,
M
ND
enters a cleanup phase during which it places a fixed string on each tape.)
Configuration graphs are used in the next section to associate a phrase-structure language
with a Turing machine. They are also used in many places in Chapter
8
, especially in Sec-
tion
8.5.3
, where they are used to establish an important relationship between deterministic
and nondeterministic space classes.
5.4 Phrase-Structure Languages and Turing Machines
We now demonstrate that the phrase-structure languages and the languages accepted by Turing
machines are the same. We begin by showing that every recursively enumerable language
is a phrase-structure language. For this purpose we use configurations of one-tape Turing
machines. Then, for each phrase-structure language
L
we describe the construction of a TM
accepting
L
. We conclude that the languages accepted by TMs and described by phrase-
structure grammars are the same.
With these conventions as background, if a standard TM halts in its accepting halt state,
we can require that it halt with
β
1
β
on its tape when it accepts the input string
w
.Thus,
the TM configuration when a TM halts and accepts its input string is
[
h
β
1
β
]
. Its starting
configuration is
[
s
βw
1
w
2
...w
n
β
]
,where
w
=
w
1
w
2
...w
n
.
THEOREM
5.4.1
Every recursively enumerable language is a phrase-structure language.
Proof
Let
M
=(Γ
,
β
,
Q
,
δ
,
s
,
h
)
be a deterministic TM and let
L
(
M
)
be the recursively
enumerable language over the alphabet
Γ
that it accepts. The goal is to show the existence of
a phrase-structure grammar
G
=(
,
S
)
that can generate each string
w
of
L
, and no
others. Since the TM accepting
L
halts with
β
1
β
on its tape when started with
w
N
,
T
,
R
L
,we
design a grammar
G
that produces the configurations of
M
in reverse order. Starting with
the final configuration
[
h
β
1
β
]
,
G
produces the starting configuration
[
s
βw
1
w
2
...w
n
β
]
,
where
w
=
w
1
w
2
...w
n
, after which it strips off the characters
[
s
β
at the beginning and
β
]
. The grammar
G
defined below serves this purpose, as we show.
Let
∈
N
=
Q
∪{
S
,
β
,
[
,
]
}
T
=Γ
. The rules
R
of
G
are defined as follows:
and
→
[
h
β
1
β
]
(a)
S
β
]
→
ββ
]
(b)
[
s
β
→
(c)
(d)
ββ
]
→
β
]
(e)
β
]
→
(f )
x
q
→
p
x
for all
p
∈
Q
and
x
∈
(Γ
∪{
β
}
)
such that
δ
(
p
,
x
)=(
q
,
R
)
(g)
q
zx
→
z
p
x
for all
p
∈
Q
and
x
,
z
∈
(Γ
∪{
β
}
)
such that
δ
(
p
,
x
)=(
q
,
L
)
(h)
q
y
→
p
x
for all
p
∈
Q
and
x
∈
(Γ
∪{
β
}
)
such that
δ
(
p
,
x
)=(
q
,
y
)
,
y
∈
(Γ
∪{
β
}
)
[
h
β
1
β
]
(Rule (a)) and then
rewrite
[
h
β
1
β
]
using other rules until the configuration
[
s
βw
1
w
2
...w
n
β
]
is reached. At
These rules are designed to start with the transition
S
→
Search WWH ::
Custom Search