Endliche Automaten und reguläre Sprachen

Reguläre Sprachen / Ausdrücke und endliche Automaten

Die regulären Sprachen bilden eine Teilmenge der Sprachen, die von endlichen Automaten erkannt werden können. Da sich reguläre auch, etwas anders, als reguläre Ausdrücke darstellen lassen bzw. Definieren lassen, ist die Formulierung eines endlichen Automaten auf Grundlage dieses regulären Ausdrucks meist intuitive. Jenachdem wie der reguläre Ausdruck aussieht, muss entweder einen nichtdeterministischen Automaten konstruieren, oder man kann sofort den deterministischen Automaten als Akzeptor aller Wörter, die durch den regulären Ausdruck gebildet werden können, konstruieren. Es gilt jedoch, dass die regulären Sprachen sich nicht von den Sprachen sowohl nichtdeterministischer als auch deterministischer endlicher Automaten unterscheiden:

Lregulär=LEA=LnEA