The request
“Draw a Turing machine that accepts strings in 0*1*: qZeroes moves right over zeroes, changes to qOnes on the first one, qOnes moves right over ones, and either state accepts on blank B.”
Then tryAdd an explicit reject state for a 0 read in qOnes.Change the alphabet from 0 and 1 to a and b.
What is in this drawing
Read the decisions behind it.
01Zero phase
qZeroes permits any initial run of zeroes.
02One phase
qOnes records that the first one has been seen.
03Blank acceptance
either an all-zero input or a completed one run can halt successfully.
Use this small machine to explain states, tape scanning and language phases before introducing more complex Turing machines.
More like this
Other examples in this family.
FAQ
Common questions
What does 0*1* mean?
It means zero or more 0 symbols followed by zero or more 1 symbols.
Is 00111 accepted?
Yes. All zeroes occur before all ones.
Is 010 accepted?
No. A zero after entering qOnes violates the required order.