Decidable languages kleene star closure - question on a proof

Question

I read a proof on the closure of decidable languages under kleene star. It begins by saying that the turing machine we want to find would non-determistically split the input string and then use the original decider of the language to approve the partition of each branch.

My question is, I can't understand how we can do this non-deterministic split on a word whose length we do not yet know. if the word is very big then there exist more partitions, thus more branches are needed.

So, i don't understand how this "non-deterministic split" can be materialized.

Also, if someone has another proof of this closure via turing machines it will be more than welcome!

Answer 1

It can be hard to grasp why we can just reason about an NTM to prove the Kleene star closure for decidable languages. The important fact is that any nondeterministic TM can be simulated by a deterministic TM. In some cases, it will just take a whole lot of time. When the topic is decidable languages, we are only concerned with whether something can be decided or not, regardless of how much time it will take to figure out. Therefore, an NTM will sometimes be more convenient to reason about, as we can abstract the "try all possible ways to do this", into "guess the right way to do this". However, the abstraction is only valid if we have a finite number of possibilities to try, of course.

So, for the Kleene star closure:

Assume that we have a decidable language $A$. Given that $A$ is decidable, there exists a decider for $A$, let us call it $M_A$. From this $M_A$, we can now construct a decider of $A^\ast$, let us call that decider $M_{A^\ast}$.

This is a description of how $M_{A^\ast}$ works:

On input $w$:

If $w = \varepsilon$ (the empty string), accept

For all possible splits of $w$ into $w_1,w_2,...,w_k$: if $M_A$ accepts all the strings $w_1, w_2, ..., w_k$, then accept

If all splits have been tried without success, reject.

Lets look at an example where $A = \{w \in \{a,b,c\}^\ast \; | \; w \; \text{starts with} \; ab \; \text{or ends with} \; c\}$

For instance, we have that $\{c, ab, ac, bc, cc, aac\} \subset A$, but $\{a, b, aa, ba, bb, ca\} \cap A = \emptyset$.

Now, let us look at how $M_{A^\ast}$ will determine whether or not the string $ccab$ is in $A^\ast$:

First, $M_{A^\ast}$ checks the trivial case. Since $w \neq \varepsilon$, it cannot accept right away. It now has to try all the 8 possible splits of $ccab$ listed here:

$S_1 = \{ccab\}$

$S_2 = \{cca, b\}$

$S_3 = \{cc, ab\}$

$S_4 = \{c, cab\}$

$S_5 = \{cc, a, b\}$

$S_6 = \{c, c, ab\}$

$S_7 = \{c, ca, b\}$

$S_8 = \{c, c, a, b\}$

NOTE: $S_8$ contains three , to allow us to split the string $w$ into each of its letters. Since we can either contain or remove each one of the commas, there are $2^3 = 8$ total splits.

You could argue that split $1$ is not a real split, but since it complies with our definition of a split, $M_A'$ has to check whether $A$ accepts all $w' \in S_1$, which is only $ccab$. $M_A$ rejects $ccab$ because it does not start with $ab$ or end with $c$. In $S_2$, $cca$ is rejected by $M_A$, and hence $M_A'$ does not have to check $b$ and proceeds to split $S_3$. In $S_3$, both strings are accepted by $M_A$. $cc$ is accepted because it ends with $c$, and $ab$ is accepted because it starts with $ab$. The machine $M_A'$ now accepts, and hence $ccab \in A^\ast$, simply because $cc \in A$ and $ab \in A$.

Answer 2

With a Turing machine, you can always compute the length of the input as the first stage of the algorithm.

But, in this case, you don't need to. Suppose the language $L$ is decided by the Turing machine $M$. We can decide $L^*$ nondeterministically as follows. Start advancing the head through the input $w_1w_2\dots w_n$. At each step nondeterministically either just keep going or simulate $M$ to see if the word $w_1\dots w_k$ that you've seen so far is in $L$. If it's not in $L$, reject immediately. If it is in $L$, continue walking through the input, building up a new word $w_{k+1}w_{k+2}\dots w_{k'}$ and nondeterministically guessing when to check whether that's in $L$.

You don't need to partition the input before you start: you can do it "on the fly".

Answer 3

So, I don't understand how this "non-deterministic split" can be materialized.

I take it that your problem is understanding non-determinism.

In essence, the machine can make guesses: whenever the transition table offers more than one choice, it will just pick one of the alternatives. Intuitively, we then assume the machine always picks right; formally, we require it to do good in one of all possible computations¹.

So, given an input $w$ for we should check whether it is in $L^*$ for some recursive $L$, the machine can guess a split

$\qquad\displaystyle w = w_1 w_2 \dots w_k$

and then run decide $M_L$ of $L$ and combine the results; we output

$\qquad M_L(w_1) \cdot \dots \cdot M_L(w_k)$.

We can actually do that because we look at Turing machines and so we can, in particular, simulate $M_L$ as often as we want². Now, since we "always guess right" our machine finds a valid split if there is one.

Of course, we can get rid of the nondeterminism and just try all possible splits -- there's your alternative proof.

---

1. Please check out the formal definitions again. It's important to get them right when doing theory.
2. To convince yourself, come up with a C program (or similar) that does this.