DFA Minimization: Marking Procedure

Thread Starter

zulfi100

Joined Jun 7, 2012
656
Hi,
I am trying to understand the concept of DFA minimization. However, I can't understand the marking procedure. I have attached the image. Some body please guide me.

Zulfi.dfa reduction.jpg
 

Thread Starter

zulfi100

Joined Jun 7, 2012
656
Hi,
DFA stands for deterministic finite automata which is drawn in the attached figure (as the first figure) having states q0, q1, q2, q3, q4 and q5. Second figure shows the transition table which shows the movement from one state to another state based upon the inputs 1 or 0. If two different inputs from a state direct the edge to the same state , then its non-deterministic finite automata (NFA) otherwise, its a deterministic finite automata (DFA).

The third figure deals with marking procedure which I want to understand.
Zulfi.
 
Last edited:

WBahn

Joined Mar 31, 2012
29,978
Hi,
DFA stands for deterministic finite automata which is drawn in the attached figure (as the first figure) having states q0, q1, q2, q3, q4 and q5.
You figure doesn't indicate what conditions lead from q5 to q4 and q5 is missing from your table.

It's somewhat moot since there is no way to get to q5, but it is still pretty sloppy and that sloppiness will get you into trouble with this stuff.

Second figure shows the transition table which shows the movement from one state to another state based upon the inputs 1 or 0. If two different inputs from a state direct the edge to the same state , then its non-deterministic finite automata (NFA) otherwise, its a deterministic finite automata (DFA).
You've got it backwards. There's no problem with two different inputs taking the machine from State 1 to State 2 -- that is a deterministic operation. What would make it non-deterministic is if the same input can take the machine from State 1 to two different states.

The third figure deals with marking procedure which I want to understand.
There are many algorithms for minimizing a DFA. I'm not familiar with the one you are trying to use (at least not based on your description this far).

Most of them aim to progressively identify equivalent states, either by breaking states that contain distinguishable subsets or by combining states that are indistinguishable.
 

Thread Starter

zulfi100

Joined Jun 7, 2012
656
Hi,
Thanks for your reply.
<
It's somewhat moot since there is no way to get to q5,
>
Yes you are right. q5 is not reachable so we would neglect it.
I saw a example. I was able to understand the last two rows of marking procedure. We will make pairs of final state with non-final state. So the marking of row q3 and q4 is clear to me. Now I have to understand row q2 & row q1.
I am attaching a marking procedure. I am able to understand step 2(a) of algorithm but not the step 2(b).

Please guide me.

Zulfi. marking alg.jpg
 
Top