Theoretische Informatik - ganz praktisch

2Deterministische Automaten

Wir haben im letzten Kapitel gesehen, dass es notwendig ist, abstrakte Berechnungsmodelle einzusetzen, um allgemeine Eigenschaften von Rechnern oder Programmen untersuchen zu können. Dabei sollten wesentliche Aussagen über das Modell auch auf die jeweiligen realen Rechner übertragbar sein. Beispielsweise sollten durch das Modell dieselben Probleme gelöst werden können wie mit den zugehörigen realen Rechnern. Darüber hinaus ist es auch wünschenswert, dass die benötigten Ressourcen (Zeit, Speicherplatz o. ä.) zur Lösung eines bestimmten Problems beim Modell ähnlich sind wie bei den realen Rechnern.

Es mag daher naheliegend erscheinen, Automaten analog zu den typischen zu untersuchenden Rechnern zu entwerfen. Soll etwa ...