NFA simulyatsiyasi işini körib çiqişdan avval NFAning özini kodda qanday ifodalanişi bilan tanişib çiqamiz. Avvalgi maqolada aytib ötilganidek, NFAda 0 dan M gaça state'lar + accept state mavjud. M - bu yerda qavs içiga olingan regular expression'dagi belgilar soni. Masalan ((A*B|AC)D) regexp uçun NFA state'lari 11 ta (10ta regexp belgi-state + 1 accept state).

NFAning qizil (epsilon) transition'larini esa directed graph körinişida saqlaymiz. Bu bizga state'larni DFSda tekşirib, qaysi path accept state'gaça borişini topiş uçun qulayroq yeçim. Epsilon transition'lar graph'da edge körinişida, state'lar vertex körinişida saqlanadi.

0→1, 1→2, 1→6, 2→3, 3→2, 3→4, 5→8, 8→9, 10→11

Qora (match) transition'lar faqat keyingi element'gagina ulaniş ehtimoli bölgani uçun uni oddiyroq qilib, re[] array'da saqlaymiz. Bunda array elementining indeksi state'ning raqamiga teng böladi. Agar match transition mavjud bölsa, öşa elementning qiymati 1 böladi:

const re = [0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0]

NFA simulyatsiyasi

NFA simulyatsiyasida abstrakt maşinaning qanday işlaşini misol bilan körib çiqamiz. Regexp özgarmagan - ((A*B|AC)D). Biz AABD matnni regexp'ga tekşirişni boşlaymiz.

Siklda dastlab epsilon transition'ga, keyin match transition'ga tekşiriladi.

**1. **Epsilon transition'da qaysi state'larga yetib borişni tekşiramiz. 0-state'dan 1 ga; 1-state'dan 2 ga va 6 ga; 2-state'dan 3 ga; 3-state'dan 2 ga (2 allaqaçon tekşirildi) va 4 ga. Jami 0, 1, 2, 3, 4, 6 state'larga kirdik.

**2. **Matnning birinçi belgisi A, u 2-va 6-state'da bor. Endi match transition'ni re[] array'dan tekşiramiz. Agar re[2] va re[6] qiymatlari 1 ga teng, ya'ni keyingi state'ga black transition bor. 3 va 7-state'ga ötamiz. Demak, birinçi A belgini tekşirganimizdan keyin biz 3 va 7 state'ga keldik.

3. 3 va 7 state'dan epsilon transition'ga tekşiramiz. 3 dan 2 ga va 4 ga epsilon transition bor; 2 dan esa 3 ga epsilon transition bor; 7 dan epsilon transition yöq. Şunday qilib, biz hozir 2, 3, 4 va 7 state'larda turibmiz.

4. Matnning ikkinçi belgisi ham A, u faqat 2-state'da bor. Match transition'ni re[] array'dan tekşiramiz. re[2] qiymati 1 ga teng, ya'ni keyingi state'ga black transition bor. 3-state'ga ötamiz. AA ni tekşirganimizdan keyin biz 3-state'da turibmiz.

5. 3-state'dan epsilon transition'ga tekşiramiz. 3 dan 2 ga va 4 ga epsilon transition bor. 2 dan esa 3 ga epsilon transition bor; Biz hozir 2, 3, 4 state'da turibmiz.

6. Uçinçi belgi - B faqat 4-state'da mavjud. Undan 5 ga match (black) transition bor. 5-state'ga ötamiz. AAB ni tekşirganimizdan keyin biz 5-state'da turibmiz.

7. 5-state'dan 8 ga epsilon transition bor; 8 dan 9 ga epsilon transition bor. Hozir biz 5, 8 va 9-state'da turibmiz.

8. Törtinçi (ohirgi) belgi - D faqat 9-state'da mavjud. 9-state'dan 10-state'ga match transition bor. Şunday qilib, AABD dan keyin biz 10-state'ga keldik.

9. 10-state'dan 11-state'ga epsilon transition bor. Hozir biz 10 va 11-state'da turibmiz. 11-state accept state bölgani uçun simulyatsiyani töxtatamiz.

Xulosa - AABD matni ((A*B|AC)D) regexp uçun mos kelar ekan.

NFA simulyatsiyasini kodda ifodalaş