Finite Automata

A finite automaton (FA, also called a finite-state automaton or a finite-state machine) is a mathematical tool used to describe processes involving inputs and outputs. An FA can be in one of several states and can switch between states depending on symbols that it inputs. Once it settles in a state, it reads the next input symbol, performs some computational task associated with the new input, outputs a symbol, and switches to a new state depending on the input. Notice that the new state may be identical to the current state.

Figure 1 shows an example of a two-state FA that can be used to add binary numbers. The FA starts in state 1 (no carry) and inputs a pair of bits. If the pair is 11, the FA outputs a 0 and switches to state 2 (carry), where the next pair of bits is input and is added to a carry bit of 1. Table F.1 shows the individual steps in adding the two 6-bit numbers 14and 23 (these are actually 5-bit numbers, but the simple design of this FA requires that an extra 0 bit be appended to the left end of every number). Since adding numbers is done from right to left, the six columns of the table should also be read in this direction.

Definition: A DFA is 5-tuple or quintuple M = (Q, ∑, δ, q0, A) where
                 Q is non-empty, finite set of states.
                 ∑ is non-empty, finite set of input alphabets.
                 δ is transition function, which is a mapping from Q ∑ to Q.
                q0 ∈ Q is the start state.
                A ⊆ Q is set of accepting or final states.
Note: For each input symbol a, from a given state there is exactly one transition (there can be no transitions from a state also) and we are sure (or can determine) to which state the machine enters. So, the machine is called Deterministic machine. Since it has finite number of states the machine is called Deterministic finite machine or Deterministic Finite Automaton or Finite State Machine (FSM).
The language accepted by DFA is
      L(M) = { w | w ∈ ∑* and δ*(q_{0, w) ∈ A }
The non-acceptance of the string w by an FA or DFA can be defined in formal notation as:
       = { w | w ∈ ∑* and δ*(q0, w)  A }}

So, the DFA which accepts strings of a’s and b’s starting with the string ab is given by M 

= (Q, ∑ , δ, q0, A) where

     Q = {q₀, q₁, q₂, q₃}
     ∑ = {a, b}
     q0­ is the start state
     A = {q₂}.
     δ is shown by the transition table 3.

Example 2: Draw a DFA to accept string of 0’s and 1’s ending with the string 011.


Example 3: Obtain a DFA to accept strings of a’s and b’s having a sub string aa


Example 4: Obtain a DFA to accept strings of a’s and b’s except those containing the sub string aab.


Example 5: Obtain DFAs to accept strings of a’s and b’s having exactly one a. atleast one a and others


Example 6: Obtain a DFA to accept strings of a’s and b’s having even number of a’s and b’s
The machine to accept even number of a’s and b’s

Definition: Let M = (Q, ∑, δ, q0, A) be a DFA. The language L is regular if there exists a machine M such that L = L(M).

Applications of Finite Automata

• String matching/processing
• Compiler Construction

The various compilers such as C/C++, Pascal, FORTRAN or any other compiler is designed using the finite automata. The DFAs are extensively used in the building the various phases of compiler such as

• Lexical analysis (To identify the tokens, identifiers, to strip of the comments etc.)
• Syntax analysis (To check the syntax of each statement or control statement used in the program)
• Code optimization (To remove the un wanted code)
• Code generation (To generate the machine code)

The concept of finite automata is used in wide applications. It is not possible to list all the applications, as there is infinite number of applications. This section lists some applications:

1. Large natural vocabularies can be described using finite automaton which includes the applications such as spelling checkers and advisers, multi-language dictionaries, to indent the documents, in calculators to evaluate complex expressions based on the priority of an operator etc. to name a few. Any editor that we use uses finite automaton for implementation.
2. Finite automaton is very useful in recognizing difficult problems i.e., sometimes it is very essential to solve an un-decidable problem. Even though there is no general solution exists for the specified problem, using theory of computation, we can find the approximate solutions.
3. Finite automaton is very useful in hardware design such as circuit verification, in design of the hardware board (mother board or any other hardware unit), automatic traffic signals, radio controlled toys, elevators, automatic sensors, remote sensing or controller etc.
4. In game theory and games wherein we use some control characters to fight against a monster, economics, computer graphics, linguistics etc., finite automaton plays a very important role.