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.