I'm having troubles with this question.
If $L\in R$, there there is a turing machine $M$ that decides it.
My idea is to build a turing machine $M'$ that somehow goes over all the possible permutations of the input word, in a way that separates it to groups of smaller words for $M$ to test. If there is a permutation that is accepted by all the invoked $M$s, $M'$ should accept this word. (or if it is $\epsilon$)
Since the number of permutations is finite, we can traverse all over them and reject the word eventually, hence $L^*\in R$.
But I'm not sure how to formulate it.
Asked
Viewed
65 times
$\begingroup$
$\endgroup$
-
1$\begingroup$ The word permutation has a specific meaning in mathematics which differs from the one you implicitly use. $\endgroup$ – Yuval Filmus May 12 '18 at 17:22
-
$\begingroup$ It seems your basic reasoning is fine. Perhaps you can get some ideas how to formulate the solution by looking at the answers to this related question: Decidable languages kleene star closure - question on a proof. $\endgroup$ – Hendrik Jan May 14 '18 at 12:15
-
$\begingroup$ It is not always clear what the right formulation is: it depends on the audience, the people that read the solution, and their level of knowledge. So, it might be sufficent to say that the TM guesses a decomposition into subwords, but in other contexts one wants to explain how the TM tests all decompositions, and how to write a TM subroutine that tests a certain substring for membership. The more details, the more tedious it gets. $\endgroup$ – Hendrik Jan May 14 '18 at 12:16
-
$\begingroup$ @HendrikJan Thanks. I have consulted my TA, and indeed I needed to write a pretty detailed implementation. $\endgroup$ – porcupine May 14 '18 at 14:53
