Potenzmengenkonstruktion - LinkFang.de





Potenzmengenkonstruktion


Die Potenzmengenkonstruktion (Myhill-Konstruktion oder auch Teilmengenkonstruktion) ist ein Verfahren, das einen nichtdeterministischen endlichen Automaten (NEA) in einen äquivalenten deterministischen endlichen Automaten (DEA) umwandelt. Das Verfahren dient als konstruktiver Beweis für die Äquivalenz der beiden Automatenmodelle.

Grundidee

Die Zustände des konstruierten deterministischen Automaten DEA sind Mengen von Zuständen des nichtdeterministischen Automaten NEA. Ein Zustand vom DEA kodiert dabei all diejenigen Zustände, in denen sich der äquivalente nichtdeterministische Automat NEA zu einem bestimmten Zeitpunkt befinden könnte. Ein Zustandsübergang im DEA ist deterministisch, da sein Folgezustand aus der Menge aller möglichen Folgezustände besteht, in die ein NEA unter einer bestimmten Eingabe gelangen kann.

Das Verfahren heißt Potenzmengenkonstruktion, weil die Zustände des konstruierten Automaten Mengen von Zuständen des Ausgangsautomaten sind und daher die konstruierte Zustandsmenge Teil der Potenzmenge der Zustandsmenge des Ausgangsautomaten ist.

Die Potenzmengenkonstruktion ergibt nicht notwendigerweise einen minimalen deterministischen endlichen Automaten.

Theoretischer Rahmen

Die Wissenschaftler Michael O. Rabin und Dana Scott wurden 1976 für ihre Arbeiten im Bereich der Automatentheorie mit dem Turing Award ausgezeichnet. Um den nach ihnen benannten Satz

Jede von einem NEA akzeptierte Sprache ist auch durch einen DEA akzeptierbar.

beweisen zu können, wird ein Algorithmus konstruiert, der jedem NEA einen äquivalenten DEA zuweist.

Konstruktion

Zu einem nichtdeterministischen Automaten [math]\mathcal{NA} = (Q, \Sigma, \delta, q_0, F)[/math] konstruiere einen äquivalenten deterministischen Automaten [math]\mathcal{A} = (Q', \Sigma, \delta', q_0', F')[/math] folgendermaßen:

  1. Starte mit leeren Zustandsmengen [math]Q\!\,'[/math] und [math]F\!\,'[/math].
  2. Wähle den Startzustand [math]q_0\!\,'[/math] von [math]\mathcal{A}[/math] als einelementige Menge [math]q_0\!\,' = \{q_0\}[/math] des Startzustandes [math]q_0 \in Q[/math] von [math]\mathcal{NA}[/math]. Füge [math]q_0\!\,'[/math] zur Menge der Zustände [math]Q\!\,'[/math] hinzu.
  3. Für alle Zustände [math]q\!\,'[/math], die bereits in [math]Q\!\,'[/math] enthalten sind:
    • Für jedes Eingabezeichen [math]s \in \Sigma[/math]:
      • Konstruiere einen Folgezustand [math]q''\!\,[/math] als Menge aller Zustände, die [math]\mathcal{NA}[/math] ausgehend von einem Zustand aus [math]q'\!\,[/math] unter Eingabe von [math]s\!\,[/math] erreichen kann. Also [math]q'' := \bigcup\{\delta(r,s)|r\in q'\}\!\,[/math].
      • Füge den Zustand [math]q\!\,''[/math] zu [math]Q\!\,'[/math] hinzu, falls er noch nicht in der Menge der Zustände von [math]\mathcal{A}[/math] enthalten ist.
      • Ergänze die Übergangsfunktion [math]\delta\!\,'[/math] um den Übergang [math]\delta\!\,'(q', s) = q''[/math].
  4. Wiederhole Schritt 3. so lange, bis sich [math]Q\!\,'[/math] und [math]\delta\!\,'[/math] nicht mehr ändern.
  5. Wähle die Menge der Finalzustände [math]F\!\,'[/math] von [math]\mathcal{A}[/math] als diejenige Teilmenge von [math]Q\!\,'[/math], deren Zustände einen Finalzustand aus [math]F\!\,[/math] enthalten.

Bemerkung: [math]\mathcal{A}[/math] kann am Ende bis zu [math]2^{|Q|}[/math] Zustände haben. Dies ist aber unvermeidlich, weil Sprachen existieren (z.B. [math](0|1)^*0(0|1)^n[/math]), die von einem NEA mit [math]n+2[/math] Zuständen akzeptiert werden, die aber [math]2^{n+1}[/math] Myhill-Nerode Äquivalenzklassen haben, womit ein äquivalenter DEA mindestens [math]2^{n+1}[/math] Zustände haben muss.

Formal

Sei [math]A = \left(Q, \Sigma, \delta, s, F \right)[/math] ein nichtdeterministischer endlicher Automat mit der Zustandsmenge [math]Q\!\,[/math], dem Eingabealphabet [math]\Sigma\!\,[/math], der Übergangsfunktion [math]\delta\colon Q\times\Sigma\to \mathcal P(Q)\!\,[/math], dem Startzustand [math]s\!\,[/math] und der Menge der Finalzustände [math]F\!\,[/math]. Seien weiterhin

[math]E: Q \rightarrow \mathcal P(Q)[/math], so dass [math]\forall q \in Q: q \in E(q)[/math] und [math]r \in E(q) \Leftrightarrow \exists p \in E(q): r\in\delta(p, \epsilon)[/math], der [math]\epsilon\!\,[/math]-Abschluss eines Zustands unter [math]\delta\!\,,[/math]
[math]s'\!\, := E(s)[/math], der [math]\!\,\epsilon[/math]-Abschluss von [math]s\!\,[/math] unter [math]\delta\!\,,[/math]
[math]\tilde\delta: \mathcal P(Q) \times \Sigma \to \mathcal P(Q)[/math], mit [math]\tilde\delta(q', a) := \bigcup \{E (r)| p\in q', r\in\delta(p,a)\},[/math]
[math]Q' \subseteq \mathcal P(Q)[/math], so dass [math]Q'[/math] die kleinste Menge ist mit [math]s' \in Q'[/math] und [math]\forall q' \in Q', \forall a \in \Sigma: \tilde\delta(q', a) \in Q',[/math]
[math]\delta'\colon Q'\times\Sigma\to Q', \delta' := \tilde\delta\mid_{Q'\times\Sigma},[/math]
[math]F' := \Big\{q' \in Q' | q' \cap F \neq \emptyset \Big\}.[/math]

Daraus ergibt sich der zu [math]A\!\,[/math] äquivalente deterministische endliche Automat [math]A'\!\,[/math] als:

[math]A' = \left(Q', \Sigma, \delta', s', F' \right)[/math]

Beispiele

Automat zum regulären Ausdruck (a|b)*aba

Gegeben sei der nichtdeterministische Automat [math]\mathcal{NA} = \Big(\{s_0, s_1, s_2, s_3\}, \Sigma, \delta, s_0, \{s_3\} \Big)[/math] über dem Alphabet [math]\Sigma\!\, = \{a, b\}[/math] mit der tabellarisch gegebenen Übertragungsfunktion [math]\delta\!\,[/math]:

δ a b
[math]s_0\!\,[/math] [math]\{s_0\!\,, s_1\}[/math] [math]\{s_0\}\!\,[/math]
[math]s_1\!\,[/math] [math]\emptyset[/math] [math]\{s_2\}\!\,[/math]
[math]s_2\!\,[/math] [math]\{s_3\}\!\,[/math] [math]\emptyset[/math]
[math]s_3\!\,[/math] [math]\emptyset[/math] [math]\emptyset[/math]

Eine graphische Darstellung des Ausgangsautomaten sieht folgendermaßen aus:

Nach obiger Konstruktion ergeben sich die Zustandsmenge [math]Q\!\,' = \{S_0', S_1', S_2', S_3'\}[/math] und die Übertragungsfunktion [math]\delta\!\,'[/math] des äquivalenten deterministischen Automaten wie folgt:

δ' a b
[math]S_0\!\,' = \{s_0\}[/math] [math]\{s_0, s_1\}\!\,[/math] [math]\{s_0\}\!\,[/math]
[math]S_1\!\,' = \{s_0, s_1\}[/math] [math]\{s_0, s_1\}\!\,[/math] [math]\{s_0, s_2\}\!\,[/math]
[math]S_2\!\,' = \{s_0, s_2\}[/math] [math]\{s_0, s_1, s_3\}\!\,[/math] [math]\{s_0\}\!\,[/math]
[math]S_3\!\,' = \{s_0, s_1, s_3\}[/math] [math]\{s_0, s_1\}\!\,[/math] [math]\{s_0, s_2\}\!\,[/math]

Daraus leitet sich die Menge der Finalzustände [math]F\!\,' = \{S_3'\}[/math] ab, da nur [math]S_3\!\,' = \{s_0, s_1, s_3\}[/math] den Finalzustand [math]s_3\!\,[/math] des Ausgangsautomaten enthält. Insgesamt ergibt sich der deterministische Automat [math]\mathcal{A} = (Q', \Sigma, \delta', s_0', F')[/math], der folgende graphische Darstellung besitzt:

Automat zum regulären Ausdruck a(a|b)*b

NEA für den regulären Ausdruck [math]a(a|b)^*b\!\,[/math]
δ' a b
[math]S_0' = \{s_0\}\!\,[/math] [math]\{s_1\}\!\,[/math] [math]\emptyset[/math]
[math]S_1' = \{s_1\}\!\,[/math] [math]\{s_1\}\!\,[/math] [math]\{s_1,s_2\}\!\,[/math]
[math]S_2' = \{s_1,s_2\}\!\,[/math] [math]\{s_1\}\!\,[/math] [math]\{s_1,s_2\}\!\,[/math]
[math]0 = \emptyset[/math] [math]\emptyset[/math] [math]\emptyset[/math]
DEA für den regulären Ausdruck [math]a(a|b)^*b\!\,[/math]

Siehe auch


Kategorien: Compilerbau | Automatentheorie

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Potenzmengenkonstruktion (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.