Algoritmul lui Thompson

În informatică, algoritmul lui Thompson este un algoritm de transformare a unei expresii regulate într-un automat finit nedeterminist (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.

Algoritmul

Algoritmul se aplică recursiv prin divizarea unei expresii în subexpresiile sale constituente, din care se poate construi AFN-ul folosind un set de reguli.^[1] Mai precis, de la o expresie regulată E, automatul obținut A cu ajutorul funcției de tranziție δ respectă următoarele proprietăți:

A are exact o stare inițială $q 0$ , care nu este accesibilă din nicio altă stare. Adică, pentru orice stare q și orice simbol o, $\delta (q,a)$ nu conține $q 0$ .
A are exact o stare finală q_f, din care nu se poate ajunge în nicio altă stare. Adică, pentru orice simbol a, $\delta (q_{f},a)=\emptyset$ .
Fie c numărul de concatenări ale expresiei regulate E și s numărul de simboluri cu excepția parantezelor — adică $|$ , $*$ , a și ε. Atunci, numărul de stări ale lui A este $2 s - c$ (liniar în dimensiunea lui E).
Numărul de tranziții care ies din orice stare este de cel mult două.
Deoarece un AFN cu m stări și cel mult e tranziții de la fiecare stare poate valida un șir de lungime n, într-un timp $O (emn)$ , un AFN Thompson poate efectua aplicarea șablonului în timp liniar, presupunând un alfabet de mărime fixă.^[2]

Reguli

Următoarele reguli sunt descrise potrivit Aho et al. (1986),^[3] p. 122. N(s) și N(t) sunt AFN-ul asociat subexpresiilor s și, respectiv, t.

Expresia vidă ε este convertită la

Un simbol a din alfabetul de intrare este convertit la

Expresia reuniune (alternanță) s|t este convertită la

Din starea q se trece prin ε fie la starea inițială a lui N(s), fie la cea a lui N(t). Stările lor finale devin stări intermediare în întreg AFN-ul și se reunesc prin intermediul a două ε-tranziții în starea finală al AFN-ului.

Expresia concatenare st este convertită la

Starea inițială a lui N(s) este starea inițială a întregului AFN. Starea finală a lui N(s) devine starea inițială a lui N(t). Starea finală a lui N(t) este starea finală a întregului AFN.

Expresia închidere Kleene s^* este convertită la

O ε-tranziție conectează starea inițială și starea finală a AFN-ului cu sub-AFN-ul N(s) dintre ele. O altă ε-tranziție de la starea finală interioară la starea inițială interioară a lui N(s) permite repetarea expresiei s în funcție de operatorul Kleene star.

Expresia paranteză (s) este convertită la N(s).

Exemplu

Aici se prezintă două exemplu, unul mic și informal doar cu rezultatul, și unul mai mare cu o aplicare pas cu pas a algoritmului.

Exemplul mic

Imaginea de mai jos arata rezultatul rulării algoritmului Thompson pe expresia (ε|a*b). Ovalul roz oval corespunde lui a, cel turcoaz corespunde lui a*, cel verde corespunde lui b, cel portocaliu corespunde lui a*b, și cel albastru corespunde lui ε.

Aplicarea algoritmului

Ca un alt exemplu, imaginea arată rezultatul algoritmului Thompson aplicat pe expresia regulată (0|(1(01*(00)*0)*1)*)* care reprezintă un set de numere binare care sunt multipli de 3: { ε, "0", "00", "11", "000", "011", "110", "0000", "0011", "0110", "1001", "1100", "1111", "00000", ... }.

Partea din dreapta sus arată structura logică (arborele de sintaxă) de exprimare, unde "." reprezintă concatenarea (presupusă a avea aritate variabilă); subexpresiile sunt numite a-q pentru referință. Partea stângă arată automatul finit nedeterminist care rezultă din algoritmul lui Thompson, cu stările entry (inițială) și exit (finală) a fiecărei astfel de subexpresii colorate în magenta și, respectiv, cyan. ε ca etichetă a tranziției este omis pentru claritate — tranzițiile neetichetate sunt, de fapt, ε-tranziții. Stările de intrare și ieșire corespunzătoare expresiei rădăcină q sunt starea inițială și, respectiv, finală a automatului.

Pașii algoritmului sunt după cum urmează:

q:	începe conversia expresei închidere Kleene									`(0\|(1(01(00)0)1))*`
	b:	începe conversia expresiei reuniune								`0\|(1(01(00)0)1)`
		a:	convertește simbolul							`0`
		p:	începe conversia expresiei închidere Kleene							`(1(01(00)0)1)`
			d:	începe conversia expresiei concatenare						`1(01(00)0)*1`
				c:	convertește simbolul					`1`
				n:	începe conversia expresiei închidere Kleene					`(01(00)0)*`
					f:	începe conversia expresiei concatenare				`01(00)0`
						e:	convertește simbolul			`0`
						h:	începe conversia expresiei închidere Kleene			`1*`
							g:	convertește simbolul		`1`
						h:	încheie conversia expresiei închidere Kleene			`1*`
						l:	începe conversia expresiei închidere Kleene			`(00)*`
							j:	începe conversia expresiei concatenare		`00`
								i:	convertește simbolul	`0`
								k:	convertește simbolul	`0`
							j:	încheie conversia expresiei concatenare		`00`
						l:	încheie conversia expresiei închidere Kleene			`(00)*`
						m:	convertește simbolul			`0`
					f:	încheie conversia expresiei concatenare				`01(00)0`
				n:	încheie conversia expresiei închidere Kleene					`(01(00)0)*`
				o:	convertește simbolul					`1`
			d:	încheie conversia expresiei concatenare						`1(01(00)0)*1`
		p:	încheie conversia expresiei închidere Kleene							`(1(01(00)0)1)`
	b:	încheie conversia expresiei reuniune								`0\|(1(01(00)0)1)`
q:	încheie conversia expresiei închidere Kleene									`(0\|(1(01(00)0)1))*`

Un automat determinist minim echivalent este afișat mai jos.

Relația cu alți algoritmi

Algoritmul lui Thompson este unul din multiplii algoritmi pentru construirea de AFN-uri din expresii regulate;^[4] un algoritm mai vechi fusese dat de McNaughton și Yamada.^[5] Spre deosebire de cel al lui Thompson, algoritmul lui Kleene^⁠(d) transformă un automat finit într-o expresie regulată.

Algoritmul lui Glușkov este similar celui al lui Thompson, cu eliminarea ε-tranzițiilor.

Referințe

^ Ken Thompson (1968). „Programming Techniques: Regular expression search algorithm”. Communications of the ACM. 11 (6): 419–422. doi:10.1145/363347.363387.
^ Xing, Guangming. „Minimized Thompson NFA” (PDF).
^ Alfred V. Aho^⁠(d), Ravi Sethi, Jeffrey Ullman^⁠(d): Compilers: Principles, Techniques and Tools.
^ Watson, Bruce W. (1995). A taxonomy of finite automata construction algorithms (PDF) (Raport tehnic). Eindhoven University of Technology^⁠(d). Computing Science Report 93/43.
^ R. McNaughton, H. Yamada (1960). „Regular Expressions and State Graphs for Automata”. IEEE Transactions on Electronic Computers. 9 (1): 39–47. doi:10.1109/TEC.1960.5221603. Mai multe valori specificate pentru |DOI= și |doi= (ajutor)

[1] Ken Thompson (1968). „Programming Techniques: Regular expression search algorithm”. Communications of the ACM. 11 (6): 419–422. doi:10.1145/363347.363387.

[2] Xing, Guangming. „Minimized Thompson NFA” (PDF).

[3] Alfred V. Aho^⁠(d), Ravi Sethi, Jeffrey Ullman^⁠(d): Compilers: Principles, Techniques and Tools.

[4] Watson, Bruce W. (1995). A taxonomy of finite automata construction algorithms (PDF) (Raport tehnic). Eindhoven University of Technology^⁠(d). Computing Science Report 93/43.

[5] R. McNaughton, H. Yamada (1960). „Regular Expressions and State Graphs for Automata”. IEEE Transactions on Electronic Computers. 9 (1): 39–47. doi:10.1109/TEC.1960.5221603. Mai multe valori specificate pentru |DOI= și |doi= (ajutor)

[1]

[2]

[3]

[4]

[5]