Previous
Next
DFA minimazation

Method 1: Partitioning Method

Steps:

1. First, remove unreachable states ie, if you see any state which doesn't have any incoming edge, or which is not reachable from the start state, remove it.

2. Draw state transition table.

3. Find 0 equivalent: 0 equivalent means, separate final state to other states. It means putting all non-final state to the same set and final state/states to another different set.

4.find 1's equivalent, it means from the current state, from a symbol on which set the transition is falling.

if you have to find n equivalent, you need to take help from (n-1) th set.

Example 1: 

 

In minimal DFA we have only 4 states and states are  q0q2 , q1,q3, q4

 

Contributor's Info

Created:
0Comment
+1
0
-1
Some Tips

while making DFA few tips may be very useful:

 

1. |w| = n ,then no. of states in DFA is n+2.

2. |w| >= n, then no.of states in DFA is n+1

3. |w|<=n, then no. of states in DFA is n+2

4.|w| mod n=n1, where n1 ⊂n then no. of states in DFA  is n

 

  

 

 

Contributor's Info

Created:
0Comment
+1
0
-1
Deterministic Finite Automata (DFA)

There are five tuples in Finite Automata:

Q: a finite set of states 

q0= initial state.

f=   final state(F ⊆ Q)

∑= input alphabets.

δ= Input transition function.

δ  for DFA is defined as you are on some state and on seeing a particular symbol you are going to only one state. 

δ= Q X ∑ --> Q.

In DFA for every state, for every input, there is exactly one transition function.

Some examples of DFA.

 

          

 

 

Contributor's Info

Created:
0Comment
+1
0
-1
Deterministic Finite Automata (DFA)

In a deterministic finite-state automaton (DFA), each move has only one choice for the next state of the device, given the current state and the next input. After processing the entire input string, if you end up in a final state (sometimes called an accept state), then the input string is in the language accepted by the finite-state automaton.

Contributor's Info

Created:
0Comment
+1
0
-1