Turing Machine for a^n b^n

Turing machine for a to the n b to the n

This Turing machine recognizes strings formed by n copies of a followed by n copies of b. It repeatedly finds the leftmost unmarked a, changes it to X, moves right to find an unmarked b and changes that symbol to Y. It then returns left to begin the next pair. Once no a remains, qCheck scans the marked b symbols and accepts only when it reaches the blank at the end of the tape. The X and Y markers are the machine's working memory: they let it remember which symbols have already been paired. This is a standard example of why Turing machines can recognize languages that finite automata cannot.

유형 상태 다이어그램표준 OMG UML 2.5.1 §14 + Harel (1987) statechart엔진 schematex-state업데이트됨 2026. 9. 24.

요청 내용

“Draw a Turing machine for a^n b^n that marks each leftmost unmarked a as X, scans right to mark one matching b as Y, returns left to repeat, then checks that only Y symbols remain before accepting on blank.”

그렇다면Add an explicit reject state for an unmatched a.Change the marker symbols from X and Y to 0 and 1.

이 도면에 담긴 내용

그 이면의 의사결정을 읽어 보세요.

01First marker

qFindA selects one unmarked a at a time.

02Paired marker

qFindB changes one corresponding b to Y.

03Completion check

qCheck accepts only after the remaining b block has all been marked.

Use a marking-and-return machine to recognize a non-regular language that requires matching counts.

모든 상태 다이어그램 템플릿 보기 →

자주 묻는 질문

What language is being recognized?

Strings with the same number of a symbols followed by b symbols, such as ab, aabb and aaabbb.

Why are X and Y needed?

They mark symbols already paired, preventing the machine from counting the same a or b twice.

Why is this not a finite automaton task?

The machine must compare an unbounded number of a and b symbols, which requires more memory than finite states provide.