1
$\begingroup$

The concept of hysteresis seems well suited to describe and distinguish finite automata:

"Hysteresis is the dependence of the state of a system on its history." (Wikipedia, Hysteresis)

"[The state of a finite state machine] is determined by its history. (Minsky, Computation)

What I am looking for is a definition of hysteresis strength $H$ of finite automata distinguishing finite automata with a stronger dependence on history from those with a weaker one.

------------------ edited -----------------------

Thanks to domotorp's hint, I found that the Nerode index is a good such measure: finite automata (equivalent to finite regular expressions) have a finite Nerode index, and the smaller the Nerode index is, the less "memory" (or hysteresis strength) the automaton has.

But: The Nerode index is defined rather abstractly, as the number of equivalence classes of a language with respect to the Nerode equivalence relation.

What I would like to know:

  1. How is the Nerode index related to the structure/complexity/size of a regular expression?

  2. How is the Nerode index related to the structure/complexity/size of an equivalent state diagram?

Is there more to say than:

  • The lesser complex the regular expression describing an automaton is, the smaller its Nerode index is.

  • The Nerode index is correlated to the number of (accessible) states.

$\endgroup$
  • $\begingroup$ You can consider automata s.t. the state is a function of the last $k$ input symbols. However, for some automata no finite $k$ is sufficient. $\endgroup$ – Vanessa Nov 16 '16 at 20:28
  • $\begingroup$ What is an automata with memory/what is a memory-less automata? Are you aware of the Myhill-Nerode theorem? $\endgroup$ – domotorp Nov 17 '16 at 12:16
  • $\begingroup$ crossposted on math.stackexchange.com/questions/2016512/… $\endgroup$ – domotorp Nov 17 '16 at 12:17
  • $\begingroup$ 1. I tried to sketch how a memory-less automaton might look like. Why doesn't this work? 2. I was not. Thanks for the hint. $\endgroup$ – Hans-Peter Stricker Nov 17 '16 at 14:23
  • $\begingroup$ From your question, it seems like you are not understanding the Myhill-Nerode theorem. The number of equivalence classes is exactly equal to the minimum number of states of a DFA recognizing the language. On the other hand, the size of a regular expression corresponds more closely to the size of an NFA, which can be a lot smaller, and for which the theory is not nearly as nice. $\endgroup$ – Sasho Nikolov Nov 18 '16 at 15:27

Your Answer

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

Browse other questions tagged or ask your own question.