Library

DFA · Regular

Well-formed UTF-8

Each symbol is a byte class: a for an ASCII byte (0xxxxxxx), c for a continuation byte (10xxxxxx), and 2, 3, 4 for the lead byte of a two-, three- or four-byte character. The DFA counts how many continuation bytes are still owed — the core of every UTF-8 decoder, before the finer rules on overlong forms.

okowe1owe2owe3a234ccc
The machine as drawn — 4 states, 7 transitions.Every word up to length 3, one row per length in shortlex order, inked where it is accepted.

The author’s examples, run

ε → accept2ca → acceptaa3cc → acceptaaaaa → acceptc → rejectaca → rejectca3cc → rejectcaaaa → reject

Essay

2 min read · 1 figure

UTF-8 is how almost all text on the web is stored. It writes each character as one to four bytes, and its design makes those bytes easy to check with a very small automaton. This machine is that check, at the level of byte classes.

The encoding

Every byte belongs to one of a few classes, told apart by its leading bits:

Byte Bits Meaning Symbol here
ASCII 0xxxxxxx a whole character a
continuation 10xxxxxx the middle or end of a character c
two-byte lead 110xxxxx starts a character of 2 bytes 2
three-byte lead 1110xxxx starts a character of 3 bytes 3
four-byte lead 11110xxx starts a character of 4 bytes 4

A lead byte announces how many continuation bytes follow, and the DFA’s state is just the number still owed — 0, 1, 2 or 3. A continuation byte when none is owed, or anything else when one is, has no edge.

okowe1owe2owe3a234ccc
Figure 1. The whole decoder: count down the continuation bytes a lead byte promised.

Why it was designed this way

Ken Thompson designed UTF-8 with Rob Pike in September 1992, famously sketching it on a placemat in a New Jersey diner. Its properties are visible in the machine:

  • ASCII is unchanged. The ASCII edge is a self-loop on the accepting state, so a plain-ASCII file is valid UTF-8 as it stands.
  • It is self-synchronising. Continuation bytes can never be mistaken for the start of a character, so a reader dropped into the middle of a text can skip forward to the next non-continuation byte and resume — a property older multi-byte encodings lacked.
  • Errors are local. A corrupt byte breaks one character, not the rest of the text.
What this machine leaves out

Real validators also reject overlong encodings (writing a character in more bytes than needed), the surrogate range and values above U+10FFFF. Those rules depend on the exact bit values of the first continuation byte, so a full validator splits some of these classes and has a few more states. Björn Höhrmann’s well-known decoder is a DFA of that kind, run as a lookup table.