State Machine Logic Gates
I’ve been using XState recently to simplify my complex React components. Using state charts is a delight to use for frontend apps. I began thinking about how a state machine’s mechanical nature remind me of switches, and how transistors are like switches, and how logic gates are built from these switches — could logic gates be modelled using state machines? After spending some time drawing state machine diagrams and stepping through the transitions I found that they can indeed be modelled.
A Switch
Possibly the most simple type of state machine is a switch. A switch has two states — ‘on’ or ‘off’. When you flip the switch you cause a transition between the two states. If a light is ‘on’ and then you flip the switch then light will transition to ‘off’, and visa-versa. The flipping of the switch is called an ‘event’ which causes a transition.
We could think of a transistor as a similar type of switch. Instead of the ‘flip’ event we could consider a voltage event in the form of ‘high’ and ‘low’. The ‘high’ event represents the voltage level above the gate threshold, and ‘low’ as the voltage below gate threshold. If the transistor is in the ‘off’ state and then there’s a ‘high’ voltage event then the transistor will transition into the ‘on’ state. If there’s another ‘high’ event then the ‘on’ state will transition back onto itself. The polar logic applies.
NOT Gate
The NOT gate is similar to the model of the transistor above, except the states are flipped. If the voltage is ‘high’ (which I’ll now refer to as ‘1’) then the gate will be in an ‘off’ state. If voltage ‘low’ (‘0’ from now on) then gate is ‘on’.
AND Gate
The following logic gates have two inputs and one output. The inputs will be a sequence of events (‘0’ or ‘1’) and the output is the state of the gate (‘on’ or ‘off’ — or in digital terms ‘1’ or ‘0’). The input events are sequential — they effect the state machine one event at a time. Unlike real logic gates that receive inputs in parallel, we must feed the inputs in series. Because of this the state machine must have two extra intermediate states, which I’ll simply call ‘x’ and ‘y’.
The most simple input series to look at is ‘1,1’. If we begin in the ‘off’ state then receive a ‘1’ event then we transition to the ‘x’ state. If the ‘x’ state receives a ‘1’ event then we transition to the ‘on’ state which is the final state of the series. If we start the ‘1,1’ series again then the ‘on’ state will transition into the ‘x’ state again from the ‘1’ event. Then just like before when ‘x’ receives a ‘1’ event we’ll transition back to the ‘on’ state.
Another interesting input series is ‘0,0’. The ‘off’ state will transition to ‘y’ on the ‘0’ event. No matter what event occurs next ‘y’ will always transition back to ‘off’. So inevitably another ‘0’ will transition into ‘off’. If ‘on’ state receives a ‘0’ then we transition to ‘y’ which inevitably finalises in the ‘off’ state.
As the events and transitions are binomial we could model the series as a binomial tree. Notice the only series that terminates at ‘on’ is ‘1,1’.
OR Gate
NAND Gate
XOR Gate
Analysis Of The Machines
From the ‘off’ state the ‘1’ event always transitions to state ‘x’ and event ‘0’ always transitions to state ‘y’. This branching simply puts the second event in the series into the context of the first event. The same is true in the opposite direction — from the ‘on’ state the ‘1’ event will always transition to ‘x’ and event ‘0’ will always transition to state ‘y’. Again, this is to put the second event into the context of the first event. Given this symmetrical topology is invariant— what are the variant transitions between them?
The NAND and XOR gates have mirrored topology. Logically they are an inverse of each other. While NAND is ‘on’ for inputs that are identical, XOR is ‘on’ for inputs that are different.
The difference between the AND & NAND is quite minimal. The ‘0’ event is carried from the AND (‘y’ > ‘off’) transition to the NAND (‘y’ > ‘on’) transition. This is because there is only 1 of 4 conditions where AND is ‘on’ — ‘1,1’. So therefore there’s only one transition that terminates at the ‘on’ state. NAND has two conditions where its ‘on’, which requires a second ‘0’ event after the first ‘0’ event.
A similar story is true for OR & XOR. The difference between AND/NAND & OR/XOR is that the carry is an inverse digit and the direction of the carry is mirrored both horizontally and vertically on the diagram. The symmetry in logic is pleasing :)
Thanks
I’d like to do more articles on state machines. I could take this idea further and build electrical logic circuits such as a half-adder, flip-flops, etc.
I’d really recommend checking out XState. I used it for all the above simulations.
Cheers all :)
