# Hysteresis in finite automata

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.

• 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. – Squark Nov 16 '16 at 20:28
• What is an automata with memory/what is a memory-less automata? Are you aware of the Myhill-Nerode theorem? – domotorp Nov 17 '16 at 12:16
• crossposted on math.stackexchange.com/questions/2016512/… – domotorp Nov 17 '16 at 12:17
• 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. – Hans-Peter Stricker Nov 17 '16 at 14:23
• 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. – Sasho Nikolov Nov 18 '16 at 15:27