Finite Automata | Theory of Computation - Computer Science Engineering (CSE) PDF Download

Part II. Finite Automata

Different classes of automata are there. examples: finite automata, pushdown automata. Of them finite automata is the simplest one.In Module I, during the discussion of chomsky classification, it was seen that type-3 or regular languages are recognised using finite automata.

Definition
A finite automation, M is a 5 tuple structure,
M ( Q, ∑, q₀, δ, F )
where M is the finite automation,
Q is a finite set of states,
∑ is a set of input symbols,
q0 is the start state,
δ is the set of transition functions,
F is the set of final states.
Consider the following example for a finite automation, M.

In the above finite automation, M,
1. Q = {q₀, q₁, q₂, q₃, q4}
Q is the set of states in the finite automata. In the above finite automata, q₀, q₁, q₂, q₃, q₄ are the states. The states are shown in circles.
            

2. ∑ = a, b, c
        ∑ is the set of input symbols in the finite automata. In the above, a, b, c are the input symbols. The arrowsare labelled with input symbols.
              

3. q₀ = {q₀}
       q₀ is the start state. In the above, q₀ is the start state. For our study, a finite automata contains only one start state. A state with arrow from free space (not coming from any other state) is designated as start state.
              

4. δ describes the operation of finite automation. δ is the transition function.
For example,
      δ(q₀, a) = q₁
This means, given the current state q0 and the input symbol, a, the finite automation moves (transits) to state q1.
Similarly,
δ(q₁, b) = q₂
δ(q₂, c) = q₃
δ(q₁, c) = q₄
δ(q₃, b) = q₄

5. F = {q₂, q₄}
F is the set of final states or accepting states. In the above finite automation, q and q₄ are the final states. They are shown enclosed in double circles.

Transition Diagrams and Transition Tables
Consider the following finite automation, M.

The above representation of finite automation is called a transition diagram. A finite automata can also be represented as a transition table.This is shown below:

→ q₀ denotes that q₀ is the start state.
∗ before q₂ and q₄ indicates that q₂ and q₄ are the final states.

3 Language Acceptibility by Finite Automata

String Processing by Finite Automation
Example 1:
Consider the following finite automation, M.

Check whether the string abcb is accepted by the above finite automation.

In the above, q₀ is the start state. the string abcb has the first symbol, a.
So,
δ(q₀, abcb) = q₁
δ(q₁, abcb) = q₂
δ(q₂, abcb) = q₃
δ(q₃, abcb) = q₄
Thus,

Thus, after processing the string abcb, we reached the state, q4. Here q4 is a final state. So the string abcb is accepted by the finite automation.

Example 2:
Consider the following finite automation, M

Check whether the string abc is accepted by M.
On processing the string, beginning from the start state, q0,
δ(q₀, abc) = q₁
δ(q₁, abc) = q₂              
δ(q₂, abc) = q₃
Here M halts at q₃. But q₃ is not a final state. Hence the string abc is rejected by the above finite automation, M.

Example 3:
Conisder the finite automation, M,

Check whether the string abca is accepted by the finite automation, M.
Beginning from the start state, q0,
δ(q₀, abca) = q₁
δ(q₁, abca) = q₂
δ(q₂, abca) = q₃
δ(q₃, abca) =
Here for current state, q₃, and for input symbol, a, there is no transition. This means M is unable to process the string abca completely. So the string abca is rejected by M.

Language of Finite Automation
In the above, finite automation is used to check the validity of a string. A language is a finite set of strings. So we can use
finite automation to check whether a string belongs to a language.
Consider the following finite automation,

Let L be the language corresponding to the above finite automation, M. Then a string belongs to the language L only if it is accepted by the finite automation, M.
We can say that,
The string abcb belongs to the language, L.
The string abc does not belong to the language, L.
The string abca does not belong to the language, L.
The string ab belongs to the language, L.
The string ac belongs to the language, L.
The string abcbc does not belong to the language , L.

4 Types of Finite Automata
Finite automation is of different types. They are,
Non-deterministic Finite Automata (NFA), and
Deterministic Finite Automata (DFA).

4.1 Non- Deterministic Finite Automata (NFA)
Consider the following finite automation, M,

In the above, from state q₀ with input symbol 0, there are two possible next states. The next state can be either q₀ or q₁.
Also from state q₁, on input symbol, 1, there are two possible next states. The next state can be either q₁or q₂.
Thus some moves of the finite automation cannot be detrmined uniquely by the input symbol and the current state.
Such finite automation are called Non-deterministic Finite automata (NFA or NDFA).

Example 1:
Consider the following NFA,

Check whether the string 0100 is accepted by the above NFA.
Beginning from the start symbol, q₀,
δ(q₀, 0100) = q₀
δ(q₀, 0100) = q₀
δ(q₀, 0100) = q₃
δ(q₃, 0100) = q₄
q₄ is a final state. So the string 0100 is accepted by the above finite automation.

Example 2:
Consider the following NFA,

Check whether the string 01101 is accepted by the above NFA.
δ(q₀, 01101) = q₀
δ(q₀, 01101) = q₀
δ(q₀, 01101) = q₀
δ(q₀, 01101) = q₁
δ(q1, 01101) = q₂
q2 is a final state. So the string 01101 is accepted by the above NFA.

Example 3:

Check whether the string abbaa is accepted by the above NFA.
δ(q₀, abbaa) = q₀
δ(q₀, abbaa) = q₀
δ(q₀, abbaa) = q₁
δ(q₁, abbaa) = q₂
δ(q₁, abbaa) = q_f
q_f is a final state. So the string abbaa is accepted by the above NFA.

4.1.1 NFA with Epsilon Transitions

An NFA can contain certain transitions on input symbol, ε (epsilon).
ε means ’null’.
For example, consider the following NFA,

Check whether the string 100110 is accepted by the above NFA.

δ(q₀, 100110) = q₀
δ(q₀, 100110) =q₀
δ(q₀, 100110) = q₀
δ(q₀, 100110) = q₁
δ(q₁, 100110) = q₂
δ(q₂, 100110) = q₂
δ(q₂, ε) = q₄
q4 is a final state. So the string 100110 is accepted by the above NFA.
Here note that, we made an ε move to reach the final state, q₄.
Thus, ε transition means a transition without scanning the symbol in the input string.

Example 2:
Consider the following NFA,

Check whether the string 0012 is accepted by the above NFA.
Beginning with the start state, q0,
δ(q₀, 0012) = q₀
δ(q₀, 0012) = q₀
δ(q₀, ε) = q₁
δ(q₁, 0012) = q₁
δ(q₁, ε) = q₂
δ(q₂, 0012) = q₂
Here q₂ is a final state. So the string 0012 is accepted by the NFA.

4.2 Deterministic Finite Automata
Consider the following finite automation,

In the above, input symbols are 0, 1 and 2. From every state, there is only one transition for an input symbol.
From state, q₀, for symbol, 0, there is only one transition, that is to state q₀ itself.
From state, q₀, for symbol, 1, there is only one transition, that is to state q₁.
From state, q₁, for symbol, 1, there is only one transition, that is to state q₃, and so on.
Thus all the moves of the above finite automation can be determined uniquely by the current state and input symbol.
Such a finite automation is called Deterministic finite Automation (DFA).
Thus in a DFA, at every step, next move is uniquely determined. No ε transitions are present in a DFA.

Example 1:
The following shows a DFA,

Above transition diagram can be represented using the transition table as follows:

Check whether the string aaba is accepted by the above DFA.
Beginning from the start state, q0,
δ(q₀, aaba) = q₀
δ(q₀, aaba) = q₀
δ(q₀, aaba) = q₁
δ(q₁, aaba) = q₁
After processing all the characters in the input string, final state q₁ is reached. So the string aaba is accepted by the above finite automation.

Example 2:
Consider the following DFA,

Check whether the string aabba is accepted by the above DFA.
δ(q₀, aabba) = q₀
δ(q₀, aabba) = q₀
δ(q₀, aabba) = q₁
δ(q₁, aabba) = q₀
δ(q₀, aabba) = q₀
After processing all the symbols in the input string, aabba, the state q₀ is reached. But q₀ is not a final state. So the DFA rejects the string aabba.