Turing Machine for 0*1*

Turing machine for zero star one star

This Turing machine accepts binary strings in the language 01: any number of zeroes followed by any number of ones. It begins in qZeroes and moves right across every zero. When it sees a one, it moves to qOnes, which continues right over one symbols. A blank B at the end of the tape causes acceptance from either state, so the empty string and an all-zero string are included. A zero seen after qOnes would have no valid transition, indicating that the input is outside the language. The example is deliberately compact so the role of each state is easy to read from the diagram.

種類 状態遷移図規格 OMG UML 2.5.1 §14 + Harel (1987) statechartエンジン schematex-state更新日 2026/9/24

依頼内容

“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.”

次はこちらAdd an explicit reject state for a 0 read in qOnes.Change the alphabet from 0 and 1 to a and b.

この図に含まれるもの

図の背後にある意思決定を読み解く。

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.

状態遷移図のテンプレートをすべて見る →

よくある質問

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.