TOC : CONSTRUCTION OF FINITE AUTOMATA (FA) | Class-3

CONSTRUCTION OF FINITE AUTOMATA

In this post we are going to learn how to construct finite automata (FA). CONSTRUCTION OF FINITE AUTOMATA (FA) means design a machine which can accept a variety of combination of input string i.e 0/1.

Input String such as :10,100,1100,10000,1010110 etc.

Let we understand by the help of examples:

1. Construct a DFA which accept string of 0's and 1's end with substring 00.


Solution: 

Here string end with 00 means those string whose last two bits are 00 such as 100,1000, 1100, 101100, 110100 etc.

Now For CONSTRUCTION OF FINITE AUTOMATA (FA) we design a machine that can accept the above strings such as 100,1000, 1100, 110100, 100100, etc.

Let first we take Input strings in different cases. 

CASE I: Input Sting =00

 CASE II: Input Sting =000

               

CASE III: Input Sting =1000    OR   1100    OR    111000

                 

CASE IV: Input Sting =110100 

                     

CASE V: Input Sting =100100  

                   

Now this transition graph is final which satisfy all input string ended with 00.

Formal Definition:

Q = {q0, q1, q2}

Σ = {0, 1}

q0 = q0

F = {q2}

δ ( Transition table) =

Now we get final transition table on the basis of above graph. For CONSTRUCTION OF FINITE AUTOMATA (FA) we consider different cases and in CASE V we get final graph that satisfy all type of input strings end with 00.

2. Construct a DFA which accept a string of 0's and 1's contain 3 consecutive 0's. Example (000, 1000, 00001, 10001, 11000, 111000 etc.)

Solution : 

 In this question we are talking about three consecutive 0's so we will take for states such as (q0, q1, q2, q3)

Let we understand with different cases by using different input strings for CONSTRUCTION OF FINITE AUTOMATA (FA) :

Case I : Input String = 000

Case II : Input String = 1000

Case III : Input String = 101000

Case IV : Input String = 101001000

Case IV : Input String = 1010010001   OR    10100100010

Formal Definition :

Q = {q0, q1, q2, q3}

Σ = {0,1}

q0 = q0

F = {q0}

δ = Transition Table

For CONSTRUCTION OF FINITE AUTOMATA (FA) we had seen different cases and finally construct a machine. In CASE V we get final graph.

3. Construct a DFA which accept a string of a's and b's start and end with a such as  aa, aaa, aba, abba, etc.

Solution : 

Here for CONSTRUCTION OF FINITE AUTOMATA (FA) input strings are combination of a and b and string must start and end with a.

For CONSTRUCTION OF FINITE AUTOMATA (FA) we will take different cases of input string and trace it.

let we start

Case I: Input string = aa or aaa or aaaaa or aaaaaa etc.

Case II: Input string = aba 

Case III: Input string = ababa 

Case IV: Input string = abaa 

Case V: Input string = abaaba 

Formal Definition : 

Q = {q0, q1, q2}

Σ = {a, b}

q0 = q0

F = {q2}

δ = Transition Table

For CONSTRUCTION OF FINITE AUTOMATA (FA) we had seen different cases and finally construct a machine. In CASE V we get final graph.

4. Construct a DFA which accept a string of a's and b's start and ends with the same symbol. such as ( aba, bab, a, b etc).

Solution : 

Here for CONSTRUCTION OF FINITE AUTOMATA (FA) input strings are combination of a and b and string must start and end with same symbol.

For CONSTRUCTION OF FINITE AUTOMATA (FA) we will take different cases of input string and trace it.

let we start

Case I: Input string = a or b 

Case II: Input string = aa or bb 

Case III: Input string = aabba /aaabbba or bbaab /bbbaaab 

Formal Definition :

Q = {q0, q1, q3, q4}

Σ = {a,b}

q0 = q0

F = {q1 , q2}

δ = Transition Table

For CONSTRUCTION OF FINITE AUTOMATA (FA) we had seen different cases and finally construct a machine. In CASE III we get final graph.

5. Constrict a DFA which accept a string of a's and b's contain even number of a's followed by odd number of b's. such as (b, aab, aabbb etc.)

Solution:

Here for CONSTRUCTION OF FINITE AUTOMATA (FA) input strings are combination of a and b and string having even number of a's and odd number of b's.

For CONSTRUCTION OF FINITE AUTOMATA (FA) we will take different cases of input string and trace it.

let we start

Case I: Input string = b / aab

Case II: Input string = b / aab /aabbb /aaaabbb 

Case III: Input string = Note there are some rejected states such as (aba / aabba / aaba etc)

Formal Definition :

Q = {q0, q1, q3, q4, q5}

Σ = {a,b}

q0 = q0

F = {q3}

δ = Transition Table

For CONSTRUCTION OF FINITE AUTOMATA (FA) we had seen different cases and finally construct a machine. In CASE III we get final graph.

6. Constrict a DFA which accept number ( integer) divisible by 2 or (multiple of 2) .

Solution:

Here for CONSTRUCTION OF FINITE AUTOMATA (FA) input strings are combination of a and b and string having 0 - 9  number  i.e 10 numbers because any number divisible by 2 the resulting number must be between 0 - 9.

For CONSTRUCTION OF FINITE AUTOMATA (FA) we will take different cases of input string and trace it.

Here we have two states such as q1 , q2. where q2 is final state.

let we start

Case I: Input string = If string is even numbers such as (0,2,4,6,8) between 0 - 9.

Case II: Input string = If string is odd numbers such as (1,3,5,7,9) between 0 - 9.

Formal Definition :

Q = { q1 , q2 }

Σ = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }

q1 = q1   Initial state

F = { q1 }

δ = 

For CONSTRUCTION OF FINITE AUTOMATA (FA) we had seen different cases and finally construct a machine. In CASE II we get final graph.

7. Constrict a DFA which accept number ( integer) divisible by 3 or (multiple of 3) .

Solution:

Here for CONSTRUCTION OF FINITE AUTOMATA (FA) input strings are combination of a and b and string having 0 - 9  number  i.e 10 numbers because any number divisible by 3 the resulting number must be between 0 - 9.

For CONSTRUCTION OF FINITE AUTOMATA (FA) we will take different cases of input string and trace it. In this case No of group = No of state.

Let we have three groups
Group1: 0,3,6,9
Group2: 2,5,8
Group3: 1,4,7

Group1 is divisible by 3.
Group2 & Group3 is not divisible by 3.

Here we have two states such as q0 , q1, q3. where q0 is final state.


let we start

Case I: Input string = If we take Group1 such as (0,3,6,9) which is divisible by 3 initially then.

Case II: Input string = If we take Group2 and Group3 such as ( 2,5,8 / 1,4,7 ) which is divisible by 3 initially then.

Formal Definition :

Q = { q0 , q1 , q2 }

Σ = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }

q0 = q0   Initial state

F = { q0 }

δ = 

For CONSTRUCTION OF FINITE AUTOMATA (FA) we had seen different cases and finally construct a machine. In CASE II we get final graph.