# Doubt in definition of closure under concatenation operation in Recursive Enumerative languages

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.

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?

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$$.
• 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. Aug 25 '19 at 21:13
• 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? Aug 25 '19 at 21:16
• 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^*$. Aug 25 '19 at 21:18