Tizimli dasturlash Mavzu: Deterministik bo'lmagan va deterministik avtomat Reja

O'ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI

Tizimli dasturlash

Mavzu: Deterministik bo'lmagan va deterministik avtomat

Reja:

• 1. Avtomatlar nazariyasi haqida tushuncha
• 2. Deterministik chekli avtomat
• 3. Nodetermisitik chekli avtomat.
• 4. Deterministik va deterministic bo’lmagan avtomatlar farqi

Avtomatlar nazariyasi -abstrak mashinalar va avtomatlarni , shuningdek, ular yordamida hal qilinishi mumkin bo'lgan hisoblash muammolarini o'rganish. Bu nazariy kompyuter fanidagi nazariya . Avtomat so'zi yunoncha aὐtsomos so'zidan olingan bo'lib, "o'z-o'zidan harakat qiladigan, o'z xohishi bilan harakat qiladigan" degan ma'noni anglatadi. Avtomat (avtomat ko'plikda) - oldindan belgilangan ketma-ketlikni avtomatik ravishda bajaradigan abstrak o'ziyurar hisoblash qurilmasi. Cheklangan sonli holatlarga ega bo'lgan avtomat chekli avtomat yoki chekli holat mashinasi deb ataladi.

Hisoblash DCHA bir bo'limi, deterministik chekli avtomat ( DFA ) - deterministik chekli akseptor ( DFA ), deterministik chekli holat mashinasi ( DFSM ) yoki deterministik chekli holat avtomati ( DFSA ) - - chekli holatli mashina bo'lib, u berilgan belgilar qatorini faqat satr bilan aniqlangan holat ketma-ketligi bo'ylab ishlash orqali qabul qiladi yoki rad etadi . [1] Deterministikhisoblash ishining o'ziga xosligini bildiradi. Uorren Makkallok va Uolter Pitts chekli holatli mashinalarni suratga olishning eng oddiy modellarini izlashda 1943 yilda chekli avtomatlarga o‘xshash kontseptsiyani joriy etgan birinchi tadqiqotchilar qatorida edi 

Nodeterministik chekli avtomat ( NFA ) yoki deterministik bo'lmagan chekli holat mashinasi bu cheklovlarga bo'ysunishi shart emas. Xususan, har bir DFA ham NFA hisoblanadi. Ba'zida ingliz tilida NFA atamasi tor ma'noda qo'llaniladi

Epsilonsiz deterministik bo'lmagan chekli avtomatlarga misol. Quyidagi avtomatlar epsilonsiz deterministik bo'lmagan chekli avtomatlarga misoldir.

Yuqoridagi NFA beshta shaklida aniqlanishi mumkin: { {A, B, C, D, E, F}, {a, b, c}, d, A, {D, F} }

• {A, B, C, D, E, F} holatlar to‘plamini bildiradi
• {a, b, c} kirish alifbolari toʻplamini bildiradi
• d o'tish funktsiyasini bildiradi
• A boshlang'ich holatga ishora qiladi
• {D, F} yakuniy holatlar to‘plamini bildiradi

Avtomatlar nazariyasida chekli holatli mashina deterministik chekli avtomat (ingliz tilida “DFA”) deb ataladi , agar uning har bir o'tishi manba holati va kirish belgisi bilan noyob tarzda aniqlanadi va har bir holatga o'tish uchun kirish belgisini o'qish talab qilinadi.

• Kichik to'plamni qurish algoritmidan foydalanib , har bir NFA ekvivalent DFA ga tarjima qilinishi mumkin; ya'ni, bir xil rasmiy tilni taniydigan DFA . [1] DFAlar singari, NFAlar ham faqat oddiy tillarni taniydilar.
• NFA'lar 1959 yilda Maykl O. Rabin va Dana Skott tomonidan kiritilgan , ular ham DFA'larga tengligini ko'rsatdilar. NFAlar muntazam iboralarni amalga oshirishda qo'llaniladi : Tompson konstruktsiyasi - bu NFAga muntazam ifodani kompilyatsiya qilish algoritmi bo'lib, u satrlarda naqsh moslashtirishni samarali amalga oshiradi. Aksincha, Kleene algoritmi NFA ni muntazam ifodaga aylantirish uchun ishlatilishi mumkin (uning hajmi kirish avtomatida odatda eksponentdir).

NFA ko'p usullarda umumlashtirildi, masalan, e-harakatlari bilan deterministik bo'lmagan chekli avtomatlar , chekli holat transduserlari , pastga tushiruvchi avtomatlar , o'zgaruvchan avtomatlar , ō-avtomatlar va ehtimollik avtomatlari . DFAlardan tashqari, NFAlarning boshqa ma'lum maxsus holatlari aniq chekli avtomatlar va o'z-o'zini tekshiradigan chekli avtomatlar .

• NFA ko'p usullarda umumlashtirildi, masalan, e-harakatlari bilan deterministik bo'lmagan chekli avtomatlar , chekli holat transduserlari , pastga tushiruvchi avtomatlar , o'zgaruvchan avtomatlar , ō-avtomatlar va ehtimollik avtomatlari . DFAlardan tashqari, NFAlarning boshqa ma'lum maxsus holatlari aniq chekli avtomatlar va o'z-o'zini tekshiradigan chekli avtomatlar .

Foydalanilgan adabiyotlar:

• 1. https://www.gatevidyalay.com internet sahifa
• 2. https://en.wikipedia.org internet sahifa
• 3. Кревский И.Г., Селиверстов М.Н., Григорьева К.В. Формальные языки, грамматики и основы построения трансляторов: Учебное пособие/Под.ред А.М.Бершадского-Пенза: Изд-ство Пенз.гос.ун-та,2002 -124с.
• 4. Афанасьев А.Н. Формальные языки и грамматики: Учебная школа: УлГТУ, 1997. – 84 с