Regular Expression algoritmiga ötişdan avval NFA - Nondeterministic Finite Automaton abstrakt hisoblaş maşinasi haqida tanişib çiqiş kerak böladi.

KMP algoritmida biz DFA - Deterministic Finite Automaton'ni körib çiqqan edik. DFA abstrakt hisoblaş maşinasi faqat aniq berilgan pattern'dagi belgilarni tekşirib, agar belgi mos kelsagina keyingi holatga ötadi (yoki mos kelmagan şartdagi holatga ötadi). Regular expressions (regexp) aslida birneça xil pattern'larning qisqaça ifodalanişi bölib, uning aniq bir patterni uçun ham DFA yasaş mumkin. Masalan, AB*A regexp içidagi ABBBA pattern uçun DFA yasasa böladi. Yoki teskarisi, istalgan DFA uçun albatta RegExp mavjud. Uşbu teorema - Kleene teoremasi deb ataladi.

Endi bilimlarni umumlaştirib olamiz:

• DFA faqat bitta pattern'ni tekşiradi.
• Istalgan regexp içida kamida bitta DFA bor.
• regexp'ga qarab birneça DFA yasaş mumkin.

Savol, regexp asosida birneça xil DFA yasaş mumkin ekan, ularni birlaştirib bitta abstrakt maşina yasaş mumkinmi?

Ha, mumkin. Ammo amaliyotda DFAning holatlari juda ham (eksponental tarzda) köpayib ketadi. Tasavvur qiliş uçun, [A-Za-z] regexp'da boşlanğiç state'dan (holatdan) 52ta ötiş şarti bor (A..Z 26 harf + a..z 26 harf = 52 harf-holat), va bu holatlar matndagi har bir belgini tekşiriş uçun kerak.

Ammo közlangan natijaga NFA - nondeterministic finite automaton abstrakt maşinasini yasab erişiş mumkin.

Nondeterministic finite automaton

Nondeterministic finite automaton (NFA) regular expression asosidagi abstrakt hisoblaş maşinasi bölib, u quyidagiça qoidalar asosida yasaladi:

• regexp qavsga olinadi
• har bir regexp belgisi bitta state deb hisoblanadi
• qizil (epsilon) ötiş (transition) - state'ni özgartiradi lekin belgini tekşirmaydi.
• qora ötiş (transition) - state'ni özgartiradi va keyingi belgini tekşiradi.
• matnning barça belgilarini tekşirgandan keyin abstrakt maşina ohirgi - accept state'ga kelsa, regexp asosida substring topilgan hisoblanadi.

Masalan bizda (A*B|AC)D regexp bor bölsin. U asosida NFA yasaymiz.

1. regexpni qavs içiga olamiz: ((A*B|AC)D)
2. har bir belgini alohida state deb olamiz.
3. berilgan regexp'ga qarab epsilon va qora transition'larni berib çiqamiz.
4. sönggiga accept state qöşamiz.

Yasalgan NFAni simulyatsiya qilib tekşiriş mumkin. Biz quyida ikki regexp'ni simulyatsiya qilib köramiz.

AAAABD:

• 0-state'dan 1 ga ötadi.
• 1-state'dan 2 ga (birinçi path) va 6 ga (ikkinçi path) ötadi.
• 2-dan A lar tugagunça 2-state'dan 3 ga, keyin yana 2 ga qaytib aylanib turadi.
• 3-state'dan 4-state - B ga, keyin 5 ga ötadi.
• 5 dan 8 ga ötadi.
• D çiqqani uçun 8 dan 9 ga ötadi.
• 9 dan 10 ga, keyin accept state'da töxtaydi.
• Ikkinçi path - 6-state'da A ni topib keyin 7-state'ga ötadi va C ni tekşiradi. AC ketma-ketligi çiqmagani uçun 7-state'da qoladi.

Path'lar:
0 -> 1 -> 2 -> 3 -> 2 -> 3 -> 2 -> 3 -> 2 -> 3 -> 4 -> 5 -> 8 -> 9 -> 10 -> 11
0 -> 1-> 6 -> 7

Biz uçun accept state'ga keliş kerakligi bois, örtada qolib ketgan path'larga ahamiyat bermaymiz.

AAAAC:

Bu regexp'da path 0 -> 1 -> 2 -> 3 -> 2 -> 3 -> 2 -> 3 -> 2 -> 3 -> 4 state'da qolib ketadi. Demak regexp NFAda topilmagan hisoblanadi.

---

DFAda oson edi, state'ni berilgan patternning har bir belgisi böyiça özgartirardik, sababi DFAda aniq bir path'dan ketilardi. NFAda turli xil path'lardan ketiş mumkin, bunda biz qaysi yöldan borişni qanday aniqlaymiz? Yana ham qiziği - NFAni kodda qanday ifodalaymiz?

Bu haqida keyingi maqolada gaplaşamiz.