Information Technology Reference
In-Depth Information
Control
Unit
Figure 5.14
A schematic representation of a two-dimensional Turing machine.
5.11 By analogy with the construction given in Section
3.9.7
, show that every deterministic
T
-step multi-tape Turing machine computation can be simulated on a two-tape Turing
machine in
O
(
T
log
T
)
steps.
PHRASE-STRUCTURE LANGUAGES AND TURING MACHINES
a
n
b
n
c
n
{
|
n
≥
}
5.12 Give a detailed design of a Turing machine recognizing
.
5.13 Use the method of Theorem
5.4.1
to construct a phrase-structure grammar generating
{
1
a
n
b
n
c
n
|
n
≥
}
.
5.14 Design a Turing machine recognizing the language
1
0
2
i
{
|
i
≥
}
1
.
UNIVERSAL TURING MACHINES
5.15 Using the description of Section
5.5
, give a complete description of a universal Turing
machine.
5.16 Construct a universal TM that has only two non-accepting states.
DECIDABLE PROBLEMS
5.17 Show that the following languages are decidable:
a)
L
=
{
ρ
(
M
)
,
w
|
M
is a DFSM that accepts the input string
w
}
}
5.18 The
symmetric differe
nce
between sets
A
and
B
is defined by
(
A
b)
L
=
{
ρ
(
M
)
|
M
is a DFSM and
L
(
M
)
is infinite
−
B
)
∪
(
B
−
A
)
,
where
A
−
B
=
A
∩
B
. Use the symmetric difference to show that the following
language is decidable:
L
EQ FSM
=
{
ρ
(
M
1
)
,
ρ
(
M
2
)
|
M
1
and
M
2
are FSMs recognizing the same language
}
Search WWH ::
Custom Search