decidability doubt

+1 vote
I am having difficulty in understanding how decidable (recursive) lang. are closed under Kleen closure? and are these lang. closed under positive closure?
asked Nov 25, 2016 in TOC by (850 points)

1 Answer

+1 vote
To understand the answer you should know the answer for this question1

Question 1:  Given an n length string how many ways it can be splitted.

Example: abcde

ab/cd/e a/bcd/e ab/cd/ on
Try to answer this question and then read below solution.

Given a recursive language We can construct turing machine for L* like this

step 1: split the input W in all possible ways. (Using TM we can do it)  the no of ways is solution to the question1
step 2: for each split w1#w2#w3...simulate TM of L on all the strings w1,w2,w3... and if it accepts all the strings w1,w2,w3 then Accept W.
Here you are accepting the string if it is concatenation of some strings which are all members of L.

Otherwise Reject
answered Nov 26, 2016 by getgatebook (33,570 points)