1
$\begingroup$

How is the equivalence of DFA defined? I found the equivalence of states --- James Hein, section 5.3, page 301. But he doesn't define equivalence between entire automata. (Ullman and Hopcropft seem to define neither.)

$\endgroup$
2
$\begingroup$

You can find a definition in Automata Theory, Languages and Computation by Hopcroft, Motwani, Ullman, in the fourth chapter.

Here's a link : HMU, the section begins at page 171 of the pdf

Two DFA are said to be equivalent if they accept the same language, and (an equivalent proposition) if they have the same minimal automaton (which is unique).

$\endgroup$
  • $\begingroup$ Since you know HMU, any idea why they used the word "madness" in the first chapter's title? I didn't read every word of the first chapter, but I couldn't find any sign of an explanation. This word is not present in the first edition. $\endgroup$ – R. Chopin May 22 at 16:33
  • $\begingroup$ No real idea, sorry! $\endgroup$ – Nathaniel May 22 at 16:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.