Computation - Finite State Automaton (part 2)

Finite State Automata

OK, so that last part was only introducing you to the idea of using automata for expressing patterns in a better, and more meaningful way. However, it is now time to take this to a new and more formal level.

Before we can even think about drawing an automaton, we must know one thing! That is of course the alphabet, Σ. As without an alphabet, an automaton would be pretty darned meaningless!

The Sets of an Automaton

Now then, let’s take a more, in depth look at what really makes up an automaton. First of all – and most importantly! – We have the states, these states themselves actually form a set, namely the set of all states that make up an automaton. We give this set a name: Q.

Next we have the state that you must start in – I hope you didn’t forget about the poor lil fella? Any way, this start is called the start state, and as guessed, it also has a name! We call this state q•.

So, how do we know when we accept a word? That’s right, the accepting states. So we call these set of states: F.

Note: q• and F are subsets of Q.

Now for a trickier part. What about the edges in the automaton? What this requires, is if we are in some state, and are given some letter from Σ, then we require precisely one edge labelled with that letter. So with this, the edge could take us to a new state, or even back to the same state – so a looping edge.

So, with this, we could describe this procedure as a function. This function would take as input a state and a letter, and then outputs a new (or the same) state. This function is called the transition function, and is denoted by δ (delta). Here we have a pair of inputs – the state and a letter:

• (q, x)   where   q Є Q and    x Є Σ

This means that the inputs come from the sets:

• Q x Σ = {(q, x) | q Є Q , x Є Σ}

And now for the functions output, which is also a state. This means we have:

• δ : Q x Σ ----------> Q

This function is probably best described with a table showing the input, and then the output. Lets take the example from the previous part 1 with the EVEN and ODD (E, O) states.

Input	Output
δ(E, 1)	E
δ(E, 0)	O
δ(O, 1)	O
δ(O, 0)	E

NOW! We can have another definition! :)

———————————————————————————————–

Definition 8: Let Σ be a finite alphabet of symbols. Then we can say that a deterministic finite automaton (DFA) can consist of:

• A finite non-empty set Q of states.


• A start state q•, which is a subset of Q.


• A set of accepting states, F, which is also a subset of Q.


• A transition function δ, which takes as input a state and letter, and outputs the next required state to move to.

We can also put all 4 together to obtain: (Q, q• , F, δ).

———————————————————————————————–

This type of automaton is called deterministic, because for every word, the path defined by the automaton is completely determined.

———————————————————————————————–

Definition 9: A word over a given alphabet is accepted by a DFA if:

• δ(q•, x1) = q1


• δ(q1, x2) = q2


• δ(qn-1, xn) = qn


• The word is accepted if qn Є F.

———————————————————————————————–

———————————————————————————————–

Definition 10: We say that a language is recognized by a finite automaton if it is the set of all words accepted by the automaton.

———————————————————————————————–

Next: NFAs! Darn this section takes forever.. its so looong.. stupid automaton :(

Notes: sorry there was no pretty pictures… I guarantee there is in NFAs!