Direkt zum Inhalt

Lexikon der Mathematik: endlicher vollständiger

Automat, ein Automat mit endlich vielen Zuständen, bei dem jeder Zustand bei jedem Eingabezeichen mindestens einen Nachfolgezustand besitzt.

Zu jedem endlichen Automaten kann ein äquivalenter vollständiger konstruiert werden, indem ein neuer Zustand q* eingeführt wird, der kein Endzustand ist. Für alle Zustands-/Eingabepaare ohne Nachfolgezustand wird dann q* als Nachfolgezustand gesetzt. Besonders für deterministische Automaten erleichtert die Vollständigkeit viele Konstruktionen.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos