The theory of computation begins with a question: "What is a computer?"

It is perhaps a silly question, as we can all recognise that the things we use are computers. But they are too complicated to manage in mathematical theory, so instead we use an idealized computer called a computational model. There are different types of computational models. We will start with the most simple. A Finite Automaton.

⚛ What is a State Automaton?

Finite automata are good models with extremely limited amount of memory. What can computers do with very limited memory? All sorts of useful things!

In fact, we interact with such simple computers all the time as they lye in electromechanically devices we use.

Example: The following depicts an automatic door controller.

The controller is in either of the two states "OPEN" or "CLOSED", representing the states of the door.

There are four possible conditions in the system:

• FRONT (meaning that one person is standing on the pad in front of the doorway, but not on the rear pad

• REAR (meaning that one person is standing at the rear of the pad, but not the front).

• BOTH (meaning one or more people are standing on both pads)

• NEITHER (meaning no one is standing on either pad)

The controller is moving from one state to another depending on the input it receives.

When in CLOSED state..

and it receives input NEITHER or REAR, it remains closed. It also stays CLOSED if BOTH pads have people, otherwise it is deemed too dangerous.

It can moved from CLOSED to OPEN if FRONT is received.

When in OPEN state..

and it receives input FRONT, REAR, BOTH, it remains open. However if is in OPEN state, and receives NEITHER, then it is deemed safe to open.

Thinking of the automatic door as a finite state automaton is useful because it is a standard way of representing this system.

See the picture below:

As you can see, these changes of "states" are represented by the diagram. This diagram is called a State Diagram.

The nodes (circles) represent the states and the arrows going from one state to another are called transitions.

⚛ What are the parts of a State Automaton?

The following is an abstract example of a state automaton without any specific application.

We will call this Finite State Automaton M1.

This diagram above is called the State Diagram of M1. It has three states labelled q1, q2, and q3. The start state is q1, as indicated by the arrow pointing to it from nowhere. The accept state is q2 as indicated by the double circle. The arrows going from one state to another are called transitions.

When this automaton receives an input string, such as 1101, it processes that string and produces an output. The output is either accept or reject.

The processing starts at M1's the start state. The automaton receives the symbols from the input string one by one from left to right. After reading each symbol, M1 moves from one state to another along the transition that has the symbol as it's label. When it reads the last symbol, M1 produces its output. The output is accept if M1 is now in an accept state (state with double circle) otherwise reject if not.

For example, if we feed the input string 1101 into the machine M1, the following steps occur:

1. starts in state q1

2. read 1, follow transition from q1 to q2

3. read 1, follow transition from state q2 to q2

4. read 0, follow transition from q2 to q3

5. read 1, follow transition from q3 to q2

6. accept, because M1 is in an accept state q2 at the end of the input

Symbols

These symbols may be handy for the following section. You can however ignore these symbols as they are not needed for NCEA. You may want to refer back to these notes for University however.

Q stands for the set of states

δ delta means transitions (more formally transition functions).

ε epsilon means "empty string"

∈ means "is a member of".

⊆ means "is a subset of".

⚛Formal definition of a State Automaton

So far we have used state diagrams to introduce finite automata. We will now introduce finite automaton formally.

Firstly, a formal definition is precise. It resolves any uncertainties about what is allowed in the automaton.

NOTE: interestingly a finite state automaton is actually allowed to have zero accept states, and exactly one transition exiting a state for each input type (note, this is true for Deterministic State Automaton, where the path is certain, but we cover Non-Deterministic State Automaton later..).

Secondly, a formal definition provides notation. Good notation helps to communicate thoughts and designs clearly.

A finite automaton has several parts.

1. It has a finite set of states (denoted Q).

2. It has an input alphabet that indicates the allowed input symbols. (This is also a finite set denoted Σ).

3. It has rules for going from one state to another, depending on the input symbol. These are called transition functions.
   For example:

So, for instance, if the given state is q1 it can stay at q1 with input 1, or move to q2 with input 1. And so on..

4. It has a start state (denoted q0). q0 is a member of the states (q0 ∈ Q) - NOTE: where ∈ means "is a member of".

5. It has a set of accept states. (accept states are a subset of all states F ⊆ Q) - NOTE: where ⊆ means "is a subset of".

A formal definition says that a finite state automaton is a list of those 5 objects.

Example ~ Formal Definition of a Finite State Automaton

So remember, we need to define the 5 elements to a Finite State Automaton. 1. The set of states, 2. The alphabet, 3. The possible transitions, 4. The start state, and 5. The set of Final states.

Here is an example of a formal definition of a Finite State Automaton (FSA):

1. set of states = {q1, q2, q3}

2. set of alphabet = {0, 1}

3. transitions are :

So, q1 can go to q1 with input 0. q1 can go to q2 with input 1, and so on.

4. Start state is q1

5. Set of final states is {q2}