Given a single taped deterministic turing machine what's the least amount of calculations needed in order to receive the language $L_k=${$0,1$}$^*0${$0,1$}$^{k-1}$.
My intuition says that i'll need at least $n+k$ calculations.
I will start at the leftmost digit, and go through whole the tape until i reach blank on the rightmost corner of the tape.
Then i'll create {$\sigma_1,...\sigma_{k-1}$} new alphabets in order to the 'count' the digits, Once i'm done using $\sigma_{k-1}$ digits i know i should reach $0$, If i don't i reject.
The solution above has 2 problem:
- Since {$0,1$}$^*$ can be infinite, The machine above will never reach accept state.
- I'm not sure it's the most efficent way.
Help please.
You only need to remember the last $k$ digits in the state. You also have to deal with the states before you get to $k$ digits. Then when you get the the vacant entry on the strip, the process halts, and either succeeds or fails based on the state - which encodes the last $k$ bits. This actually requires a Turing machine with $2^{k+1}$ states, including the final state and the preliminary states.
For example, if $k=2$, you'd have the following states:
$$e,0,1,00,01,10,11,f$$