Regular language and Applications of Finite Automata

Definition: Let M = (Q, Σ, δ, q₀, 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)

Other applications

The concept of finite automata is used in wide applications. It is not possible to list all the applications as there are 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.

DFA Examples

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

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

Obtain a DFA to accept strings of a’s and b’s except those containing the substring aab.

 

 

Obtain a DFA to accept strings of a’s and b’s having even number of a’s and b’s

 

DFA to accept strings of a’s and b’s starting with the string ab

Obtain a DFA to accept strings of a’s and b’s starting with the string ab 

Transition diagram to accept string ab(a+b)*

So, the DFA which accepts strings of a’s and b’s starting with the string ab is given by M = (Q, Σ , δ, q₀, A) where

Q = {q₀, q₁, q₂, q₃}

Σ = {a, b}

q₀­ is the start state

A = {q₂}.

q3=Dead State

Deterministic Finite Automata (DFA)

Definition: A DFA is 5-tuple or quintuple M = (Q, Σ, δ, q₀, 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 x Σ to Q.

q₀ ∈ 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₀, w) ∈ A }

The non-acceptance of the string w by an FA or DFA can be defined in formal notation as:

L(M) = { w | w ∈ Σ* and δ*(q₀, w) ∉ A }

DFA of Binary number divisible by 5 (Details)

Question:  
Construct DFA  to accept set of all strings over alphabet set {0,1}( i.e, binary integer) is divisible by 5 eg 110, 1010,....?
OR
Construct DFA of strings whose binary interpretation is divisible by 5 over alphabet set {0,1}.
OR
Draw a DFA accepting the following languages over the alphabet {0,1}The set of all strings that, when interpreted as a binary integer, is a multiple of 5. 

Answer:

First we try to look the table, how a binary number is changed with respect to divisibility by 5, when 0 or 1 is placed at right:
---------------------------------------------------------------------------------------------------------
Number | Divisibility(Modulo) |  Inserted 0/(Modulo) | Inserted 1/(Modulo)    |
---------------------------------------------------------------------------------------------------------
0                Mod_0                          00 (Mod_0)                    01(Mod_1)
1                Mod_1                          10 (Mod_2)                    11(Mod_3)
10              Mod_2                          100 (Mod_4)                  101(Mod_0)
11              Mod_3                          110 (Mod_1)                  111(Mod_2)
100            Mod_4                          1000 (Mod_3)                1001(Mod_4)

101            Mod_0                          1010 (Mod_0)                1011(Mod_1)
110            Mod_1                          1100 (Mod_2)                1101(Mod_3)
111            Mod_2                          1110 (Mod_4)                1111(Mod_0)
1000          Mod_3                          10000 (Mod_1)              10001(Mod_2)
1001          Mod_4                          10010 (Mod_3)              10011(Mod_4)

1010          Mod_0                          10100 (Mod_0)              10101(Mod_1)
1011          Mod_1                          10110 (Mod_2)              10111(Mod_3)
1100          Mod_2                          11000 (Mod_4)              11001(Mod_0)
1101          Mod_3                          11010 (Mod_1)              11011(Mod_2)
1110          Mod_4                          11100 (Mod_3)              11101(Mod_4)

1111          Mod_0                          11110 (Mod_0)              11111(Mod_1)
10000        Mod_1                          100000 (Mod_2)            100001(Mod_3)
 -------------------------------------------------------------------------------------------------
And so on....


The State Transition Table is:

-----------------------------------------------------------------------------------
             Mod_0          Mod_1       Mod_2      Mod_3        Mod_4
------------------------------------------------------------------------------------
0           Mod_0           Mod_2      Mod_4      Mod_1       Mod_3
------------------------------------------------------------------------------------
1           Mod_1           Mod_3       Mod_0     Mod_2       Mod_4
------------------------------------------------------------------------------------


Finally the DFA of binary number divisible by 5 is :
 
Where MOD_0 is the final state.