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$
$\endgroup$
1
-
$\begingroup$ Just think of accepting and rejecting states in Turing Machine accepting the language. $\endgroup$– nitishchCommented Apr 20, 2014 at 4:18
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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?
