5
$\begingroup$

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!

$\endgroup$
6
$\begingroup$

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, cab\}$

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

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$.

$\endgroup$
  • $\begingroup$ how can we make the machine find all possible splits? sorry if the question is trivial $\endgroup$ – lea Jan 18 '14 at 19:54
  • $\begingroup$ That was a good question, I have updated the answer trying to explain how it can be done. $\endgroup$ – Kent Munthe Caspersen Jan 19 '14 at 12:42
3
$\begingroup$

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".

$\endgroup$
  • $\begingroup$ i can see what you say in an automato but not in a turing machine $\endgroup$ – lea Jan 20 '14 at 20:18
  • $\begingroup$ What difference does it make? A Turing machine is just an automaton connected to a tape. $\endgroup$ – David Richerby Jan 20 '14 at 23:43
  • $\begingroup$ no it is not. automata and turing machines work differently and recognise a different class of languages. if what you mean is imitate the proof of the automata closure here, this is not possible - as far as I can see of course. $\endgroup$ – lea Jan 21 '14 at 17:02
  • $\begingroup$ It is possible -- my answer explains exactly how! It seems you've missed the extremely close connection between automata and Turing machines. An automaton is exactly a Turing machine with the restriction that the head must move one cell to the right at every step of the computation. $\endgroup$ – David Richerby Jan 21 '14 at 22:21
2
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ if i do this non-deterministicly, then after the root of our "tree" we would have a number of branches each one of them representing a particular partition of the word. if we have acceptance in one of these branches we're good and i understand that. the problem is that we do not know the length of the word beforehand so we can't know how many branches to put in the machine. $\endgroup$ – lea Jan 18 '14 at 19:51
  • $\begingroup$ @lea: Why don't you just count? $\endgroup$ – Raphael Jan 18 '14 at 20:16
  • $\begingroup$ the thing is i have to make the machine count. and i don t need just the number. i need a process to make the turing machine generate all the possible partitions. $\endgroup$ – lea Jan 18 '14 at 20:20
  • 1
    $\begingroup$ @lea: Can you write a C/Java/... program that does the job? There's really no need to get mentally stuck in the TM formalism. $\endgroup$ – Raphael Jan 18 '14 at 20:22
  • 1
    $\begingroup$ @lea You don't need to know in advance how many branches there will be. You just let the machine run on its input and it produces as many branches as it wants. $\endgroup$ – David Richerby Jan 19 '14 at 14:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.