Question

Show that if languages L1 and L2 are decidable, then concatenation of L1 and L2 is also decidable.

Answer 1

Let L1 an L2 be two decidable languages.

Suppose we have an input w.

We non-deterministically w into two parts w1 and w2.

w1 ranges from empty to w and w2 ranges for the remaining.

Lets say we have two turing machine M1 and M2 which decides L1 and L2 respectively.

We run M1 on w1, if it accepts then we run M2 on w2, else reject. As the M1 decides the L1, so it is neccesary for M1 to accept in order to move forward.

If M2 runs on L2 then we accept. Other wise we reject.

So, if both turing machine of L1 and L2 accepts then accept, else reject.

Thus, if languages L1 and L2 are decidable, then concatenation of L1 and L2 is also decidable.