Potenzmengenkonstruktion
Vorlage:Hinweisbaustein 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
Um für einen NEA <math>N</math> einen äquivalenten DEA <math>D</math> zu konstruieren, werden alle Mengen von Zuständen des NEA <math>N</math> als potentielle Zustände für DEA <math>D</math> betrachtet. Ein Zustand vom DEA <math>D</math> kodiert dabei all diejenigen Zustände, in denen sich der NEA <math>N</math> zu einem bestimmten Zeitpunkt befinden könnte. Ein Zustandsübergang im DEA <math>D</math> ist deterministisch, da sein Folgezustand aus der Menge aller möglichen Folgezustände besteht, in die der NEA <math>N</math> 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 DEA.
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{N} = (Q, \Sigma, \delta, q_0, F)</math> mit der Übergangsfunktion <math>\delta\colon Q\times \Sigma \to \mathcal P(Q)\!\,</math>, konstruiere einen äquivalenten deterministischen Automaten <math>\mathcal{D} = (Q', \Sigma, \delta', q_0', F')</math> folgendermaßen:
- Starte mit leeren Zustandsmengen <math>Q\!\,'</math> und <math>F\!\,'</math>.
- Wähle den Startzustand <math>q_0'</math> von <math>\mathcal{D}</math> als einelementige Menge <math>q_0' = \{q_0\}</math> des Startzustandes <math>q_0 \in Q</math> von <math>\mathcal{N}</math>. Füge <math>q_0'</math> zur Menge der Zustände <math>Q\!\,'</math> hinzu.
- 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{N}</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{D}</math> enthalten ist.
- Ergänze die Übergangsfunktion <math>\delta\!\,'</math> um den Übergang <math>\delta\!\,'(q', s) = q</math>.
- Für jedes Eingabezeichen <math>s \in \Sigma</math>:
- Wiederhole Schritt 3. so lange, bis sich <math>Q\!\,'</math> und <math>\delta\!\,'</math> nicht mehr ändern.
- Wähle die Menge der Finalzustände <math>F\!\,'</math> von <math>\mathcal{D}</math> als diejenige Teilmenge von <math>Q\!\,'</math>, deren Zustände einen Finalzustand aus <math>F\!\,</math> enthalten.
Bemerkung: Der DEA <math>\mathcal{D}</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.
Konstruktion für NEAs mit Epsilon-Übergängen und mehreren Startzuständen
Wir betrachten einen nichtdeterministischen Automaten <math>\mathcal{N} = (Q, \Sigma, \delta, S, F)</math> mit der Übergangsfunktion <math>\delta\colon Q\times (\Sigma\,\cup \{\epsilon\}) \to \mathcal P(Q)\!\,</math> die Epsilon-Übergänge erlaubt und einer Menge <math>S</math> von Startzuständen. Eine Möglichkeit einen äquivalenten DEA zu konstruieren ist es, den gegebenen Automaten zunächst in einen NEA ohne Epsilon-Übergänge mit einem einzelnen Startzustand umzuwandeln und dann das schon vorgestellte Verfahren für solche Automaten anzuwenden. Es ist aber meistens effizienter den gegebenen NEA direkt in einen DEA umzuwandeln. Hierzu definiert man den <math>\epsilon</math>-Abschluss <math>E(q)</math> (manchmal auch die <math>\epsilon\!\,</math>-Hülle) eines Zustands <math>q</math> unter <math>\delta</math> als die Menge aller Zustände die von <math>q</math> mit Epsilon-Übergänge erreicht werden können. Die Konstruktion wird jetzt so modifiziert, dass nur <math>\epsilon</math>-abgeschlossene Mengen als Zustände im Automaten fungieren können, d. h., jeder neue Zustand wird unter <math>\epsilon</math>-Übergängen abgeschlossen und der <math>\epsilon</math>-Abschluss der Menge aller Startzustände fungiert als Startzustand des DEA.
Konstruktion
Konstruiere einen äquivalenten deterministischen Automaten <math>\mathcal{D} = (Q', \Sigma, \delta', q_0', F')</math> folgendermaßen:
- Starte mit leeren Zustandsmengen <math>Q\!\,'</math> und <math>F\!\,'</math>.
- Wähle den Startzustand <math>q_0'=E(S)</math> von <math>\mathcal{D}</math>. Füge <math>q_0'</math> zur Menge der Zustände <math>Q'</math> hinzu.
- 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{N}</math> ausgehend von einem Zustand aus <math>q'\!\,</math> unter Eingabe von <math>s\!\,</math> erreichen kann. Also <math>q := \bigcup\{E(\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{D}</math> enthalten ist.
- Ergänze die Übergangsfunktion <math>\delta\!\,'</math> um den Übergang <math>\delta\!\,'(q', s) = q</math>.
- Für jedes Eingabezeichen <math>s \in \Sigma</math>:
- Wiederhole Schritt 3. so lange, bis sich <math>Q\!\,'</math> und <math>\delta\!\,'</math> nicht mehr ändern.
- Wähle die Menge der Finalzustände <math>F\!\,'</math> von <math>\mathcal{D}</math> als diejenige Teilmenge von <math>Q\!\,'</math>, deren Zustände einen Finalzustand aus <math>F\!\,</math> enthalten.
Formales
Sei <math>\mathcal{N} = \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\,\cup \{\epsilon\}) \to \mathcal P(Q)\!\,</math>, dem Startzuständen <math>S\!\,</math> und der Menge der Finalzustände <math>F\!\,</math>.
Der <math>\epsilon</math>-Abschluss <math>E(q)</math> (manchmal auch die <math>\epsilon\!\,</math>-Hülle) eines Zustands <math>q</math> unter <math>\delta\!\,,</math> ist definiert als
- <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 <math>E(Q)</math> einer Menge von Zuständen <math>Q</math> ergibt sich dann als <math>E(Q) = \bigcup \{E(q)| q \in Q \}</math>.
Der zu <math>\mathcal{N}</math> äquivalente Potenzautomat <math>\mathcal{P}(\mathcal{N}) = \left(P(Q), \Sigma, \tilde\delta, s', \tilde{F} \right)</math> ergibt sich wie folgt:
- <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(\delta(p,a))| p\in q'\},</math>
- <math>\tilde{F} = \Big\{q' \in P(Q) | q' \cap F \neq \emptyset \Big\}.</math>
Dieser Potenzautomat ist bereits ein zu <math>\mathcal{N}</math> äquivalenter DEA aber immer von exponentieller Größe. Durch das Eliminieren von Zuständen die vom Startzustand nicht erreicht werden können ergibt sich der in unserer Konstruktion beschriebene äquivalente DEA <math>\mathcal{D} = \left(Q', \Sigma, \delta', s', F' \right)</math> mit:
- <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>
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 Übergangsrelation <math>\delta\!\,</math>:
| <math>q</math> | <math>\delta(q,a)</math> | <math>\delta(q,b)</math> |
|---|---|---|
| <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 Übergangsfunktion <math>\delta\!\,'</math> des äquivalenten deterministischen Automaten wie folgt:
| <math>q'</math> | <math>\delta'(q',a)</math> | <math>\delta'(q',b)</math> |
|---|---|---|
| <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:
Datei:Deterministischer endlicher Automat 3.png
Automat zum regulären Ausdruck a(a|b)*b
| Datei:Nichtdeterministischer endlicher Automat 2.svg |
| NEA für den regulären Ausdruck <math>a(a|b)^*b\!\,</math> |
| <math>q'</math> | <math>\delta'(q',a)</math> | <math>\delta'(q',b)</math> |
|---|---|---|
| <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> |
| Datei:Dea02.png |
| DEA für den regulären Ausdruck <math>a(a|b)^*b\!\,</math> |
Literatur
- {{#invoke:Vorlage:Literatur|f}}
- {{#invoke:Vorlage:Literatur|f}}
- {{#invoke:Vorlage:Literatur|f}}
- {{#invoke:Vorlage:Literatur|f}}