# Automata Basics

Automata Basics – Let’s talk about automata, a kind of abstraction that help you describe and generate strings. Obviously that’s not what these are. The term automaton originally meant a kind of robot or a machine that could perform an action again and again. As you can see on the right there, the first ones were wooden. This is a kind of Pinocchio that spins the wheel again and again and again.

The one on the left is more interesting, this is a karakuri ningyo, a kind of doll from Japan that performs actions in a series of steps. So as you can see, it grabs an arrow, it pulls on the bow, and then it releases and there goes the arrow. It performs a series of actions, grab the arrow, pull on the bow, release the arrow, and it does it in a very strict order.

It is also deterministic in that not only does it do it always in the same order, but it’s gonna be doing it again and again and again for as long as it runs. This is the inspiration for the computational term automaton. What we call an automaton is gonna be an abstraction a kind of abstract machine that goes through different states and where you can go from one to the other by performing an action.

So this is a turnstile, for example, let’s say you have one in front of you. So let’s start up into our interaction with it. You will find it locked. This is the state of the turnstile. You could do several actions: one of the inputs that you can provide to the system is to push it. If you push it, you’re gonna find yourself back in the same state, you’re gonna see that it’s locked and it will remain locked, and if you push it again it will remain locked. You could do a different kind of input: you could put a coin in.

Once you put a coin in, you’re gonna have a transition into a different state. This state is going to be for the turnstile to be unlocked. Once it’s unlocked you can provide the system with two inputs: you can keep putting coins in, we’re just going to transition into keeping it unlocked, or you can push on the bar. When you push you can go through but you also switch the system from the unlocked state to the locked state and then you’re back on that – you’re back on that state.

Here you can again provide the inputs push and coin to go again. Again, an automaton is an abstraction, it has different states, so this has two states locked and unlocked. It has inputs for a coin or push and it has transitions, so if you’re locked and you provide the input coin you go into unlocked. If you are unlocked and you provide input coin, you remain unlocked. So again an automaton has transitions, inputs and states.

A kind of automaton is a finite state machine. This is a sub kind of a automaton. It is a structure with the following elements: it has symbols for inputs into the system, it has states that it can transition in between, so it has different states that the machine can be in, it has transitions between these states, so that there’s an orderly progression in between the states that you want. It has one initial state which is where you find the abstraction of the program as it begins, and it’s going to have a set of final states, so places – ways in which the program can end.

For example this is a finite state machine. The turnstile has an initial state which is for you to find it locked. It has two inputs: put in a coin or push, and it has different transitions, the transition from locked to unlocked which happens with the input coin, the transition from locked to locked which happens with the input push. The transition from unlocked to unlocked which happens with the input coin, and the transition from unlocked to locked which happens with the input push.

So again this finite state machine has states: locked and unlocked. It has inputs: coin and push. And it has transitions in between the states. A light switch is also a kind of finite state machine. You have an initial state, which is for example finding it on, you provide the input, press a button, and then this will transition from the on state to the off state. You’re now in off, so if you want to perform the input button pressed, that is now going to transition you from off to on. As you can see here, you have an initial state, on you have states on and off, you have inputs, in this case just one input, one symbol, the button press, and you have a transition from on to off triggered by the input button pressed and in transition from off to on triggered by the input button pressed.

So far we haven’t mentioned end states. So let’s look at them now. This finite state machine accepts or rejects a string so it has one initial state which is the number one start and it has two end states, number six error and number seven success. So success is going to happen when we recognize the string nice which as you can see is the road from one two three four, and then on to seven. So if we’re in state one, at the initial state, and we get an input that is the letter n, this is going to transition us from state 1 to state 2. If the input is anything that is anything other than an n, this is going to transition us from state 1 to state 6, an error, and then it’s going to reject the string because it is not nice. Once we have the n, we’re on stage two.

When we’re on state 2, we can take the input i and then transition to state three, or anything that is not an i and transition from state two to state six, because if we got an o for example, no, then that string is not nice. We can go from state 3 to state 4 if we get the c so that would be nic, or we could go from 3 to 6 if we get anything that is not a c, and again we get an error.

If we get niece for example then you go 1-2-3 error 6. If you are number 4, you get an e and then you transition from 4 to 7 and ding it checks out. Your finite state machine has accepted the string as being nice. If you get anything that is not an e for example the h and niche, you would go from 1 to 2 to 3, 3 to 4 and then number 4 you get an h for niche and then goes into the state error 6.

So this finite state machine goes into state number 7, which is an end state if it gets the string nice. It goes on to the end state number 6 if it gets any other string like niece or niche for example. Notice by the way that you can only be in each state – you can only be in one state at once at any given time. You can only be in one state and this is true for all the finite state machines that we have seen so far. If you’re in a turnstile, you can only be locked or unlocked you cannot be both states.

If you are a light switch you can only be on or off. You cannot be in more than one state, and here you need to be at a particular stage of the string. You cannot be in two places at once. This is a very simple finite state machine. What do you think the string is? You start at zero, then you get the input c, go to one, input a go to two, input t, go to three, and then end state. And we are going to represent the end states as two circles. This automaton, this finite state machine, represents I’m sorry – accepts the word cat.

Regular expressions and finite state machines are closely related and you can convert one to the other. For example, if you have the regular expression at least one a, and at least one b, you can – you can see that that regular expression will generate a lot of strings. It will generate the string ab where you have at least one a and at least one b. It will also generate abb it will also generate aaaaabbbbbb. Likewise with the finite state machine. If you go to the initial state 0 you can transition from 0 to 1 with an a so you always start with an a, and then to create the first string you would go from 1 to 2, b. So you go from 0 to 1 a 1 to 2 b, and then you’re in an end state, end of the string, and you generate the string ab.

To generate the last one, you would go from 0 to 1, one a, and then you would go through 1 2 3 4 5 times to generate aaaaa, and then you would go from 1 2, one b, and then you would go bbbb four times until you’ve had – you have to string a bbbbb and then you hit the end state.

This one would work like that as well. This regular expression has at least one a, one x, and then at least one b. So you can generate strings like the first one ax – sorry – axb, going from 0 to 1, one a, from 1 to 2 one x, and from 2 to 3, one b, end state. You can also generate more complex strings like the last one axbbbbbbbb. You go from 0 to 1, a from 1 to 2, x, and from 2 to 3 – I’m sorry from 2 to 3, b, and then you cycle in 3 bbbbb as many times as you need to generate axbbbbb. So you can think of both a regular expression and – and a finite state machine as a kind of grammar that generates strings.

Both the regular expression and the finite state machine will generate a series of strings axb axbbbbb and these are all the permissible strings in the language that’s generated, I’m sorry in the grammar that’s generated by these finite state machines. One kind of transition by the way is called an epsilon transition.

An epsilon transition is one where there’s no input symbol consumed and it’s represented by the eps or just by the Greek letter epsilon. So for example in this finite state machine what are the strings that are generated by it? It has – it goes from 0 to 1, c, 1 to 2, a, 2 to 3 t and then – so by then you have the string cat.

When you go from 3 to 4 you have an epsilon which means 0 or nothing, so when you get the 4 you have cat nothing and by the end of four you have cat. If you go from 1 to 3 and then from 3 to 5 you get the s so cats.

So the string that’s generated in the end state 4 is cat, the string that’s generated in the end state 5 is cats. So this finite state machine is a grammar that describes two words, cat and cats. Quick question how do you expand this finite state machine to accept the word dog and dogs so that it’s it accepts four things: cat cats dog and dogs? Let’s look at it. You could have something like this the upper part is what we had before, so if you go 0 1 2 3 4, you would see that it has cat and then epsilon so cat and we reach state 4 and then state 4 we have cat.

If we go 0 1 2 3 5 we have cats, by the time we reach the end state 5 we have cats. So that’s good. Let’s put in dog and dogs. If we go from 0 to 6, we could have a transition that is triggered by the input d if we go from 6 to 7 we can have the symbol o in the transition if we go from 7 to 8 we could have the symbol g, and then we can go from 8 to 9 with another epsilon transition so that when we reach the end state 9 we have dog. We could go from 8 to 10, and have the symbol s, so when we go 0 6 7 8 10, we could generate the string dogs so by the end state 4 you have cat, by the end state 5 you have cats, in end state 9 you have dog, in end state 10 you have dogs.

This is a finite state machine that can describe four words: cat, cats, dog, dogs. In summary an automaton is a kind of abstraction, a kind of machine that goes through things. A – one kind of automaton is a finite state machine which has states, transitions in between the states, inputs that you can provide to trigger the transitions, initial states where you start and final states where you generate an output or where you accept an output – I’m sorry an input. You can only be on one state at any given time and very importantly you can never look backwards if you don’t have an explicit connection going through something you cannot look at what other states contained.

We can use these finite state machines to accept or reject strings, but more interestingly to generate strings. So maybe we could come up with some sort of finite state machine that generates all of the sentences of English. More on this coming up.