<p>The concept of <a href="https://en.wikipedia.org/wiki/Hysteresis" rel="nofollow noreferrer">hysteresis</a> seems well suited to describe and distinguish finite automata:</p>

<blockquote>
  <p>"Hysteresis is the dependence of the state of a system on its history." <sub>(Wikipedia, <em>Hysteresis</em>)</sub></p>
  
  <p>"[The state of a finite state machine] is determined by its history.
  <sub>(Minsky, <em>Computation</em>)</sub></p>
</blockquote>

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

<p>------------------ <em>edited</em> -----------------------</p>

<p>Thanks to domotorp's hint, I found that the <a href="https://en.wikipedia.org/wiki/Myhill%E2%80%93Nerode_theorem" rel="nofollow noreferrer">Nerode index</a> 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. </p>

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

<p>What I would like to know: </p>

<blockquote>
  <ol>
  <li><p>How is the Nerode index related to the structure/complexity/size of a regular expression?</p></li>
  <li><p>How is the Nerode index related to the structure/complexity/size of an equivalent state diagram?</p></li>
  </ol>
</blockquote>

<p>Is there more to say than:</p>

<ul>
<li><p>The lesser complex the regular expression describing an automaton is, the
smaller its Nerode index is. </p></li>
<li><p>The Nerode index is correlated to the number of (accessible) states.</p></li>
</ul>

CC BY-SA 3.0
2016-11-16T20:28:55.340Z
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.
Vanessa
CC BY-SA 3.0
2016-11-17T12:16:41.690Z
What is an automata with memory/what is a memory-less automata? Are you aware of the Myhill-Nerode theorem?
domotorp
CC BY-SA 3.0
2016-11-17T12:17:16.803Z
crossposted on http://math.stackexchange.com/questions/2016512/hysteresis-in-finite-automata
domotorp
CC BY-SA 3.0
2016-11-17T14:23:52.533Z
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
CC BY-SA 3.0
2016-11-18T15:27:56.577Z
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
<automata-theory><regular-expressions><memory>
Hysteresis in finite automata
Hans-Peter Stricker
# Hysteresis in finite automata

(Asked by: username_0 on 2016-11-16)

The concept of [hysteresis](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Myhill%E2%80%93Nerode_theorem) 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.

**Tags:** automata-theory, regular-expressions, memory
> **Comments:**
> **username_1**: 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.  
> **username_2**: What is an automata with memory/what is a memory-less automata? Are you aware of the Myhill-Nerode theorem?  
> **username_2**: crossposted on http://math.stackexchange.com/questions/2016512/hysteresis-in-finite-automata  
> **username_0**: 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.  
> **username_3**: 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.  

---

## 0 answers

