W i l l k o m m e n   b e i   [ www.mauspfeil.com ]
 
 



 

Wörterbuch der Bedeutung
<<Zurück
Bitte wählen Sie einen Buchstaben:
A, Ä | B | C | D | E | F | G | H | I | J | K | L | M | N | O, Ö | P | Q | R | S | T | U, Ü | V | W | X | Y | Z | 0-9

Suchen:

(Groß-/Kleinschreibung wird nicht unterschieden)

Google


Potenzmengenkonstruktion

*** Shopping-Tipp: Potenzmengenkonstruktion

Die '''Potenzmengenkonstruktion''' ('''Myhill-Konstruktion''' oder auch '''Teilmengenkonstruktion''') ist ein Verfahren, das einen nichtdeterministischer endlicher Automat nichtdeterministischen endlichen Automaten NEA in einen äquivalenten deterministischer endlicher Automat 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 von 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 in DEA ist deterministisch, da sein Folgezustand aus der Menge aller möglichen Folgezustände besteht, in die 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 \mathcal{NA} = (Q, \Sigma, \delta, \{q_0\}, F) konstruiere einen äquivalenten deterministischen Automaten \mathcal{A} = (Q', \Sigma, \delta', q_0', F') folgendermaßen: # Starte mit leeren Zustandsmengen Q' und F'. # Wähle den Startzustand q_0' von \mathcal{A} als einelementige Menge q_0' = \{q_0\} des Startzustandes q_0 \in Q von \mathcal{NA}. Füge q_0' zur Menge der Zustände Q' hinzu. # Für alle Zustände q', die bereits in Q' enthalten sind und für jedes Eingabezeichen s \in \Sigma konstruiere einen Folgezustand q'' als Menge aller Zustände, die \mathcal{NA} ausgehend von einem Zustand aus q' unter Eingabe von s erreichen kann. # Füge den Zustand q'' zu Q' hinzu, falls er noch nicht in der Menge der Zustände von \mathcal{A} enthalten ist. # Ergänze die Übergangsfunktion \delta' um den Übergang \delta'(q', s) = q''. # Wiederhole die Schritte 3. bis 5. so lange, bis sich Q' und \delta' nicht mehr ändern. # Wähle die Menge der Finalzustände F' von \mathcal{A} als diejenige Teilmenge von Q', deren Zustände einen Finalzustand aus F enthalten.

Formal
Sei A = \left(Q, \Sigma, \delta, s, F \right) ein nichtdeterministischer endlicher Automat mit der Zustandsmenge Q, dem Eingabealphabet \Sigma, der Übergangsfunktion \delta, dem Startzustand s und der Menge der Finalzustände F. Seien weiterhin :E: Q \rightarrow 2^Q, so dass \forall q \in Q: q \in E(q) und r \in E(q) \Leftrightarrow \exists p \in E(q): \delta(p, \epsilon) = r, der \epsilon-Abschluss eines Zustands unter \delta, :s' := E(s), der \epsilon-Abschluss von s unter \delta, :\delta': 2^Q \times \Sigma \rightarrow 2^Q, so dass \forall a \in \Sigma, q' \in 2^Q: \delta'(q', a) = \Big\{E \big(\delta(p, a)\big) | p \in q' \Big\}, :Q' \subseteq 2^Q, so dass s' \in Q' und \forall q' \in Q', \forall a \in \Sigma: \delta(q', a) \in Q', :F' := \Big\{q' \subseteq Q' | q' \cap F \neq \varnothing \Big\}. Daraus ergibt sich der zu A äquivalente deterministische endliche Automat A' als: :A' = \left\{Q', \Sigma, \delta', s', F' \right\}

Beispiele


Automat zum regulären Ausdruck (a|b)*aba
Gegeben sei der nichtdeterministische Automat \mathcal{NA} = \Big(\{s_0, s_1, s_2, s_3\}, \Sigma, \delta, s_0, \{s_3\} \Big) über dem Alphabet \Sigma = \{a, b\} mit der tabellarisch gegebenen Übertragungsfunktion \delta: :{| class="prettytable" |-- class="hintergrundfarbe6" ! δ !! a !! b |- |s_0 ||\{s_0, s_1\} ||\{s_0\} |- |s_1 ||\varnothing ||\{s_2\} |- |s_2 ||\{s_3\} ||\varnothing |- |s_3 ||\varnothing ||\varnothing |} Eine graphische Darstellung des Ausgangsautomaten sieht folgendermaßen aus: Bild:Nea03.png Nach obiger Konstruktion ergeben sich die Zustandsmenge Q' = \{s_0', s_1', s_2', s_3'\} und die Übertragungsfunktion \delta' des äquivalenten deterministischen Automaten wie folgt: :{| class="prettytable" |-- class="hintergrundfarbe6" ! δ' !! a !! b |- |s_0' = \{s_0\} ||\{s_0, s_1\} ||\{s_0\} |- |s_1' = \{s_0, s_1\} ||\{s_0, s_1\} ||\{s_0, s_2\} |- |s_2' = \{s_0, s_2\} ||\{s_0, s_1, s_3\} ||\{s_0\} |- |s_3' = \{s_0, s_1, s_3\} ||\{s_0, s_1\} ||\{s_0, s_2\} |} Daraus leitet sich die Menge der Finalzustände F' = \{s_3'\} ab, da nur s_3' = \{s_0, s_1, s_3\} den Finalzustand s_3 des Ausgangsautomaten enthält. Insgesamt ergibt sich der deterministische Automat \mathcal{A} = (Q', \Sigma, \delta', s_0', F'), der folgende graphische Darstellung besitzt: Bild:Dea03.png

Automat zum regulären Ausdruck a(a|b)*b
{| Bild:Nea02.png |- | align="center"| NEA mit dem regulären Ausdruck a(a|b)*b |} :{| class="prettytable" |-- class="hintergrundfarbe6" ! !! a !! b |- |S'0 = S0 ||S1 ||0 |- |S'1 = S1 ||S1 ||{S1,S2} |- |S'2 = {S1,S2} ||S1 ||{S1,S2} |- |0 ||0 ||0 |} {| |Bild:Dea02.png |- | align="center"| DEA mit dem regulären Ausdruck a(a|b)*b |}
Kategorie:Automatentheorie Kategorie:Theoretische Informatik Kategorie:Compilerbau en:Powerset_construction

*** Shopping-Tipp: Potenzmengenkonstruktion




[Der Artikel zu Potenzmengenkonstruktion stammt aus dem Nachschlagewerk Wikipedia, der freien Enzyklopädie. Dort findet sich neben einer Übersicht der Autoren die Möglichkeit, den Original-Text des Artikels Potenzmengenkonstruktion zu editieren.
Die Texte von Wikipedia und dieser Seite stehen unter der GNU Free Documentation License.]

<<Zurück | Zur Startseite | Impressum | Zum Beginn dieser Seite