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.