Algoritmul lui Thompson
From Wikipedia, the free encyclopedia
În informatică, algoritmul lui Thompson este un algoritm de transformare a unei expresii regulate într-un automat finit nedeterminist(d) (AFN) echivalent. Acest AFN poate fi folosit pentru a valida șiruri de caractere(d) cu expresia regulată inițială.
Expresiile regulate și automatele finite nedeterministe sunt două reprezentări de limbaje formale. De exemplu, utilitarele de procesare de text(d) utilizează expresiile regulate pentru a descrie căutări după șabloane avansate, dar AFN-urile sunt mai potrivite pentru execuție pe un calculator. Prin urmare, acest algoritm este de interes practic, deoarece poate compila expresii regulate într-un AFN. Din punct de vedere teoretic, acest algoritm face parte din demonstrația faptului că ambele acceptă exact aceleași limbaje, limbajele regulate.
Un AFN poate fi făcut determinist prin construcția prin părți(d) și apoi poate fi minimizat(d) pentru a obține un automat optim corespunzător cu o expresie regulată dată. Cu toate acestea, un AFN poate fi și interpretat direct(d).