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 die Zustandsmengen der Automaten A und B und sei A ein Potenzautomat von B. Dann ist .
Siehe auch
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.