I recently started studying theory of computation.

Recusive enumerable language – closed under concatenation. Sir, I have a doubt regarding understanding of this.

Please Note - RE shortform i am taking for Recusively enumerative language

One way --> If L1, and L2 are RE s then L1.L2 is RE then RE is closed under concatenation.

Another way if we talk interms of strings, If for all ‘a’ belongs to L1 and for all ‘b’ belongs to L2 then w=a.b belongs to L1.L2.

What about the other side? Please see if this is correct?

For closure under concatenation, If w belongs to L1.L2 then all or some string splits of w into 2 make 1st part acceptance under L1 and 2nd string split acceptance under L2?

I was thinking, as L1 and L2 are REs we can make L1.L2 RE by concatenating L1 and L2 turing machines and make start state as start state of L1 and endstate as final state of L2. But when i am thinking in terms of string input i am getting confused

THe proof in my textbook says that we can non-deterministically split w into 2 parts so that each part accepted by Turing machines for L1 and L2 respectively. If string length is n, then we can have (n+1) kinds of 2 splits of w-string. Will the L1.L2 turing machine accepts all these n+1 types of w-splits? But this is what we need to prove right?

enter image description here


1 Answer 1


If $L_1,L_2$ are two languages over a common alphabet, then their concatenation is given by $$ L_1 L_2 = \{ x_1 x_2 : x_1 \in L_1 \text{ and } x_2 \in L_2 \}. $$ If $L_1,L_2$ are r.e. then so is their concatenation. To see this, you can use the following algorithm. Given an input $x$, consider all possible partitions $x = x_1x_2$. For each partition, run a machine for $L_1$ on $x_1$ and a machine for $L_2$ on $x_2$; do this in parallel for all possible partitions. Accept if for some partition $x = x_1x_2$, you find that both $x_1 \in L_1$ and $x_2 \in L_2$.

  • $\begingroup$ Sir ideally Concatenation means it should accept all kinds of possible partitions right? Why only 1 possible partition acceptance by L1L2 turing machine. Why other partition is not getting accepted? $\endgroup$ Aug 25, 2019 at 21:11
  • $\begingroup$ Again what is guarantee that even 1 possible partition will be accepted? $\endgroup$ Aug 25, 2019 at 21:12
  • 1
    $\begingroup$ A word $x$ is in the language $L_1L_2$ if there exists a partition $x = x_1x_2$ such that $x_1 \in L_1$ and $x_2 \in L_2$. This is the definition. $\endgroup$ Aug 25, 2019 at 21:13
  • $\begingroup$ THank you for clarifying the definition part. But Sir if i take following case - say $T_1$ is turing machine for $L_1$ and $T_2$ for $L_2$. Now i connect end state of $T_1$ to start state of $T_2$ and make start state as start state of $T_1$ and final state as final state of $T_2$, THis is turing machine description of concatenation right?(Pls correct me if i am wrog here). In this case, it should accpet all kinds of partitions of w right? $\endgroup$ Aug 25, 2019 at 21:16
  • $\begingroup$ This won't work even for recursive languages. It doesn't work even for DFAs. Try it on $L_1 = a^*$ and $L_2 = b^*$. $\endgroup$ Aug 25, 2019 at 21:18

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.