Deterministische Maschine

Deterministische Maschine

Ein deterministischer endlicher Automat (DEA, engl.: DFA=deterministic finite automaton) ist ein endlicher Automat, der unter Eingabe eines Zeichens seines Eingabealphabetes (mögliche Eingaben) von einem Zustand, in dem er sich befindet, in einen eindeutig bestimmten Folgezustand wechselt.

Formal kann ein DEA \mathcal{A} als 5-Tupel \left( Q, \Sigma, \delta, q_0, F \right) definiert werden. Hierbei gilt Folgendes:

  • Q (oft auch Z oder S) ist eine Zustandsmenge, eine nichtleere endliche Menge von Zuständen. Zum Beispiel z0, z1 und z2 oder auch „Getränkeautomat wartet auf Eingabe“, „Kaffee ausschenken“, „Wechselgeld zurückgeben“, …
  • Σ ist ein endliches Eingabealphabet, also erlaubte Eingaben, wie z. B. 1 und 0 oder auch „Münze einwerfen“, „Taste für Milchkaffee drücken“, „Taste Abbruch drücken“, …
  • Es gibt eine Übergangsfunktion \delta : Q \times \Sigma \rightarrow Q, so dass für p, q \in Q und a \in \Sigma gilt δ(q,a) = p. δ ordnet jedem Paar, bestehend aus einem Zustand q und einem Eingabesymbol a, einen neuen Zustand p zu. Der Automat wechselt also von einem Zustand q in einen anderen Zustand p, wenn im Zustand q eine (gültige) Eingabe a gemacht wurde. Beispiel: δ(z0, 1) = z2 oder δ(„Getränkeautomat wartet auf Eingabe“, „Taste für Milchkaffe gedrückt“) = "Kaffee ausschenken"
  • q_0 \in Q ist der Startzustand. Statt q0 wird oft auch z0 verwendet. Beispiel: z0 oder „Getränkeautomat wartet auf Eingabe“.
  • F \subseteq Q (oft auch A) ist die Menge der akzeptierenden Zustände, die sogenannten Finalzustände. Zum Beispiel: z2 oder „Getränkeautomat wartet auf Eingabe“ (in diesem Fall ist der Startzustand auch ein Finalzustand)

Wenn sich der Automat nach dem Lesen des Eingabewortes w \in \Sigma^*, also einer Folge von Eingaben und den damit verbundenen Zustandsübergängen, in einem Finalzustand aus F befindet, so gehört w zur Sprache L\left(A\right).

Ist ein DEA in der Lage jedes Wort über dem betrachteten Alphabet bis zum Ende lesen zu können, auch wenn es nicht in der zu akzeptierenden Sprache enthalten ist, wird er vollständig genannt.

Nichtdeterministische endliche Automaten (NEAs), DEAs und Typ-3-Grammatiken (vgl. Chomsky-Hierarchie) beschreiben die gleiche Sprachklasse. NEAs lassen sich mittels Potenzmengenkonstruktion in äquivalente DEAs wandeln.

Minimierung

Zu jedem DEA existiert ein (bis auf die Benennung der Zustände) eindeutiger minimaler Automat, der dieselbe Sprache akzeptiert.

Da die Zustände des Minimalautomaten den Äquivalenzklassen der vom endlichen Automaten M akzeptierten Sprache unter der Nerode-Relation entsprechen, spricht man auch vom Äquivalenzklassenautomat:

u \sim_{L(M)} v \Longleftrightarrow (\forall w \in \Sigma^{*} : uw \in L(M) \Leftrightarrow vw \in L(M))

Sei M = (Q,Σ,δ,q0,F) ein deterministischer endlicher Automat. Dann ist N = (Q',Σ,δ',q0',F') mit

  • Q' = \Big\{[w]_{L(M)}  \mid w \in \Sigma^*\Big\}
  • ~q'_0 = [\epsilon]_{L(M)}
  • ~\delta'([u]_{L(M)} ,a)=[ua]_{L(M)}
  • F' = \Big\{[u]_{L(M)}  \mid u \in L(M)\Big\}

der Äquivalenzklassenautomat zu M.

Die Minimierung eines deterministischen Automaten kann algorithmisch durch fortwährende Verfeinerung der Äquivalenzklassen gelöst werden. Man beginnt mit den Zustandsmengen F und QF. Für jeden Buchstaben aus dem Alphabet wird nun jede Zustandsmenge dahingehend aufgeteilt, dass die Überführungsfunktion die Zustände jeder neuen Menge den Buchstaben in eine jeweils eindeutige Menge abbildet. Dies wird so oft wiederholt bis sich keine Änderung mehr ergibt.

Siehe auch

Literatur

  • John E. Hopcroft, Jeffrey D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. 2. Auflage. Pearson Studium, Reading 2002, ISBN 3-8273-7020-5
  • Gottfried Vossen, Kurt-Ulrich Witt, Grundkurs Theoretische Informatik 3.Auflage, ISBN 3-528-23147-5
  • Peter Sander, Wolffried Stucky, Rudolf Herschel: Automaten, Sprachen, Berechenbarkeit. Teubner, Stuttgart 1992, ISBN 3-519-02937-5
  • Uwe Schöning: Ideen der Informatik, Grundlegende Modelle und Konzepte. Oldenbourg, München 2006, ISBN 3-486-57833-2

Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Turing-Maschine — Die Turingmaschine ist ein von dem britischen Mathematiker Alan Turing 1936 entwickeltes Modell, um eine Klasse von berechenbaren Funktionen zu bilden. Sie gehört zu den grundlegenden Konzepten der Informatik. Das Modell wurde im Rahmen des von… …   Deutsch Wikipedia

  • Abstrakte Maschine — Ein Automat oder eine abstrakte Maschine ist in der Informatik das Modell eines digitalen, zeitdiskreten Rechners. Ob es möglich oder sinnvoll ist, eine solche Maschine tatsächlich zu bauen, ist dabei zunächst unerheblich. Die Vereinfachung der… …   Deutsch Wikipedia

  • Linear beschränkte Turing-Maschine — Eine linear beschränkte Turingmaschine (auch LBA = Linear Bounded Automaton) ist eine Turingmaschine, die den Eingabebereich nicht verlässt. Das bedeutet, dass sie nur den Teil des Bandes benutzt, auf dem zu Beginn das Eingabewort steht. Eine LBA …   Deutsch Wikipedia

  • Determinist — Determinismus (lat. determinare „abgrenzen“, „bestimmen“) ist ein philosophisches Konzept und zusammen mit seinem Gegenstück, dem Indeterminismus, ein wesentliches Grundelement zur Herausbildung eines konsistenten Weltbildes. Er geht davon aus,… …   Deutsch Wikipedia

  • Deterministisch — Determinismus (lat. determinare „abgrenzen“, „bestimmen“) ist ein philosophisches Konzept und zusammen mit seinem Gegenstück, dem Indeterminismus, ein wesentliches Grundelement zur Herausbildung eines konsistenten Weltbildes. Er geht davon aus,… …   Deutsch Wikipedia

  • Seiteneffekt — In der Programmierung bezeichnet Wirkung (engl. effect) die Veränderung des Zustands, in dem sich ein Computersystem befindet. Beispiele sind das Verändern von Inhalten des Speichers oder die Ausgabe eines Textes auf Bildschirm oder Drucker. Da… …   Deutsch Wikipedia

  • Wirkung (Informatik) — In der Programmierung bezeichnet Wirkung (engl. effect) die Veränderung des Zustands, in dem sich ein Computersystem befindet. Beispiele sind das Verändern von Inhalten des Speichers oder die Ausgabe eines Textes auf Bildschirm oder Drucker. Da… …   Deutsch Wikipedia

  • Zustandsänderung (Informatik) — In der Programmierung bezeichnet Wirkung (engl. effect) die Veränderung des Zustands, in dem sich ein Computersystem befindet. Beispiele sind das Verändern von Inhalten des Speichers oder die Ausgabe eines Textes auf Bildschirm oder Drucker. Da… …   Deutsch Wikipedia

  • Komplexitätstheorie — Die Komplexitätstheorie als Teilgebiet der Theoretischen Informatik befasst sich mit der Komplexität von algorithmisch behandelbaren Problemen auf verschiedenen mathematisch definierten formalen Rechnermodellen. Die Komplexität von Algorithmen… …   Deutsch Wikipedia

  • Turingmaschine — Die Turingmaschine ist ein von dem britischen Mathematiker Alan Turing 1936 entwickeltes Modell, um eine Klasse von berechenbaren Funktionen zu bilden. Sie gehört zu den grundlegenden Konzepten der Theoretischen Informatik. Das Modell wurde im… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”