Deterministic Finite Automata

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 q₀q₂ , q₁,q₃, q₄

0Comment

thumbs up down

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

2Comments

thumbs up down

k prashanth kumar @prashanthkumar1

3 Jan 2020 10:13 pm

Nice content it's very helpful exactly according to gate needs

Vikas @vikasrajput

4 Jan 2020 11:18 pm

can you explain this with examples

Deterministic Finite Automata (DFA)

There are five tuples in Finite Automata:

Q: a finite set of states

q₀= 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.

0Comment

thumbs up down

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.

0Comment

thumbs up down