Fsm Simulator Solution – Programming Languages

Fsm Simulator Solution – Programming Languages


Alright, let’s go through a possible answer together. To see if there’s an outgoing edge, we’ll just check to see if the tuple (current, letter) is in edges. If so, our destination state can be obtained by just looking up the tuple (current, letter) in edges. We’ve already processed letter, the 0th element of string, so we want to peel off the 0th character, retaining only the rest of them. For example, if the input was “aaa111”, we’ve used the “a”, so now we want it to be just “aa111”. Now we just call ourselves recursively, call finite state machine simulation on the remaining string, starting from the destination node, and the edges and accepting states are unchanged. Otherwise, we fall off the finite state machine and return false. Alright. The moment of truth. We want to print out this answer. Oh! Just as we expected, “aaa111” is accepted by this string. What if I try to mix it up and make it something like “a1a1a1”? This should not be accepted by our finite state machine, and it is not. The output changes to false. How about the empty string? Is that accepted? It’s not because we’re looking for “a+1+” so this should also be false. And it is, but how about the smallest string we do accept, “a1”? That one is accepted. Great! So we can check any finite state machine to see if it accepts a string. You may have noticed as we were going through it, that edges and accepting never change. I defined them once at the beginning of the file. So our finite state machine simulator is really just recursive in the input and the current state, and that matches our intuition because those are the 2 fingers I was using to work it out on paper.

Leave a Reply

Your email address will not be published. Required fields are marked *