Reading

Sections 2.1 of Theory of Computing, A Gentle Introduction. Now we can finally understand their definition of a Deterministic Finite Automaton.

Homework

Printout the homework and answer the questions on that paper.

Functions

So how are we going to represent the transitions in a finite automaton? Well, essentially what you're asking is this: "if I'm in state q and I read character x, what state should I go to?" In other words we want to be able to give a state and a character as input and get a state as output. Hopefully this sounds like a function to you! If Q is the set of states in your machine and Σ is the alphabet, the domain of the function (i.e. the set of possible input values) is Q x Σ (i.e. all pairs whose first component is a state and whose second component is a character). The co-domain of the function (i.e. the set of possible output values) is Q. For our example machine M1, the domain is {(q0,a),(q0,b),(q1,a),(q1,b),(q2,a),(q2,b)}. By convention, this transition function is named δ. The proper mathematical way to indicate the domain and co-domain of a function is to give the domain "→" the co-domain. So for δ we have:

δ: Q x Σ → Q

This plays precisely the same role as a prototype in C++. It tells you what the possible inputs are and what the possible outputs are.

Now for the sake of writing out the 5-tuple representing a machine in as legible a form as possible, I provide a table defining the function δ rather than truly reducing it to a sequence of symbols. This gives us the following definition of M1: \[ M1 = \left( \underbrace{\{q_0,q_1,q_2\}}_{\text{states}}, \underbrace{\{a,b\}}_{\text{alphabet}}, \underbrace{ \begin{array}{c|cc} & a & b\\ \hline q_0 & q_2 & q_1\\ q_1 & q_2 & q_1\\ q_2 & q_1 & q_2 \end{array} }_{\text{transitions}}, \underbrace{q_0}_{\text{start state}}, \underbrace{\{q_0,q_2\}}_{\text{accepting states}} \right) \ \ \ \longleftarrow\text{ 5-tuple representing M1} \]

As we discussed, a table is a common way to describe a function with finite domain. If we really want to represent an automaton as a linear sequence of characters, we can always go back to the OG definition of function and describe $\delta$ as the set of input/output ordered pairs. In this case we would get $\{ ((q_0,a),q_2), ((q_0,b),q_1), ((q_1,a),q_2), ((q_1,b),q_1), ((q_2,a),q_1), ((q_2,b),q_2)\}$. With this we get a complete specification of M1 as a sequence of symbols: \[ (\ \underbrace{\{q_0,q_1,q_2\}}_{Q}, \underbrace{\{a,b\}}_{\Sigma}, \underbrace{\{ ((q_0,a),q_2), ((q_0,b),q_1), ((q_1,a),q_2), ((q_1,b),q_1), ((q_2,a),q_1), ((q_2,b),q_2)\}}_{\delta}, \underbrace{q_0}_{s}, \underbrace{\{q_0,q_2\}}_{W} \ ) \]

For communication between us humans, we will prefer to use a table to represent the transition function.

The payoff: a formal definition of a finite automaton

Here we've been putting a lot of work into getting a representation of a finite automaton as a string of characters, but it turns out we get something more - a formal mathematical definition of what a finite automaton is! (Technically a deterministic finite automaton, we'll look at non-deterministic finite automata later.)

Anything satisfying the requirements of this definition is a finite automaton. With a formal definition like this, we'll be able to give formal proofs (which will generally be algorithms) about properties of finite automata.

Lots of examples!

Here are several examples of machines given as diagrams versus machines given formally as 5-tuples:

({q0,q1},{i,j,k}, | i j k --+--------- q0| q1 q0 q0 q1| q0 q1 q1 ,q0,{q1})
({q0,q1,q2},{a,b,c}, | a b c --+--------- q0| q1 q0 q0 q1| q1 q0 q2 q2| q2 q2 q2 ,q0,{q1,q2})
({q0,q1,q2,q3,q4},{a,b}, | a b --+------ q0| q1 q3 q1| q1 q2 q2| q2 q2 q3| q4 q2 q4| q2 q4 ,q0,{q1,q4})

You're going to need to get comfortable with moving back and forth between the mathematical specification of a machine as a 5-tuple and the diagram of a machine.