By now we should have an okay understanding
of Finite State Automata, what they’re used for and how to read them.
Let’s try to create our own. First up, we need to define
what we want this automaton to achieve. Let’s go with this: This automaton is to accept any string of ‘A’s and ‘B’s
that has no more than two ‘B’s in a row. Okay, we have our definition,
now let’s break it up to understand what it means: “Any string of ‘A’s and ‘B’s.” This tells us that in our alphabet
we have two transition types, ‘A’ and ‘B’. “Accept… no more than two ‘B’s in a row.”
This tells us that our language, or the set of strings our automaton will accept,
is all strings with at most zero, one or two ‘B’s in a row. So let’s begin our diagram. A good starting point is the start state,
a circle with an arrow into it. Let’s call this state ‘0’. That’s great, what else can we do? Well, let’s look at what we expect
to happen if we give the automaton nothing. A string containing zero ‘A’s and zero ‘B’s. That may seem a bit odd but an empty string,
denoted asepsilonor sometimeslambda, is very useful for understanding
how our automaton works. So, we put in nothing.
There are at most zero ‘B’s in a row in our string. Zero ‘B’s is obviously fewer than three ‘B’s,
so the string is accepted. This means that our first state
is also an accepting state. Let’s give it another circle to show this.