Modellierung durch endlichen Automaten

Vorgang:

Zustände? → $Q$ und $I, F$

Aktionen/Eingaben? → die Zustandsübergänge auslösen / dabei stattfinden

Tabelle erstellen, alle Fälle abdecken

Beispiel: Simpsons Flussbeispiel

Dieses Beispiel wäre als Automat leichter zu modellieren.

$\left.\begin{array}{ll}M & \ldots \text { Maggie } \\K & \ldots \text { Knecht Ruprecht } \\G & \ldots \text { Gift } \\H & \ldots \text { Homer }\end{array}\right\}$ System Koponenten

System-Zustand:

Dinge hierDinge dort\frac{\text{Dinge hier}}{\text{Dinge dort}}Dinge dortDinge hier

Endzustand:-MKGHAnfangszustand:MKGH-\textsf{Endzustand: }\frac{\text{-}}{\text{MKGH}} \qquad \textsf{Anfangszustand: }\frac{\text{MKGH}}{\text{-}}Endzustand:MKGH-Anfangszustand:-MKGH

Verbotene Zustände:

GHMK,MKGH,KHMG,MGKH,HMKG,MKGH\frac{G H}{M K}, \frac{M K}{G H}, \frac{K H}{M G}, \frac{M G}{K H}, \frac{H}{M K G}, \frac{M K G}{H}MKGH,GHMK,MGKH,KHMG,MKGH,HMKG

Zustandsübergänge: $\mathrm{h}, \mathrm{m}, \mathrm{k}, \mathrm{g}$

Dadurch Automat ohne verbotenen Zuständen:

Alle gültigen Wörter (die zum Ziel führen) sind die Sprache des Automaten.

Mögliche Lösungen: $\{\text { mhkmghm, mmmhhhgmkhm, ..., mhkmgkmgkmghm, ... \} }$

Beispiel: RLL (run-length limited) Codes

Daten werden auf Festplatten, CDs und DVDs binär kodiert.

Probleme: Abstand zwischen den 1en...

zu groß - zu viele 0en - Synchronisation geht verloren

zu klein - zu wenige 0en - ununterscheidbar

(m : n)-(d, k)-RLL-Codes

Wir wollen die Anzahl der 0en beeinflussen.

Ziel: minimiere n/m, maximiere d

Lösung: Nütze die „natürlichen“ 0er-Strecken und 1er im Datenstrom.

$m \text{ Datenbits} \rarr n \text{ Codebits }$

$\text{Zwischen zwei 1 sollen:}$

$\text{min d, max k}$

$0 \text{ vorkommen.}$

(1 : 2)-(0, 1)-RLL-Code

1 eingabe-bit → 2 ausgabe-bits

Es dürfen nicht zwei 0 hintereinander vorkommen.

Wir machen einen Automaten der das erzwingt. (Ausgaben)

Zustand $\textsf{a}$ hat 2 augehende Kanten.

Zustand $\textsf{b}$ hat 1 augehende Kante. → problematisch bei 3 input bits

Wir "Potenzieren" den Automaten (mehr Kanten)

Zustand $\textsf{a}$ hat 3 augehende Kanten.

Zustand $\textsf{b}$ hat 2 augehende Kanten.

Jetzt entscheidet man willkürlich welches der 3 Kanten man für $0$ und welches man für $1$ wählt:

$10010 \Rightarrow \text{10 10 10 11 01} \text { oder } \text{11 01 01 11 01} \text { oder... }$

Bedingung bleibt immer erhalten.

Vorherige Beispiele

(1:2)-(0,1)-RLL Encoder
$\mathcal{A}=\langle\{a, b\},\{0,1\},\{01,10,11\}, \delta, \gamma, a\rangle$
$\begin{array}{c|cc}\delta & 0 & 1 \\\hline a & a & b \\b & b & a\end{array}$ Zustand $\begin{array}{l|cc}\gamma & 0 & 1 \\\hline a & 01 & 10 \\b & 10 & 11\end{array}$ Ausgabe
$\begin{array}{rllllllllllll}w: & \varepsilon & 0 & 1 & 00 & 10 & 01 & 11 & 000 & 100 & \cdots \\\hline[\mathcal{A}](w): & \varepsilon & 01 & 10 & 0101 & 1010 & 0110 & 1011 & 010101 & 101010 & \cdots\end{array}$

(1:2)-(0,1)-RLL Encoder
$\mathcal{A}=\langle\{a, b\},\{0,1\},\{01,10,11\}, \delta, \gamma, a\rangle$ bei Mealy
$\mathcal{A}=\left\langle\left\{a_{1}, a_{2}, b\right\},\{0,1\},\{01,10,11\}, \delta, \gamma, a\right\rangle$
$\begin{array}{c|cc}\delta & 0 & 1 \\\hline a_{1} & a_{1} & b \\a_{2} & a_{1} & b \\b & b & a_{2}\end{array}$ $\begin{array}{c|c}\gamma & \\\hline a_{1} & 01 \\a_{2} & 11 \\b & 10\end{array}$