Block Diagram of a Finite Automata
Analytically. a finite automaton can be represented by a 5-tuple (Q, ∑, δ, q0, F) where
i. Q is a finite non-empty set of states.
ii. ∑ is a finite nonempty set of inputs called the input alphabet.
iii. δ is a function which maps Q x ∑ into Q and is usually called the direct transition function. This is the function which describes the change of states during the transition. This mapping is usually represented by a transition table or a transition diagram.
iv. q0 ∈ Q is the initial state.
v. F ⊆ Q is the set of final states. It is assumed here that there may be more than one final state.
Components of a Finite Automata:
1. Input tape: The input tape is divided into squares, each square containing a single symbol from the input alphabet ∑. The end squares of the tape contain the end marker ¢ at the left end and the end marker $ at the right end. The absence of end markers indicates that the tape is of infinite length. The left-to-right sequence of symbols between the two end markers is the input string to be processed.
2. Reading head: The head examines only one square at a time and can move one square either to the left or to the right. For further analysis, we restrict the movement of the R-head only to the right side.
3. Finite control: The input to the finite control will usually be the symbol under the R-head, say a, and the present state of the machine, say q, to give the following outputs:
i. A motion of the R-head along the tape to the next square (in some a null move, i.e. the R-head remaining in the same square is permitted).
ii. the next stage of the finite state machine is given by δ(q, a).