How DFA operates ( Theory with block diagram of FA )

Block diagram of finite automata and operation of DFA:

The thought process of a finite automaton can be graphically represented as;

The various components consist by a finite automata is as follows;

• Input tape: The input tape has the left end and extends to the right end. It is divided into squares and each square containing a single symbol from the input alphabet ∑. The end squares of the tape contain the end markers ₵ at the left end and the end marker $ at the right end. The absence of endmarkers indicates that the tape is of infinite length. The left-to-right sequence of symbols between the two endmarkers in the input string to be processed.
• Read only Head: The tape has a read only head that examines only one square at a time and can move one square either to the left or to the right. At the beginning of the operation the head is always at the leftmost square of the input tape. For further analysis, machine restrict the moment of the read only head from left to right direction only and one square every time when it reads a symbols. Note: The read head never moves to the left direction. When it there is not more symbol in the next right move of the input tape, at this state the machine stops proceeding and automaton terminates its operation.
• Finite control: There is a finite control which determines the state of the automaton and also controls the movement of the head. The input to the finite control will usually be the symbol under the read head (assumed a) and the present state of the machine (assumed q) to give the following outputs;

1. A motion of Read head along the tape to the next square.
2. The next state of the finite state machine given by δ(q, a).

Operation of finite automata:

A finite automata or a deterministic finite accepter operates in the following manner. At the operation initial time, it is assumed to be that the machine in the initial state q₀, with its input mechanism on the leftmost symbol of the input string in input tape. During each move of the automaton, the input mechanism advances one position to the right, so each move consumes one input symbol. When the end of the string is reached, the string is accepted if the automaton is in one of its final states. Otherwise the string is rejected. The input mechanism can move only from left to right and reads exactly one symbol on each step. The transitions from one internal state to another are governed by the transition function δ. For example, if
δ(q0, a) = q1,
then if the finite automaton is in state q₀ and the current input symbol is am then machine will go into the next state q₁. Once it gets to state q₁, and then no matter what symbol is read, this machine never leaves state q₁ until another input symbol is scanned or accepted.

For example;

Check whether string s = {01} is accepted by the machine or not if machine M is defined as
M = ({q₀, q₁, q₂}, {0, 1}, δ, q₀{q₁}), where δ is given as;
δ (q₀, 0) = q0,
δ (q₀, 1) = q₁,
δ (q₁, 0) = q₀,
δ (q₁, 1) = q₂,
δ (q₂, 0) = q₂,
δ (q₂, 0) = q₁.

This machine M accepts the string 01. Let’s starting from the state q₀, the symbol 0 is scanned form the input tape first. Looking at the edges of the graph, it is clear that the automaton remains in state q₀. Next, the read-only head upgraded by 1 and it read 1and the automaton goes into state q₁. We are now at the end of the string and, at the same time, in a final state q₁.

Useful Tutorial for you:

• DFA : definition, representations, application
• Finite State machine : history definition Model example
• Automata : Alphabets, String & definition notation