Library

DFA · Regular

Decoding a prefix code

The codewords are 0, 10, 110 and 111 — no one a prefix of another, as a Huffman code guarantees. The DFA is the code tree with every leaf glued back to the root: it accepts a bit string exactly when it splits into whole codewords, and each return to the root is one decoded letter.

rootn1n1101010, 1
The machine as drawn — 3 states, 6 transitions.Every word up to length 8, one row per length in shortlex order, inked where it is accepted.

The author’s examples, run

ε → accept00110 → accept0 → accept0000000110 → accept1 → reject0011 → reject01 → reject000000011 → reject