Prologue
In this series of blog post we are going to learn about Turing Machines, but before that we need to introduce some concepts of the theory of computation. In this part we introduce finite automata.
note
Introduction
Have you ever been asked the question, “What is a computer”?. Well, according to the Oxford Advanced Learner’s dictionary a computer:
Hmm…, that is deep, but I want you to take note of the features, store, organise, find information, and process . By design, the real computers we have around us are complex in a way that we cannot directly set up a mathematical theory for them. Instead, we use computational model which is a form of idealised computer. In understanding the theory of computation we are going to introduce some models of computer depending on depending on the feature of computer we want to focus on.
A simple computer model The simplest of computational model we can have is the finite automaton (plural: automata) , because they are best for computers with extremely limited amount of memory. In fact, there are severaal finite automata systems around us, for exampe an automatic door in a shopping mall.
AIMS main door
To explain how a finite automaton works, I am going to use the mechanism of the main door at the African Institute for Mathematical Sciences (where I’m currently a student btw) as an example.
Every students has a personal token they scan in order to enter or exit the main building, with the way the door is, we can only have two states locked and unlocked . Now, suppose a student Bongo is coming from outside he has to scan his token and push the door to enter an the push from the inside to lock the door again, and this is synonymous to another student Ada exiting the building (but she has to pull the door to get it into it locked state after scanning her token).
Now, we can think of the door to take in three inputs:
And here is the mechanism:
If the door is locked and a token is scanned then state of the door shift from locked to unlocked
If the door is unlocked, no matter the number of time you try to scan a token the door remains unlocked
If the door is locked no matter the push or pull (unless you’re Hulk ), the door remain locked.
If the door is unlocked , it can either be push or pull to shift it to locked state.
Consider the following table
State / Input Push Pull Token LOCKED LOCKED LOCKED UNOCKED UNLOCKED LOCKED LOCKED UNOCKED
And it is also represented in the following figure.
AIMS door machine
Abstract-adabra
Now that, we’ve got a glimpse of how a finite automaton work, it’s high time we formalised the concepts into mathematical theory without a reference to an object.
We are using mathematical symbols as a way to represent machines generally. Imagine we have to write description for every finite automaton system we have, that would be very tedious . Besides we are artist, so we need a unique way to represent our artistic work .
We are using mathematical symbols as a way to represent machines generally. Imagine we have to write description for every finite automaton system we have, that would be very tedious . Besides we are artist, so we need a unique way to represent our artistic work .
Consider the following figure
A simple abstract finite automaton Let the machine in the above picture be M1M 1, we can see it has three states q1,q2,q3q 1,q 2,q 3 wuth different transitions between each states.
note
The state with the double circle is called an accept state.
The arrow from pointing towards q1q 1 is where the input is being passed and it shows that q1q 1 is the start state (i.e where the machine M1M 1 start processing inputs.)
important
The input for our machines are strings which are elements of {0,1}n{0,1}n
Suppose we feed M1M 1 the string 1010110101, then we would have the following sequence of processses:
Start at q1q 1
Read 11 then transition to q2q 2
Read 00 then transition from q2q 2 to q3q 3
Read 11 then transition from q3q 3 to q2q 2
Read 00 then transition from q2q 2 to q3q 3
Read 11 then transition from q3q 3 to q2q 2
Accept, because M1M 1 is in an accept state.
If the processing of an input in a machine stops in the accept state we say that the machine accept the input else we say the machine reject the input. Hence, the output from a machine is either accept or reject .
Now, we give a formal definition for a finite automaton.
note
A finite automaton is a 5-tuple (Q,Σ,δ,q0,F)(Q ,Σ,δ ,q 0,F ), where
Q is a finite set called statesΣΣ is a finite set called the alphabet
δ:Q×Σ⟶Qδ :Q ×Σ⟶Q is the transition function
q0q 0 is the start state
F⊆QF ⊆Q is the set of accept states
Machine $M_1$ In the case of M1M 1, we can write the following
Q={q1,q2,q3}Q ={q 1,q 2,q 3}
Σ={0,1}Σ={0,1}
δδ
note
A machine can have more than one accept state.
In the above automaton, we have the following:
note
Q={q1,q2,q3,q4}
Σ={a,b}
q0=q1q
F={q1,q4}
δδ is given in the table below;
aa bb q1 q1 q2 q2 q3 q4 q3 q2 q1 q4 q3 q4
We see that thsi machine accepts any inputs such as a , aa , bbb , abbbab, and some other input strings you can think of. If we represent the collection of strings a machine MM accepts as AA then we say that AA M$ and it is represented asA=L(M)A =L (M )
and we say MM accepts AA or MM recognises AA .
warning
A machine may accepts several string, but it always recognises only one laknguage.
If the machine accepts no strings, it still recognises one language (the empty language.)
If you note from the last example we gave from above, the state q1q 1 which is the start state is also an accept state. In this case, we can feed our machine the empty string (denoted εε ).
If the processing of an input in a machine stops in the accept state we say that the machine accept the input else we say the machine reject the input. Hence, the output from a machine is either accept or reject .
note
It is not possible to represent every finite automaton with state diagram and that is the reason for the formal definition.
If the processing of an input in a machine stops in the accept state we say that the machine accept the input else we say the machine reject the input. Hence, the output from a machine is either accept or reject .
If M=(Q,Σ,δ,q0,F)M =(Q ,Σ,δ ,q 0,F ) and w=w1w2…wnw =w 1w 2…w n are finite automaton and string respectively, with wi∈Σw i ∈Σ. We say that MM accepts ww if ∃∃ a sequence of states r0,r1,…,rn∈Qr 0,r 1,…,r n ∈Q such that
r 0=q 0δ(ri,wi+1)=ri+1∀i
rn∈F
Bonus
Here is a simple class in C++ representing a finite automaton, directly from the formal definition.
C++ #include <functional> #include <unordered_set> template < typename T > struct FiniteAutomaton { FiniteAutomaton ( std :: unordered_set < T > states , std :: unordered_set < T > alphabet , T start_state , std :: unordered_set < T > accept_states , std :: function < T ( T , T )> transition ) { this -> states = states; this -> start_state = start_state; this -> transition = transition; this -> alphabet = alphabet, this -> accept_states = accept_states; } const std :: unordered_set < T > & getStates () const { return states; } const std :: unordered_set < T > & getAlphabet () const { return alphabet; } const T & getStartState () const { return start_state; } const std :: unordered_set < T > & getAcceptStates () const { return accept_states; } private: std ::function< T (T, T)> transition; std ::unordered_set<T> states; std ::unordered_set<T> alphabet; T start_state; std ::unordered_set<T> accept_states; };
