Minimale endliche Automaten

Minimale endliche Automaten

Ein minimaler endlicher Automat hat höchstens so viele Zustände wie jeder anderer endliche Automat der dieselbe Sprache erkennt.

Minimale endliche Automaten können durch Minimierung eines gegebenen endlichen Automaten, der die gewünschte Sprache erkennt, konstruiert werden. Dies geht über die Aufdeckung äquivalenter Zustände, die zusammegefasst werden, damit wirklich nur eine minimale Anzahl an Zuständen vorhanden sind.