Zur Strukturtheorie sequentieller Automaten

Viac o knihe

Abstrakte Modelle sequentieller Automaten wurden erstmals von MOORE und MEALY in den 1950er Jahren eingeführt. Diese Modelle zeichnen sich durch eine endliche Anzahl von Zuständen, Eingangs- und Ausgangssymbolen aus. Das MOORE-Modell basiert auf deterministischem Verhalten, wobei der aktuelle Zustand der Maschine vom vorhergehenden Eingangs-Symbol und Zustand abhängt, während das Ausgangs-Symbol nur vom aktuellen Zustand bestimmt wird. Im MEALY-Modell hingegen sind das aktuelle Ausgangs-Symbol und der nächste Zustand direkt durch das aktuelle Eingangs-Symbol und den aktuellen Zustand definiert. Diese Beziehungen werden durch Tabellen und Zustandsdiagramme veranschaulicht. Eine formalere Definition sequentieller Automaten wurde 1957 von BURKS vorgestellt, der Eingangs- und Ausgangssymbole sowie Zustände auf natürliche Zahlen abbildet und die Zeit durch natürliche Zahlen erfasst. Die funktionalen Beziehungen werden durch S(t+1)=g[x(t), S(t)] und Y(t)=J[x(t), S(t)] beschrieben, was dem MEALY-Modell entspricht. AUFENKAMP wählte eine Darstellung mit Transitions- und Ausgangsmatrizen. 1958 erweiterten RANEY, GINSBURG und SRINIVASAN-NARASIMHAN die funktionalen Beziehungen zwischen Eingangs- und Ausgangssymbolen sowie Zuständen durch die Betrachtung von Folgen dieser Symbole.