Mavzu. Chekli avtomat. Deterministik bo'lmagan va deterministik avtomat
Download 407.66 Kb. Pdf ko'rish
|
|
Amaliy ishi - 2 Fan: Tizimlarning matematik va dasturiy ta'minoti O’qtuvchi: Djangazova Kumriniso O’qiuvchi: Sharofiddinov Shaxriyor Guruh: MSS001-1 Mavzu. Chekli avtomat. Deterministik bo'lmagan va deterministik avtomat Cheklangan avtomat, shuningdek, chekli holat mashinasi sifatida ham tanilgan, belgilar yoki holatlar ketma-ketligini tan olish yoki yaratish uchun ishlatiladigan matematik modeldir. Bu chekli holatlar to'plamidan, kirish belgilari yoki alifbosidan, har bir holat va kirish belgisini yangi holatga, boshlang'ich holatiga va yakuniy yoki qabul qiluvchi holatlar to'plamiga moslashtiruvchi o'tish funktsiyasidan iborat oddiy hisoblash modeli. Cheklangan avtomatni kiritish jarayonidagi xatti-harakatlariga ko'ra ikki toifaga bo'lish mumkin: Deterministik chekli avtomat (DFA): DFAda mashina bir vaqtning o'zida faqat bitta holatda bo'lishi mumkin va har bir holatdan har bir kirish belgisi uchun noyob o'tish mavjud. DFA 5-karta (Q, S, d, q0, F) bilan ifodalanishi mumkin, bunda: • Q - chekli holatlar to'plami • S - kirish belgilari yoki alifbosining cheklangan to'plami • d - Q x S dan Q ga o'tish funktsiyasi • q0 - boshlang'ich holat • F - yakuniy yoki qabul qiluvchi holatlar to'plami Non-deterministic Finite Automaton (NFA): NFAda mashina bir vaqtning o'zida bir nechta holatda bo'lishi mumkin va har bir holatdan har bir kirish belgisi uchun bir nechta o'tish bo'lishi mumkin. NFA 5karta (Q, S, d, q0, F) bilan ifodalanishi mumkin, bunda: • Q - chekli holatlar to'plami • S - kirish belgilari yoki alifbosining cheklangan to'plami • d - Q x S dan Q quvvat to'plamiga o'tish funktsiyasi • q0 - boshlang'ich holat • F - yakuniy yoki qabul qiluvchi holatlar to'plami Cheklangan avtomatlar kompyuter fanida, xususan hisoblash nazariyasida, rasmiy til nazariyasida va kompilyator dizaynida keng qo'llaniladi. Ulardan oddiy tillarni tanib olish, muntazam iboralar yaratish, leksik tahlil va naqsh solishtirish va boshqalar uchun foydalanish mumkin. Deterministik chekli avtomat (DFA) chekli avtomat bo'lib, unda har bir holat va kirish belgisi uchun keyingi holatga aynan bitta o'tish mavjud. Boshqacha qilib aytganda, DFA har bir holat va kiritish belgisi kombinatsiyasi uchun o'ziga xos o'tishga ega. Shuning uchun, ma'lum bir kirishni hisobga olgan holda, DFA har doim bir xil holatga o'tadi, bu uni bashorat qilish va amalga oshirishni osonlashtiradi. Mana, 1 bilan tugaydigan {0,1} alifbosidagi barcha satrlar tilini taniydigan deterministik chekli avtomatga misol: Boshqa tomondan, deterministik bo'lmagan chekli avtomat (NFA) ma'lum bir holat va kirish belgisi uchun bir nechta mumkin bo'lgan o'tishlarga ega bo'lishi mumkin yoki u epsilon o'tishlariga ega bo'lishi mumkin (hech qanday kirish belgisini talab qilmaydigan o'tishlar). Bu shuni anglatadiki, ma'lum bir kirishni hisobga olgan holda, NFA bir nechta holatlarga o'tishi yoki hatto tsiklga yopishib qolishi mumkin, bu esa uni oldindan aytib bo'lmaydigan va amalga oshirishni qiyinlashtiradi. Biroq, NFAlar DFA-larga qaraganda ko'proq ifodali bo'lishi mumkin, ya'ni ular DFA-lar qila olmaydigan ba'zi tillarni taniy oladilar. Quyida “101” pastki qatorini oʻz ichiga olgan {0,1} alifbosidagi barcha satrlar tilini taniydigan deterministik boʻlmagan chekli avtomatga misol keltirilgan: Xulosa qilib aytganda, DFAlar deterministik bo'lib, har bir holat va kirish belgisi kombinatsiyasi uchun o'ziga xos o'tishga ega, NFA esa deterministik bo'lmagan va berilgan holat va kirish belgisi yoki epsilon o'tishlari uchun bir nechta mumkin bo'lgan o'tishlarga ega bo'lishi mumkin. Download 407.66 Kb. Do'stlaringiz bilan baham: 
|