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