Algoritm haqda tushuncha
AA. A: 0 holatdan 1 holatga o’tdi. A: 1 holatda istalgan belgi bo’lishi mumkin bo’lgani bois, 1 holatda qoldi. BAC
Download 271.88 Kb.
|
2-modul Muhammadiyev Sherxon mustaqiil ish algooritm
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, 6-holatga kelganda qidiruv to’xtaydi, biz matn ichidan patternni topgan bo’lamiz. Yuqoridagi shartlarni graph ko’rinishida ifodalasak: Jadval ko’rinishida:
Download 271.88 Kb. Do'stlaringiz bilan baham: |
Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling
ma'muriyatiga murojaat qiling