Vom Regulären Ausdruck zum NEA

Durch einen regulären Ausdruck kann eine Sprache einfach beschrieben werden. Um zu prüfen, ob ein Wort in der beschriebenen Sprache ist, ist ein Automat hilfreich, da der direkt in Programmcode oder Hardware umgesetzt werden kann. Zu jedem regulären Ausdruck kann leicht ein nichtdeterminisitischer endlicher Automat induktiv konstruiert werden. Dazu nutzt man Konstruktionen für die Abschlusseigenschaften regulärer Sprachen.