Algoritmul lui Thompson
În informatică, algoritmul lui Thompson este un algoritm de transformare a unei expresii regulate într-un Format:Ill-wd (AFN) echivalent. Acest AFN poate fi folosit pentru a Format:Ill-wd cu expresia regulată inițială.
Expresiile regulate și automatele finite nedeterministe sunt două reprezentări de limbaje formale. De exemplu, utilitarele de Format:Ill-wd 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 Format:Ill-wd și apoi poate fi Format:Ill-wd pentru a obține un automat optim corespunzător cu o expresie regulată dată. Cu toate acestea, un AFN poate fi și Format:Ill-wd.
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ă Format:Math, care nu este accesibilă din nicio altă stare. Adică, pentru orice stare q și orice simbol o, nu conține Format:Math.
- 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ă Format:Math, Format:Math, a și ε. Atunci, numărul de stări ale lui A este Format:Math (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 Format:Math, 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
(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.
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, Format:Ill-wd transformă un automat finit într-o expresie regulată.
Algoritmul lui Glușkov este similar celui al lui Thompson, cu eliminarea ε-tranzițiilor.
Referințe
- ↑ Format:Cite journal
- ↑ Format:Cite web
- ↑ Format:Ill-wd, Ravi Sethi, Format:Ill-wd: Compilers: Principles, Techniques and Tools.
- ↑ Format:Cite techreport
- ↑ Format:Citat revistă