Algoritmul lui Thompson

De la Wikipedia, enciclopedia liberă
Sari la navigare Sari la căutare

Î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).

Algoritmul[modificare | modificare sursă]

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ă q0, care nu este accesibilă din nicio altă stare. Adică, pentru orice stare q și orice simbol o, nu conține q0.
  • A are exact o stare finală qf, din care nu se poate ajunge în nicio altă stare. Adică, pentru orice simbol a, .
  • 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 2sc (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[modificare | modificare sursă]

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

Thompson-epsilon.svg

Un simbol a din alfabetul de intrare este convertit la

Thompson-a-symbol.svg

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

Thompson-or.svg

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

Thompson-concat.svg

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

Thompson-kleene-star.svg

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[modificare | modificare sursă]

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[modificare | modificare sursă]

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 ε.

Small-thompson-example.svg

Aplicarea algoritmului[modificare | modificare sursă]

AFN obținut din expresia regulată (0|(1(01*(00)*0)*1)*)*

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.

DFA example multiplies of 3.svg

Relația cu alți algoritmi[modificare | modificare sursă]

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[modificare | modificare sursă]

  1. ^ Ken Thompson (). „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. (). A taxonomy of finite automata construction algorithms (PDF) (Technical report). Eindhoven University of Technology⁠(d). Computing Science Report 93/43. 
  5. ^ R. McNaughton, H. Yamada (). „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)