Information Technology Reference
In-Depth Information
5.19 Show that the following language is decidable:
L
=
{
ρ
(
G
)
,
w
|
ρ
(
G
)
encodes a CFG
G
that generates
w
}
Hint:
How long is a derivation of
w
if
G
is in Chomsky normal form?
5.20 Show that the following language is decidable:
L
=
{
ρ
(
G
)
|
ρ
(
G
)
encodes a CFG
G
for which
L
(
G
)
=
∅}
5.21 Let
L
1
,
L
2
∈
P
where
P
is the class of polynomial-time problems (see Definition
3.7.2
).
Show that the following statements hold:
a)
L
1
∪
L
2
∈
P
L
1
L
2
∈
P
,where
L
1
L
2
is the concatenation of
L
1
and
L
2
b)
c)
L
1
∈
P
P
. Show that
L
1
∈
5.22 Let
L
1
∈
P
.
Hint:
Try using dynamic programming, the algorithmic concept illustrated by the
parsing algorithm of Theorem
4.11.2
.
UNSOLVABLE PROBLEMS
5.23 Show that the problem of determining whether an arbitrary TM starting with a blank
tape will ever halt is unsolvable.
5.24 Show that the following language is undecidable:
L
EQ
=
{
ρ
(
M
1
)
,
ρ
(
M
2
)
|
L
(
M
1
)=
L
(
M
2
)
}
5.25 Determine which of the following problems are solvable and unsolvable. Defend your
conclusions.
a)
{
ρ
(
M
)
,
w
,
p
|
M
reaches state
p
on input
w
from its initial state
}
{
there is a configuration
[
u
1
...u
m
q
v
1
...v
n
]
yielding a configuration
containing state
p
ρ
(
M
)
,
p
|
b)
}
c)
{
ρ
(
M
)
,
a
|
M
writes character
a
when started on the empty tape
}
d)
{
ρ
(
M
)
|
M
writes a non-blank character when started on the empty tape
}
{
ρ
(
M
)
,
w
|
on input
w
M
moves its head to the left
}
e)
FUNCTIONS COMPUTED BY TURING MACHINES
5.26 Define the integer division function
f
div
:
2
→
using primitive recursion.
5.27 Show that the function
f
remain
:
2
→
that provides the remainder of
x
after
division by
y
is a primitive recursive function.
5.28 Show that the factorial function
x
!
is primitive recursive.
5.29 Write a RAM program (see Section
3.4.3
) to realize the composition operation.
5.30 Write a RAM program (see Section
3.4.3
) to realize the primitive recursion operation.
5.31 Write a RAM program (see Section
3.4.3
) to realize the minimalization operation.
Search WWH ::
Custom Search