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?