Potenzautomat

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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.

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 .