Library

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.

startopenafterclosedneeddone
The machine as drawn — 6 states, 10 transitions.

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