Medwedew-Automat

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<ref>C. E. Shannon, J. McCarthy (Hrsg.): Automata Studies. Princeton University Press, 1956, S. 129–153.</ref> ins Russische einen eigenen Artikel<ref>Ю. Т. Медведев: О классе событий, допускающих предсавление в конечном автомате. В сб. Автоматы. ИЛ, Moskau 1956, S. 385–401.</ref><ref>Yu. T. Medvedev: On the class of events representable in a finite automaton. Sequential Machines: Selected Papers. Addison-Wesley, 1964.</ref> anhängte.<ref>Arto Salomaa: Composition Sequences and Synchronizing Automata. LNCS 7160. Springer, Berlin/Heidelberg 2012, S. 403–416.</ref>

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