Theory of computation: model of computation and Deterministic Finite Automaton
When we talk about Theory of Computation, we talk about the branch of Computer Science that deals with the set of problems that can be solved using an algorithm, providing a model of computation.
When we have a problem, the Theory of Computation permits us to answer questions like:
- Could be the problem solved algorithmically?
- If the answer of the above question is yes, how efficiently can be solved?
- Could exists a precise solution of this problem? Or only an approximative one?
In this post we are going to learn something about automata theory, a subfield of Theory of Computation.
But before going deeper, we need to understand what a model of computation is.
Model of computation
The model of computation is a mathematical abstraction of a computer that permits to describe how is computed the output of a mathematical function and how memories and unit of computations are organized.
We can use the model of computation to analyze the essence of the performance of an algorithm forgetting about variable elements of a specific implementation of it.
A very important model of computation is the Turing Machine. It is a super model that could be seen like an abstraction of all general-purpose computers that we can find around us.
If you are here, I think that you know who is Alan Turing.
If not, have you ever seen the “The Imitation Game” movie? It talks about the story of this guy and how he tried to crack Nazis communication during the Second World War. I think that it is an interesting movie to watch, because it talks about a page of our past that no all of us know.
If you don’t like movie, you can read the book from which the movie is taken.
I propose to consider the question, “Can machines think? “
— Alan Turing, 1950
We are not going to talk about Turing Machine in this article. The theory of computation field is an huge one and Turing Machine is a bit advanced, so it is better to go with the basic first.
Okay, we talked about Theory of Computation. We saw what a model of computation is, and now?
Automata Theory
Automata Theory is the study of the above mention model of computation and of all the problems that we can solve with them.
What automata has in common with model of computation?
Well, a lot of things. An automata is self-operating machine that follows some defined sequence of instruction or rules over an input, automatically.
For a better understanding, think about automata like something that contains an algorithm. We can feed it with some data and it will take these data, execute the algorithm over the data and provides an output.
So, automata is like a program. They are not the same things, but act very similar.
The input can be seen as a list of symbol.
An automaton has a set of states.
One of these states is the starting state, i.e. is the state where the automata is when he starts to process the input.
The input is processed symbol by symbol.
A state contains a set of rules that says how the automata should behave in response to the current symbol input, telling it what is the next state.
The automaton, when it is on a state, looks on the list of rule the one for the actual symbol and jump to the state defined, moving on to the next input symbol.
This is done until all the input is processed.
If the state where the automaton is at the end is an accept state, the automata accepts the input. Otherwise, it rejects it.
The language of an automata is the set of words that it accepts.
If the language of an automata is the set {“hello”, “world”}, if we feed the automata with input “hello”, when it has done processing the input, it will be in an accept state.
Otherwise, if we use the input “three” at the end we are in a non-accept state.
I know it’s a bit messy, but with I think that this non-formal definition helps to better understand the formal ones. I will give you the formal definition of the DFA (deterministic finite automata) in a moment.
Deterministic Finite Automata (DFA)
At the end of the previous section, we talked about states, rules, symbols. Now we provide a formal definition of these things looking at the DFA.
A DFA, or deterministic finite automaton, is a 5-tuple <Q, Σ, δ, q0, F>, where:
- Q is the finite set of states.
- Σ is the alphabet. Is a finite set of symbols.
- δ:Q × Σ → Q is a function, called the transition function (is the above mentioned rule, where given a state and a symbol it returns the next state)
- q0 is the initial state (start state)
- F is a subset of Q whose elements are called accept states.
The transition function tell us what the DFA can do in one step.
If the DFA is in the state r and the current input is the symbol a, the next state is δ(r,a).
Language of a Finite Automaton
The language of a finite automaton M is set of words that it accepts.
Let M=<Q, Σ, δ, q0, F> be a DFA and let w = w1w2. . . wn be a string over Σ.
We can define a sequence of state r0,r1,…,rn such that:
- r0 = q,
- ri+1 = δ(ri , wi+1), for i = 0, 1, . . . , n − 1.
If rn ∈ F, then we say that M accepts w. Otherwise, M rejects w.
The language L(M) accepted by M is defined to be the set of all strings that are accepted by M:
L(M) = {w : w is a string over Σ and M accepts w }.
A language is regular if there exists at least one DFA that accepts it.
Example
Let’s say that we have a language A.
A = {w : w is a binary string containing an odd number of 0s}.
We want to build a DFA M such that L(M)=A.
How we can do? Let’s think about it.
We know that w is a binary string. So the alphabet is Σ={0,1}.
We need to keep track of the number of 0 in the input, that needs to be odd. The DFA read input symbol by symbol, so we can’t just count the 0.
We need at least 2 states: one accepting state, for all the strings with an odd number of 0, and another one for all the other strings (even number of 0, or all the words that doesn’t have a 0)
The initial state (that is not an accept state, because we don’t have already read a 0) could bring us to an accept state only if we read a 0. If we read 1, we can stay on this state.
In the accept state, if we read a 0, we need to move to another state because the number of 0 is not odd anymore.
If we read 1, we can stay in the same state. The number of 0s will not change.
The idea is to switch state only if we read 0.
Intuitively, we can use only 2 state for doing that. Let’s call these state qe and qo.
- we are in qe when the DFA has read an even number of 0s.
- we are in qo when the DFA has read an odd number of 0s.
- the start state, q0, is qe. Initially we have read zero 0, and zero is even.
- the accepting states is F={qo}.
The transition function is defined as:
- δ(qe,0) = qo
- δ(qe,1) = qe
- δ(qo,0) = qe
- δ(qo,1) = qo
And the DFA is finished! We have built a DFA for language A, so we can say that A is regular.
Next steps
This article ends here.
If you like this topic, there are a lot of other things to learn!
