Sequenzielle Maschine
Einfache Sprache
Eine sequenzielle Maschine ist ein Transduktor.
Syntax einer Sequenziellen Maschine
Def. Syntax einer Sequenzielle Maschine
Eine sequenzielle Maschine ist eine Struktur $(Q,A,B,\delta,\alpha,q_I,\iota,\omega)$ mit:
- $Q$ endliche Menge -> Zustände oder Zustandsmenge
- $A$ endliche Menge -> Eingabesymbole oder Eingabealphabet
- $B$ endliche Menge -> Ausgabesymbole oder Ausgabealphabet
- $\delta:Q\times A\rightarrow Q$ -> Transitionsfunktion
- $\alpha:Q\times A\rightarrow B^*$ -> Ausgabefunktion
- $q_I\in Q$ -> Startzustände
- $\iota\in Q$ -> Initiale Aussage
- $\omega:Q\rightharpoonup B^*$ -> Finale Ausgabefunktion
Erweiterung der Transitions- und Ausgabefunktion
Def. erweiterte Transitionsfunktion
Sei $\delta:Q\times A\rightarrow Q$ die Transitionsfunktion einer sequentiellen Maschine. Dann ist die erweiterte Transitionsfunktion $\hat\delta:Q\times A^*\rightarrow Q$ durch Strukturelle Induktion wie folgt definiert: IA: $\hat\delta(q,\varepsilon)=q$ für alle $q\in Q$ IS: sei $w\in A^*$ und $a\in A$ , dann
$$\hat\delta(q,wa)=\delta(\hat\delta(q,w),a)\;.$$
Def. erweiterte Ausgabefunktion
Sei $\alpha:Q\times A\rightarrow B^*$ die Ausgabefunktion einer sequentiellen Maschine. Dann ist die erweiterte Ausgabefunktion $\hat\alpha:Q\times A^*\rightarrow B^*$ durch Strukturelle Induktion wie folgt definiert: IA: $\hat\alpha(q,\varepsilon)=\varepsilon$ für alle $q\in Q$ IS: sei $w\in A^*$ und $a\in A$ , dann
$$\hat\alpha(q,wa)=\hat\alpha(q,w)\alpha(\delta(q,w),a)$$
Semantik einer Sequenziellen Maschine
Def. Semantik einer Sequenziellen Maschine
Sei $M=(Q,A,B,\delta,\alpha,q_I,\iota,\omega)$ eine sequentielle Maschine. Dann ist die von $M$ berechnete Funktion $f_M$ die Partielle Funktion $A^*\rightharpoonup B^*$ mit
$$f_M=\left\{\begin{array}{cc} & \begin{array}{ll}iota\hat\delta(q_I,w)\omega(\hat\delta(q_I,w))& \text{falls $w$ auf $\hat\delta(q_I,w)$definiertist}\\\text{undefiniert}&\text{sonst}\end{array}\end{array}\right.$$Diese Funktion ist eine Sequenzielle Funktion.
Korrektheit
Mit folgenden Schritten kann die Korrektheit einer Sequenzielle Maschine bewiesen werde:
- Formulieren der zu berechnenden Funktion (Spezifikation).
- Bestimmung, welche Funktion von der Sequenzielle Maschine berechnet wird.
- Vergleich beider Funktionen.