Potenzautomat

Ein Potenzautomat ist ein Begriff der theoretischen Informatik.

Man benutzt Potenzautomaten insbesondere als Hilfsmittel zur Transformation nichtdeterministischer endlicher Automaten in deterministische endliche Automaten. In der Regel sind Potenzautomaten nicht minimal, das heißt sie enthalten viele redundante oder nicht erreichbare Zustände. Sie bilden daher meist einen Zwischenschritt bei der Konstruktion deterministischer endlicher Automaten.

Definition

Ein endlicher Automat A heißt Potenzautomat des endlichen Automaten B, wenn seine Zustandsmenge gerade die Potenzmenge der Zustandsmenge von B ist. Formal ausgedrückt:

Seien Z_A,Z_B die Zustandsmengen der Automaten A und B und sei A ein Potenzautomat von B. Dann ist $Z_A = \mathcal{P}(Z_B)$.

Siehe auch

• Potenzmengenkonstruktion