Thompson-Konstruktion
Algorithmus zur Konvertierung von regulären Ausdrücken in nichtdeterministische endliche Automaten
From Wikipedia, the free encyclopedia
Die Thompson-Konstruktion (auch englisch Thompson's Construction), eingeführt 1968 durch den Informatiker Ken Thompson, ist in der theoretischen Informatik ein algorithmisches Verfahren, mit dem man in der Lage ist, für jeden regulären Ausdruck systematisch einen nichtdeterministischen endlichen Automaten zu bestimmen[1][2]. Der modulare Algorithmus arbeitete rekursiv und der erstellte Automat akzeptiert so genau die gleiche Sprache wie der reguläre Ausdruck.
Ein anderes Verfahren mit dem gleichen Ziel ist das Berry-Sethi-Verfahren, auch Gluschkow-Konstruktion genannt.