You want to recognize a n b n, meaning that you want to recognize some number of "a"'s followed by the same number of "b"'s. Now here's an example of something that you can't do with a FSM because the FSM has limited memory. Non-deterministic with this example would be if your machine can transition from state Q0 either to Q0 or Q1 when it reads an "a". See in this case that the input can be of variable length? You can have only "ab" or an billion a's and b's but your machine still needs only those constant number of states for any given length of input. Meaning that your input indeed corresponds to the pattern "a certain number of a followed by a certain number of b". If you machine remains in the state Q1 and there's nothing to read past the last "b" then you "accept". If your machine sees another "a" after all the "b" it crashes because in this case we haven't created it to recognize anything past the "b"'s. When it will encounter another "b", it moves in Q1 etc. When it encounters a "b", it moves in state Q1. You start in Q0 and whenever your machine reads an "a", it will transition to Q0 (it remains in Q0 but you need to specify that otherwise the machine crashes if it reads an "a"). You can have 2 states, S0 and S1 (or you might see states written as Q0 and Q1). Examples can be: aaabbb, abbbbb, aaaaaaab, etc. Here's an example: you want to create a program that will recognize a certain number of "a" followed by a certain number of "b". See how it's non-deterministic because you can't predict exactly what will happen when the semaphore changes to green? You can either cross the street or not and since I won't know what you'll do, your behavior is not deterministic. In a non-deterministic world, you can either cross the street or just sit there. In a deterministic world when the semaphore changes you MUST cross the street. Real world example: when the semaphore changes to green, you can cross the street. your moves should be deterministic as to know exactly in which state you will end up given an event, you can't end up in two or more because that not/non deterministic). Deterministic means that you can't transition to more than one state from your current state with your current input (i.e. What does limited memory mean? It means that the memory needed shouldn't grow with the input size of your program. It's composed of a set of states and it can transition (move) from one state to another based on an event. Each transition is one of the if statements, and each state, in this analogy, is one possible value of the variable.Ī deterministic finite automaton (or finite state machine) is an abstract description of a machine that can do certain types of computations given limited memory (or constant memory). They're actually not that unlike simple programs, so if you have a decent understanding of programming, it might make more sense to think of them as programs with if-statements that allow you to go to different states (for instance, different values of a variable) based on the input. You keep doing this until you can't anymore - then you're done!ĭFAs underly a significant portion of computer science.
#DETERMINISTIC FINITE STATE AUTOMATA CODE#
So, when you're in a certain place and you have a certain code, you just find the road that is labeled with that code and you follow it, taking you to the next place. There are roads between the different places, and each road is labeled with a code. Every time you're in one of these places, somebody tells you a code - the input. One of these places is your home - that's the start state. Think of DFA (that's short for deterministic finite automaton, and that's how I'm going to refer to them from now on) as a collection of places - these are the states.