Transcript from the "Finite State Machines" Lesson
>> So let's go into a little bit of graph theory. Our applications are structured as graphs, believe it or not. So, a graph is a mathematical concept which is made of nodes and edges. Each node is connected by an edge, or a node might not be connected, but in this graph example, we have four nodes a, b, c, and d.
[00:00:27] And a and b are connected to each other by an edge. So you could consider the edge the way that a and b could move between each other. And so b and c are also connected by an edge as well. B and d, and same with a and d.
[00:00:43] Now this is called an undirected graph because we don't have an arrow. A could go to b, b could go to a. But graphs are a really good visual model for thinking about how your application flows should be structured. Now, directed graphs are a little bit different. We also have nodes and edges, or you'll see in some math textbooks, vertices and edges, but with a direction on the edge.
[00:01:12] So we could have a node a, a node b, and we could say a could go to b, but b can't go to a. And so this is where we get paths. So for example, if we want a to go to c, we could see that we could go from a to b, and then b to c.
[00:01:32] But there's another path we could take too. We go from a to d, and we could also go from d to b, and then from b to c. And so this shows you, hopefully, how you could structure your application flows as a directed graph. For example, your application might have a login screen.
[00:01:53] And then once you've logged in, you might go to an error screen if the login is incorrect, or you might go to the dashboard. So that could be represented as a directed graph where login is a node, error is a node, and dashboard is a node. And then when you log out from the dashboard, you have an arrow going back to login.
[00:02:13] There's three types of nodes in a directed graph. There's a source node, where we have no incoming edges. There's a sink node where we have no outgoing edges. So you can see, once we reach this c node, there's no way that we could exit it. There's nothing going out from c.
[00:02:33] And then all of the other nodes are called transfer nodes. And transfer nodes allow you to go in between nodes. So they have at least one incoming edge and at least one outgoing edge. So if you've ever seen the finite state machine diagram, you might immediately recognize now that finite state machines are directed graphs.
[00:02:57] Finite state machines are considered a quintuple, which means they have five important parts. But before we get into that, I just want you to take a look at this and try to think about how the state machine works. This is a state machine representing a promise, which as a web developer you might be dealing with every day.
[00:03:18] So our first state is idle, and we could see that we have an arrow going from idle to pending on the fetch events. And then pending to resolve or pending to reject, or pending to resolved or pending to rejected. And we see that in this particular graph, we can't go back.
[00:03:37] So we can't go from resolved to pending and we can't go from rejected to pending. So this is sort of our intuition for how the graph works. Let's dissect it and take a look at each of the parts. So the first part of a finite state machine is, of course, the finite states.
[00:03:55] Now, the word states has sort of been using many different ways in programming, but in this case we're going to consider states like a mode or a status. A state is something where you could only exist in one mode or status at a time. For example, I could be sleeping or I could be awake.
[00:04:19] I can't be both sleeping and awake. That's impossible unless you have some sort of medical condition. But let's just consider for ease of thinking that I'm either asleep or awake. I could transition between the asleep state and the awake state, or I could go from the awake state to the asleep state.
[00:04:40] Now, these finite states don't describe what's called extended states such as my name, my age, other things that might be possibly infinite. Not that I could live for an infinite number of years, but one could hope. So there's also transitions. Transitions are how you go between states. So for instance, we have idle to pending, pending to resolved, and pending to rejected.
[00:05:09] Again, this is a directed graph, so you can't go back from pending to idle. There's also events, and events are labels on these edges, these transitions, which tell you how one state could go from that state to another state. For example, in the idle state, we could only go to the pending state when a fetch event happens.
[00:05:35] And so, this is considered the transition between those states. And similarly, from pending we could go to resolved or we could go to rejected depending on which event happens. So, every single state machine starts with an initial state, and there's only ever one initial state. So when you walk up to an ATM or when you turn on your TV, that state is the initial state.
[00:06:05] And it's basically how it starts to work and accept events. So this is why we have what's called a pseudo transition over here, which is a dot with a very small arrow. And that indicates that this is the first or initial state of your state machine. We also have final states, which we're not gonna cover too much in this workshop.
[00:06:27] And final states represents the fact that once you reach these states, your state machine is considered done. It can no longer accept any events and it can no longer transition to any states. In classic finite state machines, these are also known as accepting states. So fun fact, regex or regular expressions are a form of a finite state machine.
[00:06:50] And when you reach the end of a regular expression, that can be considered its final state. And so once you reach the final state, that means that the string which is parsed by the regular expression is accepted, or it's rejected if it doesn't reach one of those final states, but the goal is to reach a final state.
[00:07:11] Now because we're working with web applications, which might have many states and might have continuous user behavior where we don't really have a defined end, we're not gonna be covering final states too much.