Medwedew-Automat

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

In der theoretischen Informatik versteht man unter einem Medwedew-Automaten einen endlichen Automaten, dessen Ausgabe direkt der Zustand ist (während sie beim Moore-Automat mit einem eigenen Schaltwerk auf der Basis des Speicherzustandes generiert wird). Der Name geht auf Ju. T. Medwedew zurück, der einer Übersetzung von Automata Studies[1] ins Russische einen eigenen Artikel[2][3] anhängte.[4]

Als Indikator dienen die Zustände, wobei bei manchen Automaten Akzeptanzzustände (Endzustände) existieren. Ein solcher Medwedew-Automat wird auch Akzeptor genannt. Medwedew-Automaten sind besonders einfach zu realisieren; komplexer sind Mealy-Automaten und Moore-Automaten. Der Medwedew-Automat ist ein Spezialfall des Moore-Automaten.

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. C. E. Shannon, J. McCarthy (Hrsg.): Automata Studies. Princeton University Press, 1956, S. 129–153.
  2. Ю. Т. Медведев: О классе событий, допускающих предсавление в конечном автомате. В сб. Автоматы. ИЛ, Moskau 1956, S. 385–401.
  3. Yu. T. Medvedev: On the class of events representable in a finite automaton. Sequential Machines: Selected Papers. Addison-Wesley, 1964.
  4. Arto Salomaa: Composition Sequences and Synchronizing Automata. LNCS 7160. Springer, Berlin/Heidelberg 2012, S. 403–416.