DFA : definition, representations, application ( Deterministic Finite Automata )

Deterministic Finite Automata:

The first type of finite automata is named Deterministic Finite Automata (DFA). DFA have a rich background in terms of the mathematical theory underlying their development and use. Informally DFA is defined as, “Deterministic finite automaton is a simple idealized machine used to recognize pattern within input takes from some set of symbols or alphabet ∑”. The main job of DFA is to accept or reject an input depending on whether the pattern defined by the finite automata occurs in the input. DFA is also called deterministic finite state machine or deterministic finite accepter.

Analytically a deterministic finite automaton is defined by five-tuples are as follows;
M = (Q, Σ, δ, q₀, F)
Where, each tuple have its specification and own definition.

1. Q: It represents the finite non-empty set states. All the finite number of states which is the part of M participates in Q.
2. Σ: It presents the non-empty finite set of the input alphabet.
3. δ : It represents the state transition function which maps Q × Σ → Q. It is usually called direct transition function. The state transition function takes the current state from Q and an input alphabet from Σ and returns the new set of output alphabets and the next state. This function mapping is usually represented by a transition table or a transition diagram.
4. q₀: It is the initial state (which may be fixed or variable depends on machine behavior). q₀ ∈ Q
5. F: It is the set of final states (F ⊆ Q). It is assumed here that there may be more than one final state.

Representation of DFA:

A DFA can be represented by the following ways;

1. Transaction diagram DFA or State diagram
2. Transaction table DFA
3. Language of DFA

Transaction diagram DFA:

Transaction diagram is the graphical representation of a DAF. It is also called state transaction diagram. To represent the behavior of a machine under DFA we are using digraph where;

• Nodes or vertices of the digraph represent the states that belong to set of states Q, and
• The connected arcs or arrow labeled with an input alphabets from ∑ that show the transition.
• The initial state is denoted by a circle with an empty single incoming arc.
• The finial state is indicated by double circles.

Transaction table:

A transaction table is a tabular representation that used to represents the working behavior of transaction function δ that takes two arguments as input and returns a output state. Transaction table represents all the moves of a finite semi automaton or finite state machine based on the current state and other inputs. Formally a transaction table is a 2-dimension array which consist rows and columns where;

• The columns contain the state in which the machine will be on the input alphabets ∑ represented by that column.
• The rows corresponds to the state of the finite control unit can be in or it contains the states of finite automata machine (current state and/or next state).
• The entry for one row corresponding to state q_i and the column corresponds to input a is the state δ(q_i, a).

Also check: nfa applications

A transaction table is essentially a truth table in which some of the inputs are the current state, and the outputs include the next state, along with other outputs. A transaction table is also called state transaction diagram.

Language:

The language of DFA consist a set of all strings chosen from ∑^* that all are accepted by machine M.

Example of DFA:

Represent the DFA of machine
M = ({q₀, q₁, q₂}, {0, 1}, δ, q_0, {q₁}), where δ is given as;
δ (q₀, 1) = q₀,
δ (q₀, 0) = q₂,
δ (q₂, 0) = q₂,
δ (q₂, 1) = q₁,
δ (q₁, 0) = q₁,
δ (q₂, 0) = q₁.

State transaction diagram of machine ‘M’:

State transaction table of machine ‘M’:

Language of DFA of machine ‘M’:

                        L_M = {1^*00^*1(0, 1)^*} or
L_M = {1^*00^*1(0+1)^*} or
L_M = {1^*00^*10^*1^*}

Also check: cfg examples with solutions

Application of DFA ( Deterministic Finite Automata):

As DFA have a rich background in terms of the mathematical theory underlying their development it has wide application that we are used our daily life directly or indirectly, some of them are as follows;

• Protocol analysis
• Text parsing,
• Video game character behavior,
• Security analysis,
• CPU control units,
• Natural language processing
• Speech recognition, etc.

More Useful Tutorial for You on:

• Theory of Automata : definition with real time example
• Automata Language, Grammar definition and Rules with examples
• Automata : Alphabets, String & definition notation