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.
bet4/5
Sana19.06.2023
Hajmi271.88 Kb.
#1611711
1   2   3   4   5
Bog'liq
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:

j

0

1

2

3

4

5

pat.charAt(J)

A

B

A

B

A

C

A

1




3




5




B




2




4







C
















6

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:


Download 271.88 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling