Block Diagram of a Finite Automata

Finite Automata:

Analytically. a finite automaton can be represented by a 5-tuple (Q, ∑, δ, q₀, 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 that maps Q x ∑ into Q and is usually called the direct transition function. This is the function that describes the change of states during the transition. This mapping is usually represented by a transition table or a transition diagram.

iv. q₀ ∈ 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).