NFA -> DFA immer möglich ?

Wissenschaft Informatik
#1

Hi,

die Menge aller endlicher Automaten ist gleich der Menge aller nicht-deterministischer Automaten. Eine Teilmenge davon ist die Menge der deterministischen Automaten. Heisst das, dass es nicht-deterministische Automaten gibt, die man nicht in einen deterministischen überführen kann (mit Hilfe der Potenzmengenkonstruktion) ?

Grüße,

Tris

#2

Hallo,
nein bei endlichen Automaten klappt diese Konstruktion immer. Die Aussage bezieht sich sicher darauf, daß jeder DFA auch als NFA angesehen werden kann bzw. das die Abbildung DFA -> NFA hochgradig trivial ist.

Gruss
Enno