Die Potenzmengenkonstruktion Myhill Konstruktion oder auch Teilmengenkonstruktion ist ein Verfahren das einen nichtdeterministischen endlichen Automaten NEA in einen aquivalenten deterministischen endlichen Automaten DEA umwandelt Das Verfahren dient als konstruktiver Beweis fur die Aquivalenz der beiden Automatenmodelle Inhaltsverzeichnis 1 Grundidee 2 Theoretischer Rahmen 3 Konstruktion 4 Formales 5 Beispiele 5 1 Automat zum regularen Ausdruck a b aba 5 2 Automat zum regularen Ausdruck a a b b 6 Siehe auchGrundidee BearbeitenDie Zustande des konstruierten deterministischen Automaten DEA sind Mengen von Zustanden des nichtdeterministischen Automaten NEA Ein Zustand vom DEA kodiert dabei all diejenigen Zustande in denen sich der aquivalente nichtdeterministische Automat NEA zu einem bestimmten Zeitpunkt befinden konnte Ein Zustandsubergang im DEA ist deterministisch da sein Folgezustand aus der Menge aller moglichen Folgezustande besteht in die ein NEA unter einer bestimmten Eingabe gelangen kann Das Verfahren heisst Potenzmengenkonstruktion weil die Zustande des konstruierten Automaten Mengen von Zustanden 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 BearbeitenDie Wissenschaftler Michael O Rabin und Dana Scott wurden 1976 fur 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 konnen wird ein Algorithmus konstruiert der jedem NEA einen aquivalenten DEA zuweist Konstruktion BearbeitenZu einem nichtdeterministischen Automaten N A Q S d q 0 F displaystyle mathcal NA Q Sigma delta q 0 F nbsp konstruiere einen aquivalenten deterministischen Automaten A Q S d q 0 F displaystyle mathcal A Q Sigma delta q 0 F nbsp folgendermassen Starte mit leeren Zustandsmengen Q displaystyle Q nbsp und F displaystyle F nbsp Wahle den Startzustand q 0 displaystyle q 0 nbsp von A displaystyle mathcal A nbsp als einelementige Menge q 0 q 0 displaystyle q 0 q 0 nbsp des Startzustandes q 0 Q displaystyle q 0 in Q nbsp von N A displaystyle mathcal NA nbsp Fuge q 0 displaystyle q 0 nbsp zur Menge der Zustande Q displaystyle Q nbsp hinzu Fur alle Zustande q displaystyle q nbsp die bereits in Q displaystyle Q nbsp enthalten sind Fur jedes Eingabezeichen s S displaystyle s in Sigma nbsp Konstruiere einen Folgezustand q displaystyle q nbsp als Menge aller Zustande die N A displaystyle mathcal NA nbsp ausgehend von einem Zustand aus q displaystyle q nbsp unter Eingabe von s displaystyle s nbsp erreichen kann Also q d r s r q displaystyle q bigcup delta r s r in q nbsp Fuge den Zustand q displaystyle q nbsp zu Q displaystyle Q nbsp hinzu falls er noch nicht in der Menge der Zustande von A displaystyle mathcal A nbsp enthalten ist Erganze die Ubergangsfunktion d displaystyle delta nbsp um den Ubergang d q s q displaystyle delta q s q nbsp Wiederhole Schritt 3 so lange bis sich Q displaystyle Q nbsp und d displaystyle delta nbsp nicht mehr andern Wahle die Menge der Finalzustande F displaystyle F nbsp von A displaystyle mathcal A nbsp als diejenige Teilmenge von Q displaystyle Q nbsp deren Zustande einen Finalzustand aus F displaystyle F nbsp enthalten Bemerkung A displaystyle mathcal A nbsp kann am Ende bis zu 2 Q displaystyle 2 Q nbsp Zustande haben Dies ist aber unvermeidlich weil Sprachen existieren z B 0 1 0 0 1 n displaystyle 0 1 0 0 1 n nbsp die von einem NEA mit n 2 displaystyle n 2 nbsp Zustanden akzeptiert werden die aber 2 n 1 displaystyle 2 n 1 nbsp Myhill Nerode Aquivalenzklassen haben womit ein aquivalenter DEA mindestens 2 n 1 displaystyle 2 n 1 nbsp Zustande haben muss Formales BearbeitenSei A Q S d s F displaystyle A left Q Sigma delta s F right nbsp ein nichtdeterministischer endlicher Automat mit der Zustandsmenge Q displaystyle Q nbsp dem Eingabealphabet S displaystyle Sigma nbsp der Ubergangsfunktion d Q S ϵ P Q displaystyle delta colon Q times Sigma cup epsilon to mathcal P Q nbsp dem Startzustand s displaystyle s nbsp und der Menge der Finalzustande F displaystyle F nbsp Seien weiterhin E Q P Q displaystyle E Q rightarrow mathcal P Q nbsp so dass q Q q E q displaystyle forall q in Q q in E q nbsp und r E q p E q r d p ϵ displaystyle r in E q Leftrightarrow exists p in E q r in delta p epsilon nbsp der ϵ displaystyle epsilon nbsp Abschluss eines Zustands unter d displaystyle delta nbsp s E s displaystyle s E s nbsp der ϵ displaystyle epsilon nbsp Abschluss von s displaystyle s nbsp unter d displaystyle delta nbsp d P Q S P Q displaystyle tilde delta mathcal P Q times Sigma to mathcal P Q nbsp mit d q a E r p q r d p a displaystyle tilde delta q a bigcup E r p in q r in delta p a nbsp Q P Q displaystyle Q subseteq mathcal P Q nbsp so dass Q displaystyle Q nbsp die kleinste Menge ist mit s Q displaystyle s in Q nbsp und q Q a S d q a Q displaystyle forall q in Q forall a in Sigma tilde delta q a in Q nbsp d Q S Q d d Q S displaystyle delta colon Q times Sigma to Q delta tilde delta mid Q times Sigma nbsp F q Q q F displaystyle F Big q in Q q cap F neq emptyset Big nbsp Daraus ergibt sich der zu A displaystyle A nbsp aquivalente deterministische endliche Automat A displaystyle A nbsp als A Q S d s F displaystyle A left Q Sigma delta s F right nbsp Beispiele BearbeitenAutomat zum regularen Ausdruck a b aba Bearbeiten Gegeben sei der nichtdeterministische Automat N A s 0 s 1 s 2 s 3 S d s 0 s 3 displaystyle mathcal NA Big s 0 s 1 s 2 s 3 Sigma delta s 0 s 3 Big nbsp uber dem Alphabet S a b displaystyle Sigma a b nbsp mit der tabellarisch gegebenen Ubertragungsrelation d displaystyle delta nbsp d a bs 0 displaystyle s 0 nbsp s 0 s 1 displaystyle s 0 s 1 nbsp s 0 displaystyle s 0 nbsp s 1 displaystyle s 1 nbsp displaystyle emptyset nbsp s 2 displaystyle s 2 nbsp s 2 displaystyle s 2 nbsp s 3 displaystyle s 3 nbsp displaystyle emptyset nbsp s 3 displaystyle s 3 nbsp displaystyle emptyset nbsp displaystyle emptyset nbsp Eine graphische Darstellung des Ausgangsautomaten sieht folgendermassen aus nbsp Nach obiger Konstruktion ergeben sich die Zustandsmenge Q S 0 S 1 S 2 S 3 displaystyle Q S 0 S 1 S 2 S 3 nbsp und die Ubertragungsfunktion d displaystyle delta nbsp des aquivalenten deterministischen Automaten wie folgt d a bS 0 s 0 displaystyle S 0 s 0 nbsp s 0 s 1 displaystyle s 0 s 1 nbsp s 0 displaystyle s 0 nbsp S 1 s 0 s 1 displaystyle S 1 s 0 s 1 nbsp s 0 s 1 displaystyle s 0 s 1 nbsp s 0 s 2 displaystyle s 0 s 2 nbsp S 2 s 0 s 2 displaystyle S 2 s 0 s 2 nbsp s 0 s 1 s 3 displaystyle s 0 s 1 s 3 nbsp s 0 displaystyle s 0 nbsp S 3 s 0 s 1 s 3 displaystyle S 3 s 0 s 1 s 3 nbsp s 0 s 1 displaystyle s 0 s 1 nbsp s 0 s 2 displaystyle s 0 s 2 nbsp Daraus leitet sich die Menge der Finalzustande F S 3 displaystyle F S 3 nbsp ab da nur S 3 s 0 s 1 s 3 displaystyle S 3 s 0 s 1 s 3 nbsp den Finalzustand s 3 displaystyle s 3 nbsp des Ausgangsautomaten enthalt Insgesamt ergibt sich der deterministische Automat A Q S d s 0 F displaystyle mathcal A Q Sigma delta s 0 F nbsp der folgende graphische Darstellung besitzt nbsp Automat zum regularen Ausdruck a a b b Bearbeiten nbsp NEA fur den regularen Ausdruck a a b b displaystyle a a b b nbsp d a bS 0 s 0 displaystyle S 0 s 0 nbsp s 1 displaystyle s 1 nbsp displaystyle emptyset nbsp S 1 s 1 displaystyle S 1 s 1 nbsp s 1 displaystyle s 1 nbsp s 1 s 2 displaystyle s 1 s 2 nbsp S 2 s 1 s 2 displaystyle S 2 s 1 s 2 nbsp s 1 displaystyle s 1 nbsp s 1 s 2 displaystyle s 1 s 2 nbsp 0 displaystyle 0 emptyset nbsp displaystyle emptyset nbsp displaystyle emptyset nbsp nbsp DEA fur den regularen Ausdruck a a b b displaystyle a a b b nbsp Siehe auch BearbeitenPotenzautomat Abgerufen von https de wikipedia org w index php title Potenzmengenkonstruktion amp oldid 234016858
