I can't figure out a proof that recursive languages are closed under concatenation. I know this is easy for most of the people but unfortunately my professor is not very good at explaining the material. If anybody can provide any hints on how to do it I would greatly appreciate it.

  • $\begingroup$ Just think of accepting and rejecting states in Turing Machine accepting the language. $\endgroup$
    – nitishch
    Apr 20, 2014 at 4:18

1 Answer 1


Imagine you have an algorithm $A$ that decides $L_A$ and an algorithm $B$ that accpts $L_B$. How would you write a program that checks whether any given word $w$ can we written as $w=uv$ with $u \in L_A$ and $v \in L_B$?

Broad hint: how many possible choices for $u$ and $v$ are there?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.