Nicht deterministischer endlicher Automat

Erweiterung des DKA bei dem die Übergänge nicht eindeutig sind. Ein NEA kann mehrere Startzustände. NEAs unterstützen $ϵ$-Übergänge. Das heißt es kann ein Übergang ohne Eingabe stattfinden.