Exercise 11:

{u,v,RΣ={a,b}    uRv}{u,v,RuRv with an even number of steps but not with an odd number of steps}\{\langle u,v,R\rangle\mid\Sigma=\{a,b\}\;\wedge\;u\to_R^*v\}\quad\leq\quad\{\langle u,v,R\rangle \mid u\to_R^*v\text{ with an even number of steps but not with an odd number of steps}\} (morphism not allowed in the reduction)
Reduce the word reachability problem restricted to the alphabet {a,b}\{a,b\} to the set of tuples u,v,R\langle u,v,R\rangle where u,vu,v are words, RR is a word rewrite system, uu reaches vv using RR with an even number of steps, but it is not possible with an odd number of steps, in order to prove that such set is undecidable (not recursive).

The use of morphism is not allowed in the description of this reduction.
Authors: Guillem Godoy / Documentation:
To be able to submit you need to either log in, register, or become a guest.