Thompson-Konstruktion

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.

• Nichtdeterministischer endlicher Automat
• Deterministischer endlicher Automat

1. ↑ Karin Haenelt: Überführung regulärer Ausdrücke in endliche Automaten. In: Fraunhofer Institut. 25. April 2009, abgerufen am 25. Juni 2025. 
2. ↑ Ken Thompson: Programming Techniques: Regular expression search algorithm. Hrsg.: Communications of the ACM,. Band 11, Nr. 6, Juni 1968.