O’ZBEKISTON RESPUBLIKASI OLIY VA O’RTA -MAXSUS TA’LIM VAZIRLIGI SAMARQAND DAVLAT UNIVERSITETI RAQAMLI TEXNOLOGIYALAR FAKULTETI KAMPYUTER ILIMLARI VA DASTURLASH TEXNOLOGIYALARI YO’NALISHI 20 6-GURUH TALABASI SAYDULLAYEV YAXSHIMURODNING “ALGORITM VA MA’LUMOTLAR STRUKTURASI ” FANIDAN “NFX GRAMATIKASIDAGI TAHLIL QILISH UCHUN COCCO -YOUNGERI -KSSAMI ALGARITMI” MAVZUSIDA TAYYORLAGAN TEKSHIRDI: DJABBAROV A.H. SAMARQAND – 2021

MUNDARIJA . I.bob Kirish … … … … … … … … … … … … … … … … … … … … … … … … … … … 3 II.bob Asosiy qism: … … … … … … … … … … … … … … … … … … … … … … … … 5 2.1. Kontekstsiz gramatika … … … … … … … … … … … … … … … … … … … … .5 2.2. Chomsyening normal shakli … … … … … … … … … … … … … … … … … ..19 III .bob Xu losa … ..… … … … … … … … … … … … … … … … … … … … … … … … 30 IV .bob Foydalanilgan adabiyotlar … … ... .… … … … … … … … … … … … … … ...31

KIRISH Bu kurs ishi binominal koeffitsientlarni o’rganish algoritmini ko ’rib chiqib o’rgandim .Bugungi kunda ma ’lumotlar oqimining ko ’pligi tufayli ularni qisqa vaqt ichidazmashina buyruqlarini o’zida saqlovchi assembler tili yaratildi . Keyinchalik FORTRAN , BASIC , PASKAL va COBOL singari yuqori darajali tillar ham paydo bo ’ldiki , bu tillar yordamida so ’z va gaplarning mantiqiy konstruksiyasidan foydalanib algoritmlash imkoniyati yaratildi . Ular buyruqlarni mashina tiliga interpretatorlar va kompilyatorlar yordamida o’tkazar edi. Algoritmlash tillari yaratilishi bo’yicha uchta turga ajratiladi: -quyi darajadagi; - o’rta darajadagi; -yuqori darajadagi. Ma’lumki, ma’lum bir masalani yechish uchun buyruqlar ketma - ketligi ya’ni algoritm algoritmlash tilida yozi layotganda kamroq buyruqlardan foydalanilsa, bunday tillar darajasi yuqoriroq hisoblanadi. Quyi darajadagi algoritmlash tillari bevosita kompyuter qurilmalari bilan bog’liq bo’lib, buyruqlar ularning kodlari bilan yoziladi. Bu kabi buyruqlardan tashkil top gan algoritmlar katta hajmli bo’lib, ularni taxrirlash katta mehnat talab qiladi. Dastlabki kompyuterlar(ENIAK, MESM va boshqalar) ana shunday tillarda ishlagan. O’rta darajadagi algoritmlash tillari buyruqlarida faqat raqamlar emas, balki insonlar tushuna digan ba’zi so’zlar ishlatila boshlandi(Assemblaer). Yuqori darajadagi algoritmlash tillari quyidagicha bosqichlarga bo’linadi: Algoritmik(Basic, Pascal, C va b.) Mantiqiy(Prolog, Lisp va b.) Obyektga mo‘ljallangan(Object Pascal, C++, Java va b.) Alg oritmlash tillarida yaratilgan algoritmlar mashina tiliga translyatorlar yordamida o’tkaziladi. Translyator(translator -tarjimon) biror bir algoritmlash tilida yozilgan algoritmni mashina tiliga tarjima qiladi. Translyatorlar ikki turda bo’ladi: - Kompilyatorlar(compiler -yig'uvchi) biror bir algoritmlash tilida yozilgan algoritmni mashina tiliga to’liq o’qib olib tarjima qiladi; - Interpretatorlar(interpreter - izohlovchi, og’zaki tarjimon) biror bir algoritmlash

tilida yozilgan algoritmni mashin a tiliga satrma - satr tarjima qiladi. Translyatorlarni bu ikkala turi - bir biridan farq qiladi. Komplyatsiya qilingan algoritmlar birmuncha kam vaqt talab etadi, ya’ni tezroq ishlaydi, lekin interpretatsiya qilingan algoritmlarni o’zgartirish osonroq hi soblanadi. C++ dasturlash tili tarkibida bir nechta imkoniyatlar mavjud, ya’ni consol rejimi, forma ob’yekt rejimi, grafik muhiti va ma’lumotlar bazasi bilan ishlash imkoniyatlari keng joriy etilgan. Ushbu qo’llanmada keltirilgan misol va masalalarning y echimi dasturining int main funksiyasi tarkibini C++ dasturlash tilinining ixtiyoriy versiyalarida ishlatib ko’rish mumkin. Qo’llanma oliy o’quv yurtlari talabalari va magistrantlari, litsey, kasb -hunar kollejlari talabalari hamda mustaqil o’rganuvchilar u chun qulay manba hisoblanadi. Kontekstsiz grammatika ( CS -grammatika , kontekstsiz grammatika ) - rasmiy tilni tavsiflash usuli , bu to 'rtta , bu erda : • - alifbo , uning elementlari terminallar deb ataladi (Eng. Terminals ) • - elementlari noterminallar deb ataladigan to'plam (Ingliz. Nonterminals ) • - grammatikaning boshlang'ich belgisi (inglizcha Boshlash belgisi ) • - xulosa qilish qoidalari to'plami (Eng. A ishlab chiqarish qoidalari yoki ishlab chiqarishlar ) turi , bu erda , ya'ni qaysi chap tomonda - yagona nonterminal, va o'ng - terminallar va nonterminallar ketma -ketligi. Misol Terminallar . S = { ( , ) Noterminallar . N= { S} Pul o'tkazish qoidalari : P S→ e S→ SS S→ ( S) Ushbu grammatika to'g'ri qavs qatorlari tilini belgilaydi . Masalan, ketma - ketlik quyidagicha chiqarilishi mumkin: ( ( ) ( ( ) ) ) S⇒ ( S) ⇒ ( SS) ⇒ ( ( ) ( S) ) ⇒ ( ( ) ( ( ) ) ) Chomsky normal shakli . Chomskiyning normal shakli KS -grammatikaning normal shakli bo'lib, unda barcha mahsulotlar quyidagi shaklga ega:

• A → a bu erda terminal bo'lmagan va terminal AAaa • A → BC Bu erda , , - terminal bo'lmagan va va boshlang'ich noterminal emas ABCBC • S→ e bu erda dastlabki noterminal va bo'sh satr (agar tilda bo'sh qator bo'lsa, bu ishlab chiqarish kerak) Se • Har qanday CS grammatikasini Chomskiyning oddiy shakliga tushirish mumkinligini ko'rsatish mumkin. Vikipediyadan, bepul ensiklopediya Sahifaning joriy versiyasi hali tajribali ishtirokchilar tomonidan ko'rib chiqilmagan va 2016 yil 6 yanvarda ko'rib chiqilgan versiyadan sezilarli darajada farq qilishi mumkin ; tekshiruvlar 10 ta tahrirni talab qiladi . Kontekstga bog'liq grammatika ( KZ -grammatikasi , kontekst grammatikasi ) rasmiy grammatikaning maxsus holatidir ( Xomskiy ierarxiyasi bo'yicha 1 -tur ), unda barcha ishlab chiqarishlarning chap va o'ng qismlari terminal va terminal bo'lmaganlar bilan o'ralgan bo'lishi mumkin. belgilar. Rasmiy grammatikaning alohida holati ham kontekstsiz grammatikadir . KZ -grammatikasi bilan aniqlanishi mumkin bo'lgan til kontekstga bog'liq til yoki KZ tili deb ataladi . Algor itm Algoritm Coca -Younger -Kasami (Engl. Cocke -Younger -Kasami algorithm , Engl. CYK algorithm - ) - algoritm normal shaklda Chomskian oldindan belgilangan kontekstsiz grammatika hosila bo'lsa, so'z topish. Har qanday KS -grammatikani NFH ga qisqartirish mumkin, shuning uchun algoritm har qanday KS -grammatikasi uchun universaldir. Muammoni dinam ik dasturlash orqali hal qilamiz . Bir mag'lubiyatga hisobga hajmi . Keling, buning uchun bir uch o'lchovli qator yaratish hajmi , mantiqiy qiymatlar iborat, va faqat agar agar pastki olingan mumkin bitişte bo'lmagan dan grammar qoidalar yordamida . wnd| N | ×n×d[ A ] [ i ] [ j ] = true Aw [i ... j ] Barcha juftlarni ko'rib chiqing , bu erda doimiy va . { ⟨ J , i ⟩ | j - i = m }<n