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.

Continue reading Simple Deterministic Push Down Automata in Kotlin →

I wanted to learn more about Kotlin, so I implemented a simple finite state machine. In this implementation, if an invalid event is passed to the state machine, then it goes into an “error” state, but we never check for the error state soooo… that’s helpful. Also, a current state and an event can be associated with a particular action. Figuring out how to trigger this action led me to use the invoke() method, of which I was previously unaware. In a more realistic implementation we’d probably want a pre-transition action, and a post-transition action.

Continue reading Simple Finite State Machine in Kotlin →