Тілдер мен автоматтар теориясы
жүктеу/скачать 1.65 Mb.
|
- Бұл бет үшін навигация:
- БЕКІТЕМІН
- Кафедра меЈгерушісі _________________________ Н±рбекова Ж.љ.
ФФСО ПГУ 7.18.2/05 љаза›стан Республикасы Білім жЩне “ылым министрлігі
пЩні бойынша зертханалы› ж±мыстарды орындау“а арнал“ан Щдістемелік н±с›аулар Павлодар
ФФСО ПГУ 7.18.2/05
___________ С.К.Тлеукенов 200 __ ж. «___»____________ љ±растырушы: Доцент Джарасова Г.С. Информатика жЩне а›паратты› жЇйелер кафедрасы 050602 «Информатика» маманды“ыныЈ студенттері Їшін «Тілдер мен автоматтар теориясы» пЩні бойынша зертханалы› ж±мыстар“а Щдістемелік н±с›аулар Кафедра мЩжілісінде бекітілді, 200__ж. «___»____________ Хаттама №_____.
ФакультеттіЈ Щдістемелік кеЈесінде ›±пталды, 200__ж. «___»____________ Хаттама №_____.
1 -2 зертханалы› ж±мыс. Толы› автоматтардыЈ эквиваленттілігі мен минимизациясы. Дербес автоматтар жЩне олардыЈ минимизациясы. Ма›саты: Студентерді ба“дарламаны кезеЈмен ›±ру“а Їйрету 5.1 љыс›аша теориялы› мЩліметтер Кнут – Моррис – Пратта алгоритмі (КМП) 
Оларды оЈнан сол“а, Щріппен Щріпті ›арастырамыз, сонымен ›оса натурал сандардыЈ массивін толтырамыз , онда = сйз ±зынды“ы (l функциясы йткен пункте аны›тал“ан).
Сйзбен: Б±л барлы“ы ба“ыЈын›ы сйзді іздестіруге ›андай ›атысы бар? Бас›а сйзбен айт›анда, Шешімі. КМП алгоритмін Мысалы кестені толтыру алгоритмін жазыЈыз.
Шешімі. I бірінші ма“ынасы --------------------------------------------------------
i:=1; l[1]:= 0; {кесте l[1]..l[i] д±рыс толтырыл“ан} while i <> n do begin | len := l[i] | {len – сйз басыныЈ ±зынды“ы x[1]..x[i], оныЈ соЈы болып келетін | еЈ ±зын басталымдар ›ажет болмай ›алды | } | while (x[len+1] <> x[i+1]) and (len > 0) do begin | | {бас жа“ы келмейді, l функциясын ›олданайы›} | | len := l[len]; | end; | {керектіні таптыЈыз ба немесе жо› екеніне кйзіЈіз жетті ме? } | if x[len+1] = x[i+1] do begin | | {x[1]..x[len] - еЈ ›ажетті ±зын бас жа“ы} | | l[i+1] := len+1; | end else begin | | {›ажеттілері жо›} | | l[i+1] := 0; | end; | i := i+1; end; Тапсырма 1 Жо“арыда келтірілген алгоритмдегі Щрекет Тапсырма 2 Б±л алгоритмді ›олданамыз, Тапсырма 3 СЩйкес алгоритмді жазыЈыз ( Тапсырма 4 Берілген массивтердіЈ элементтері ішінен Щр тЇрлі сандарын табыЈыз. Шешімі. Сандарды с±рыптап, ал сосын Щр тЇрлі сандарды есептеу керек (тЩртіп бойынша массив элементтерін ›арап).
Шрекеттер саны - Шешімі. КесінділердіЈ барлы› сол жа› жЩне оЈ жа› ая› жа›тарын белгілейік (сол тЇзу нЇктесінде орналас›ан, сол жа› ая› жа“ы оЈ жа“ына ›ара“анда ›ыс›а болып келеді). Ары ›арай солдан оЈ“а ›арай жылжып, ›абаттар саныЈ есептейміз. Кездескен сол жа› соЈы ›абаттар саныЈ 1-ге арттырады,ал оЈ жа› азайтады. Белгілейік, бір біріне жа›ын келген кесінділер д±рыс йЈделеді: еЈ бірінші сол жа› соЈы келеді (оЈ жа› кесіндініЈ), ал сосын оЈ жа› (сол жа› кесіндініЈ).
Жазы›ты›та n нЇктелері берілген. - сын“ан бекітілмеген йздігінен ›иыспа“ан тЇйінді белгілеЈіз, барлы› нЇктелерден йтетін. (Кйршілес кесінділерге бір тЇзу сызы›та жату“а болады) тЩртібіндегі Щрекеттер саны.
Тапсырма 7 Сол есеп, егерде сын“ан бекітілген болса. Тапсырма 8 жазы›ты“ында“ы нЇктелер берілген. ОлардыЈ дйЈес ›аптамасын ›±рыЈыз- минималды дйЈес фигурасы бар. (Резенке са›ина, та›тай“а шегеленген шегелерге киілген – олардыЈ дйЈес ›аптамасы.) Операциялар саны .кем емес
Н±с›аулы›тар. НЇктелерді реттейік – алда“ы екі есепте ›олдан“ан тЩртіптер келе береді. Сосын, нЇктелерді кезегімен ›арастырайы›.љарастырыл“ан нЇктелердіЈ дйЈес ›аптамасын ›±рамыз (дйЈес ›аптаманы са›тау Їшін деректер тЇрлері туралы 6 тарауда“ы ›араЈыз). Ба›ылау с±ра›тары 1 -грамматикасында ›андай атрибуттар ›олданылады?
2 Атрибут дегеніміз не? 3 љандай тарату грамматиканы - атрибутты› грамматика немесе Формалды› тіл мен грамматиканы аны›тау“а ›ажет ал“аш›ы жЩне еЈ жай тЇсінік болып алфавит пен алфавиттегі сйздер табылады. СимволдардыЈ б±л ›арастыруда бйлінбейтін соЈ“ы жиыны сйздік немесе алфавит деп, ал жиын“а жататын символдар - алфавит Щріптері деп аталады. Мысалы, Щрбіреуі екі символдан т±ратын Алфавит ЩріптерініЈ реті б±л алфавиттегі сйз немесе шынжыр деп аталады. Сйздегі Щріптер саны Грамматика ережелерініЈ жиынына сондай-а› Егер грамматикасыныЈ терминалды› алфавитініЈ соЈ“ы шынжыр жиынын ал“аш›ы символынан шы“арамыз, ол грамматикасынан тЇ“ан тіл деп аталып, былайша белгіленеді.
1мысал грамматикасы берілген,
грамматикасы тудыратын тілді аны›тау ›ажет.
Грамматика схемасында бір 5 “ана ереже бар, сонды›тан
Берілген грамматикада“ы барлы› тЇйіндерді ›±райы›. Оны екі Щдіспен істеуге болады. Алдымен 1, 2, 4 ережелерін ›олданамыз, ал содан соЈ 1 жЩне 3 ережелерін ›олданып екінші тЇйінді ›±рамыз. НЩтижесінде
аламыз. Я“ни б±л грамматика тудыратын тіл 3 мысал
Келтірілген грамматика схемасыныЈ Їш ережесі бар. ЕреженіЈ оЈ жЩне сол жа› бйлігінде екінші ереженіЈ терминалды емес символы бар.Сондай ережелерді рекурсивті деп атайды. Терминалды емес нЇктесін белгілі бір тізбеде ›олдану, жаЈа Їлгідегі нЇктені алу“а мЇмкіндік береді. Сонымен ереженіЈ оЈ жа› бйлігініЈ терминалды емес нЇктесініЈ орнын бірнеше рет ауыстыру“а болады,ол Щр тЇрлі ±зын тізбектерді жасау“а мЇмкіндік береді. Рекурсивті ережені ›олдануда“ы нЩтиже шексіз болмау Їшін, грамматика тізбесінде оЈ жа“ында символы бар бір ереже болу керек. Осындай ереже рекурсияны ая›тап, йткізілген тізбектен нЇктесін алып тастайды. љарастырыл“ан грамматикада нЩтижені ая›тау Їшін ережесі ›олданылады. грамматикалы› ережелер кймегімен нЩтижелерді ›±растырып кйрейік. Бірінші жЩне Їшінші ережелерді ›олдан“анда, мынаны аламыз: .
Бірінші, екінші жЩне содан кейін Їшінші ережені ›олдан“анда, шы“атын нЩтиже: Екінші
Екі Шешілім. љосымша толы›
љосымшаныЈ ауыстырылымсыз болу мЇмкіндігі, жазамыз
ма›сат›а жеткізбейді ( ауыстырылымныЈ бастап›ы ма“ынасы айтарылымсыз жойылады)
Алдын“ы есепті шеш, ›осымша ауыстырылымдарды ›олданбай (толы› ауыстырылымдар ма“ынасы деп еркін толы› сандарды атаймыз.) 2 Тапсырма Толы› азайту. Ба“дарлама ›±растыру керек, оны орында“анда жЩне ауыстырылымдар ма“ынасы ауыспайды, ал бас›а да ауыстырылымдар ма“ынасы (мысалы) теЈ болады. (Сонымен бас›а да ауыстырылымдарды ›олдану“а болады).
Шешім. :=0; :=1; {b=aвдеЈгейіk} while k <> n do begin |k:=k+1;
|b:=b*a; end;
Алда“ы есепті шеш, егер де орындал“ан операторлар ›абылдауыныЈ ›ызметтік санын тЩртібінде шешу керек, сонды›тан ол аспау керек, кейбір константтары Їшін; -б±л деЈгейге 2-ні енгізу керек, алу Їшін . 3 Тапсырма саннын барлы› орын ауыстырымдарын басыЈыз ( ±зындылы“ыныЈ реттілігін, о“ан 1 саныныЈ Щр ›айсысы бір рет кіреді). Шешім. изгертулерді массиве массивінде са›таймыз жЩне лексикографикалы› тЩртіпте тереміз. ( ауыстырылымы бірінші, ал соЈ“ы болады). Келесі ауыстырылым“а кйшуде алгоритмі ›±растыруда с±ра› туындайды: ›ай жа“дайда алда“ыларды йзгертпегенде ауыстырылымын арттыру“а болады ма? Жауабы: егер де келесі мЇшелерден аз болса ( нймірлері бар мЇшелер кйп). Біз кйбірек –ны аны›тауымыз керек. Ол , . Одан кейін еЈ тйменгі мЇмкіндікпен арттыру керек. арасынан, ..., –ден кйп еЈ тйменгі санды табу керек. - пен ауыстыр“анда, сандарды нймірлермен орналастырамыз, ..., ауыстырылым еЈ тймен болу керек, я“ни йсу тЩртібінде. Келесі ауысым“а кйшу алгоритмы. { <> k:=n-1; { x[k+1] >...> x[n]}тймендегі,k оЈ жа›та“ы реттілік while x[k] > x[k+1] do begin | k:=k-1; end; {x[k] < x[k+1] > ... > x[n]} t:=k+1; {t <=n, кесіндініЈ барлы› мЇшелері x[k+1] > ... > x[t] кйп x[k]} while (t < n) and (x[t+1] > x[k]) do begin | t:=t+1; end; {x[k+1] > ... > x[t] > x[k] > x[t+1] > ... > x[n]} ... x[k] и x[t] ауыстыру {x[k+1] > ... > x[n]} ... x[k+1] ... x[n] кері тЩртіпте орналастыру Ескерту. Ба“дарламада бізге таныс дефект бар: егер , онда аны›талма“ан. Келесі ауыстырылым“а модифицирлан“ан алгоритмды кйшіруде, ол йзі атал“ан ауыстырылым а›ыр“ы емес екенін тексеріп отыру керек. жүктеу/скачать 1.65 Mb. Достарыңызбен бөлісу:
|