Regular Expression algoritmiga o’tishdan avval NFA – Nondeterministic Finite Automaton abstrakt hisoblash mashinasi haqida tanishib chiqish kerak bo’ladi.
KMP algoritmida biz DFA – Deterministic Finite Automaton‘ni ko’rib chiqqan edik. DFA abstrakt hisoblash mashinasi faqat aniq berilgan pattern’dagi belgilarni tekshirib, agar belgi mos kelsagina keyingi holatga o’tadi (yoki mos kelmagan shartdagi holatga o’tadi). Regular expressions (regexp) aslida birnecha xil pattern’larning qisqacha ifodalanishi bo’lib, uning aniq bir patterni uchun ham DFA yasash mumkin. Masalan, AB*A regexp ichidagi ABBBA pattern uchun DFA yasasa bo’ladi. Yoki teskarisi, istalgan DFA uchun albatta RegExp mavjud. Ushbu teorema – Kleene teoremasi deb ataladi.
Endi bilimlarni umumlashtirib olamiz:
- DFA faqat bitta pattern’ni tekshiradi.
- Istalgan regexp ichida kamida bitta DFA bor.
- regexp’ga qarab birnecha DFA yasash mumkin.
Savol, regexp asosida birnecha xil DFA yasash mumkin ekan, ularni birlashtirib bitta abstrakt mashina yasash mumkinmi?
Ha, mumkin. Ammo amaliyotda DFAning holatlari juda ham (eksponental tarzda) ko’payib ketadi. Tasavvur qilish uchun, [A-Za-z] regexp’da boshlang’ich state’dan (holatdan) 52ta o’tish sharti bor (A..Z 26 harf + a..z 26 harf = 52 harf-holat), va bu holatlar matndagi har bir belgini tekshirish uchun kerak.
Ammo ko’zlangan natijaga NFA – nondeterministic finite automaton abstrakt mashinasini yasab erishish mumkin.
Nondeterministic finite automaton
Nondeterministic finite automaton (NFA) regular expression asosidagi abstrakt hisoblash mashinasi bo’lib, u quyidagicha qoidalar asosida yasaladi:
- regexp qavsga olinadi
- har bir regexp belgisi bitta state deb hisoblanadi
- qizil (epsilon) o’tish (transition) – state’ni o’zgartiradi lekin belgini tekshirmaydi.
- qora o’tish (transition) – state’ni o’zgartiradi va keyingi belgini tekshiradi.
- matnning barcha belgilarini tekshirgandan keyin abstrakt mashina ohirgi – accept state‘ga kelsa, regexp asosida substring topilgan hisoblanadi.
Masalan bizda (A*B|AC)D regexp bor bo’lsin. U asosida NFA yasaymiz.
- regexpni qavs ichiga olamiz: ((A*B|AC)D)
- har bir belgini alohida state deb olamiz.
- berilgan regexp’ga qarab epsilon va qora transition’larni berib chiqamiz.
- so’nggiga accept state qo’shamiz.
Yasalgan NFAni simulyatsiya qilib tekshirish mumkin. Biz quyida ikki regexp’ni simulyatsiya qilib ko’ramiz.
AAAABD:
- 0-state’dan 1 ga o’tadi.
- 1-state’dan 2 ga (birinchi path) va 6 ga (ikkinchi path) o’tadi.
- 2-dan A lar tugaguncha 2-state’dan 3 ga, keyin yana 2 ga qaytib aylanib turadi.
- 3-state’dan 4-state – B ga, keyin 5 ga o’tadi.
- 5 dan 8 ga o’tadi.
- D chiqqani uchun 8 dan 9 ga o’tadi.
- 9 dan 10 ga, keyin accept state’da to’xtaydi.
- Ikkinchi path – 6-state’da A ni topib keyin 7-state’ga o’tadi va C ni tekshiradi. AC ketma-ketligi chiqmagani uchun 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 uchun accept state’ga kelish kerakligi bois, o’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 bo’yicha o’zgartirardik, sababi DFAda aniq bir path’dan ketilardi. NFAda turli xil path’lardan ketish mumkin, bunda biz qaysi yo’ldan borishni qanday aniqlaymiz? Yana ham qizig’i – NFAni kodda qanday ifodalaymiz?
Bu haqida keyingi maqolada gaplashamiz.