Satz zur Sprache von DEAs und nDEAs

Satz zur Sprache deterministischer und nichtdeterministischer endlicher Automaten

Zu jedem nichtdeterministischen endlichen Automaten existiert ein deterministischer endlicher Automaten, so dass beide genau die selbe Sprache erkennen. Umgekehrt gilt dass auch, zu jedem deterministischen endlichen Automaten existiert ein endlicher nichtdeterministischer endlicher Automat der genau dieselbe Sprache wie der deterministische endliche Automat erkennt.