Wikipedia · einfach zusammengefasst · Stand
Potenzautomat
Ein endlicher Automat A heißt Potenzautomat des endlichen Automaten B, wenn seine Zustandsmenge gerade die Potenzmenge der Zustandsmenge von B ist. Formal …
Potenzautomat
Ein Potenzautomat ist ein Begriff der theoretischen Informatik. Er dient insbesondere als Hilfsmittel, um einen nichtdeterministischen endlichen Automaten in einen deterministischen endlichen Automaten umzuwandeln. Dabei bildet der Potenzautomat meist nur einen Zwischenschritt.
In der Regel ist ein Potenzautomat nicht minimal. Das bedeutet, dass er viele redundante oder nicht erreichbare Zustände enthalten kann. Nach seiner Konstruktion müssen deshalb gegebenenfalls Zustände entfernt oder zusammengefasst werden.
Formal gilt: Ein endlicher Automat A heißt Potenzautomat des endlichen Automaten B, wenn die Zustandsmenge von A genau der Potenzmenge der Zustandsmenge von B entspricht. Sind Z_A und Z_B die Zustandsmengen der Automaten A beziehungsweise B, so lautet die Definition:
Z_A = 𝒫(Z_B).
Die Zustände von A bestehen somit aus allen Teilmengen der Zustandsmenge von B.
