Creating a minimized DFA

[charris67]

Anyone know a good site that explains step by step how to create a minimized Deterministic Finite State Automaton? I found a few site, but they don't go into enough detail on the process.

Thanks.

[mehdi62b]

well,I try to give you an example
take a look at this DFA
it has two inputs {1,0},Dashed line mean 0,solid lines mean 1
state A is the first state,state C is the accepting state

http://www.geocities.com/mahdi62b/DFA0.gif

now we want to minimize this DFA,so we should find the equvalent states,we firstly make a chart table like fger below,we have tree numbers in the table which I explain you as follow

well in the first stpe we know C is the only accepting state so it would be inequivalence to other states so we put 1 in the cells regards to C
for the second step(number 2) for example cell (B,A),you with input 1 B goes to C while A goes to F which C and F are inequvalent states so A and B would be inequvalent
well for number 3,like (A,G) with input 0 A goes to B while G goes to G and B and G was inequvalent(from the previous step (2))
you should make a table like below and folow those steps in its order so the blank cells are equvalent I mean two pairs, {B,H} and {D,F} and {A,E}

http://www.geocities.com/mahdi62b/chart1.gif

of cource without that table you could the equvalent nodes
for example D and F with input 0 they go to C and with input 1 they go to G (like B and H)
for A and E with input 1 they go to F with input 0 A goes to B and E goes to H and B,H was equvalent so A and E would be equvalent.
(Copyright: Mehdi)

[charris67]

Thanks mehdi62b for the explanation. I have another question...

Why are dfas created by syncronizing two dfa? Is it possible to just take each string the dfa recognizes and add each one char by char? Will this not create an equivalent dfa as the minimized algorithm?

[mehdi62b]

Why are dfas created by syncronizing two dfa?you know every regular expression have an equivalent DFA,in regular expressions we have some basic operations like union,intersection,repetition which would result in bigger regular expressions and also eqiuvalent DFAs,all those operations have their own way for making the resulting DFA from previous ones, I don't know what do you mean there by synchronizationIs it possible to just take each string the dfa recognizes and add each one char by char?Will this not create an equivalent dfa as the minimized algorithm?I can't get your meaning there, DFAs necessarily don't accept finite strings which you want to make them in that manner
like this regular expression in the figure
01(1)*=01+011+0111+01111... (states A,B,C)