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 '14 at 4:18

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, privacy policy and cookie policy

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