This was another programming exercise to get more comfortable with Kotlin. A deterministic push down automaton (DPDA) is basically a finite state machine with a stack for memory. Since finite state machines (FSM) generally use their states as memory, this allows you to have fewer states in your model. The downside is that you will have more numerous and complex state transitions. Whereas with a finite state machine you consider the current state and a new event to determine the next state, with a push down automaton you need to consider the current state, the incoming event, and the top of the stack before determining the next state and the next action to perform on the stack, either pushing a symbol, popping one off, or doing nothing.

Below, I wrote a DPDA for determining whether a sequence of parentheses were closed properly or not. If the parentheses all have closing pairs, then when the DPDA reaches the semicolon at the end, it will be in the “halt” state, otherwise it will be in the “error” state. The thing to notice here is that I only have three states, “initial”, “halt”, and “error”, but this state machine can handle an arbitrarily long sequence of parentheses, given enough memory.