Potenzautomat
aus Wikipedia, der freien Enzyklopädie
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 die Zustandsmengen der Automaten A und B und sei A ein Potenzautomat von B. Dann ist .
