Mavzu : matnda qidiruv algoritimini tahlil qilish

A. 0 holatdan 1 holatga o’tdi. Qidiruv yakunlandi. 1 holatga o’tgani uchun string topilgan hisoblanadi.
AA. A: 0 holatdan 1 holatga o’tdi. A: 1 holatda istalgan belgi bo’lishi mumkin bo’lgani bois, 1 holatda qoldi.
BAC. B: 0 holatda qoldi, sababi 1 holatga faqat birinchi belgi A bo’lgandagina o’tadi.
DBCA. D: 0 holatda qoldi, sababi 1 holatga faqat birinchi belgi A bo’lgandagina o’tadi.
Yana bir misol. ABABAC pattern uchun DFA yasashimiz kerak.
DFA holatlari 0 dan 6gacha bo’ladi. Ideal holatda, ABABAC uchun 6-holatga yetib kela oladi.

Jadval ko’rinishida:

Matnda pattern mos kelmagan holatlardachi?

0-holatdan 1-holatga faqat A bo’lsagina o’tadi. Aks holda 0-holatda qoladi. Demak tekshirilayotgan birinchi belgi B yoki C bo’lsa, birinchi holatda qoladi.
1-holatdan 2-holatga faqat B bo’lsagina o’tadi. Agar A bo’lsa, 1-holatida qoladi, sababi pattern’ga ko’ra, biz uchun birinchi belgi A bo’lishi kerak. C bo’lsa, 0-holatga qaytadi – qidiruv patt[0] dan boshlanadi.
2-holatdan 3-holatga faqat A bo’lsagina o’tadi. Agar B,C bo’lsa, 0-holatga qaytadi.
3-holatdan 4-holatga faqat B bo’lsagina o’tadi. Agar A bo’lsa, 1-holatiga qaytadi; C bo’lsa, 0-holatga qaytadi.
4-holatdan 5-holatga faqat A bo’lsagina o’tadi. Agar B,C bo’lsa, 0-holatga qaytadi.
5-holatdan 6-holatga faqat C bo’lsagina o’tadi. Agar B bo’lsa 4-holatga qaytadi, sababi 5-holatga ko’ra, qidiruvda patternning dastlabki 5 belgisi mos kelgan hisoblanadi, ya’ni qidirilayotgan matnda ABABA allaqachon bor. Keyingi belgi C bo’lishi kerak edi, ammo B chiqdi (ABABAB). Biz avvalgi mos kelgan harflarni bilar ekanmiz, qidiruvni 0-holatdan emas, 4-holatdan, ABABAB holatidan davom ettiramiz. A chiqsa, 1-holatga qaytadi.
6-holatga kelganda qidiruv to’xtaydi, biz matn ichidan patternni topgan bo’lamiz.
Yuqoridagi shartlarni graph ko’rinishida ifodalasak:

Jadval ko’rinishida:

Bizda quyidagi matn mavjud: AABACAABABACAA
Pattern esa yuqorida ko’rib o’tganimiz: ABABAC
Matn ichidan patternni topishimiz kerak bo’lsin. Qidiruvni 0-holatdan boshlaymiz.

Pattern topildi. Qidiruv tugaydi.

Holatlarning o’zgarishini graph va jadvalga qarab boshqatdan ko’rib chiqishingiz mumkin.