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.

Typ ZustandsdiagrammStandard OMG UML 2.5.1 §14 + Harel (1987) statechartEngine schematex-stateAktualisiert 24.9.2026

Die Anfrage

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

Dann probieren SieAdd an explicit reject state for an unmatched a.Change the marker symbols from X and Y to 0 and 1.

Was diese Zeichnung zeigt

Die dahinterstehenden Entscheidungen verstehen.

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.

Alle Zustandsdiagramm-Vorlagen durchsuchen →

FAQ

Häufige Fragen

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.