DPDA · Deterministic context-free
A nested list: [x;[x;x];[]]
The bones of JSON’s arrays: a list is brackets around items separated by semicolons, and an item is an atom x or another list. The control knows only whether an item or a separator comes next; the stack knows how deep the brackets go, so the machine can tell when the outermost list has closed.
The author’s examples, run
[] → accept[x] → accept[x;x] → accept[x;[x;x];[]] → accept[[[]]] → accept[x;] → reject[x → rejectx → reject[];[] → reject[[x]x] → reject