# Fsm Simulator – Programming Languages

With all of that in mind, let’s encode our finite state machine in Python. Here I’ve redrawn our finite state machine for “a+1+”, and we said before that we were going to make the edges a mapping or a dictionary. Well, one of our edges is at state 1 on ‘a.’ State 1 on input ‘a’ goes to state 2. And another one is at state 2 on ‘a’ stays in state 2. That’s our self-loop. If we were on state 2 and we see a 1, we go to state 3. State 3 on 1 stays the same. Let me just highlight one of these. This particular edge from 2 to 3 on 1 corresponds to this entry in our edges mapping. I also need to know which states are the accepting states. Previously, I denoted that by drawing double lines, but again we can’t pass a picture into Python, so I’ll just make a list of all the things it accepts. Then actually that’s it. You’d think we’d need a list of nodes, but you’re going to see that we’re actually able to finesse it because all the nodes we really care about already appear in this edges listing. So here we are writing our finite state machine simulator, and this is actually super exciting because it previews one of the concepts that we’re going to have later in the course–interpreting another program. It’s like the junior grade version of it, even this will be a lot of fun. So together, we’re going to write a procedure called fsmsim for FSM simulation, finite state machine simulator. You pass in the input string, the start state or the current state, the edges, and the accepting states, and it returns true if that string is accepted by the finite state machine and false otherwise. We’ll do it together. Submit via the interpreter–I’ll write the first half of this procedure with you. So let’s get started on our finite state machine simulation quiz. Here I’m just recopying the edges definition so that we’ll have a test input to work with. These 2–the edges and the accepting state–correspond to the regular expression “a+1+”, and now we’re going to define our procedure, finite state machine simulator given a string, the current state, the edges–these ones up here–and the accepting state. What do we do? Well, one possibility is that we’re already at the end of the input, at which point we should just check to see if our current state is an accepting state or not. If we’re at the end of the input and we are state 3, then we return true. Otherwise, we should be returning false. If the string isn’t empty, then I can get the current letter as the 0th position from the string. And now, here’s your part. We know the current input letter we’re looking at, the current state we’re in, all of the edges are available to us– you fill out the rest of this code. Here’s a hint. Find out if there’s a valid edge leaving from this state on this letter. If there is, you should take that edge and keep walking. If there is not, we fall off the end of the finite state machine and die, so you should return false. And the big hint for you is recursion, which is always the hint in computer science because it’s the secret of all power and knowledge in the universe. Recursion, use it. Oh, and I can’t even spell it! Alright, recursion. You should use it and spell it correctly, unlike me.