FOTOC2 – Sample for 2nd TEST
1. Transitions of the nondeterministic Turing machineM = 〈{q0, q1, q2, q3, q4, q5, q6, qa, qr}, {a, b}, {a, b,t}, δ, q0, qi, qn〉
are given by the following transition diagram.
q0 q1 q2
q3q4
q5 q6
qa
a/t, R t/t, L
a
/
t
,L
t/t, R
a
/t
,R
b/
t
,R
t/t, L
b/t
,L
t/t, S
a/t,R
b/t,R
a/a,R
b/b,R
a/a,R
b/b,R
a/a,L
b/b,L
(a) Which transition(s) make M non-deterministic?
(b) Give an accepting computation (as a sequence of configurations) for baaa.
(c) Determine L(M), the language recognized by M . Support your answer by an argument.
(d) Is it true, that M has O(n2) time complexity? Why? (9 points)
2. (a) Give a deterministic Turing machine deciding L = {ambkcm | k,m ∈ N}.
Multitape TM’s are allowed. Tell a few words about your concept.
(b) Give an asymptotically sharp asymptotic upper bound for the time complexity of your machine. (7 points)
3. (a) Give a deterministic Turing machine computing the folloing function f : {0, 1}∗ → {0, 1}∗.
f(u) = preb|u|/2c(u),
where prek(u) denotes the prefix of u of length k. Multitape TM’s are allowed. Tell a few words about
your concept.
Examples: f(101011) = 101, f(10100) = 10, f(0) = λ.
(b) Give an asymptotically sharp asymptotic upper bound for the time complexity of your machine. (7 points)
4. Is there an instance D of Post Correspondence Problem satisfying all of the following properies
(i) |D| ≥ 3,
(i) the alphabet of the dominoes is {0, 1},
(ii) D has a solution,
(iv) there exists a domino of D, such that if we change one bit of the bottom word of this domino, then the new
set of dominos D′ has no solution.
Support your answer by an argument. (6 points)
Choose one from the following 2 exercises. You do not have to solve the other one. Points will be given only for the
chosen one.
5A. Let Lmin100 = {wi
∣∣ |L(Mi)| ≥ 100}, where wi is the ith word of {0, 1}∗. If wi is a code of a Turing machine,
then let us denote this machine by Mi.
Prove, that Lmin100 is undecidable.
OR
5B. A simple undirected graph is k-colorable if its vertices can be colored by k colors, such that no 2 endpoints of
an edge get the same color. Let k −Coloring = {〈G〉 |G is k-colorable }.
Prove, that 3−Coloring ≤p 5−Coloring.
(7 points)