Тілдер мен автоматтар теориясы



жүктеу 1.65 Mb.
бет1/3
Дата25.04.2016
өлшемі1.65 Mb.
  1   2   3
: arm -> upload -> umk
umk -> Әдістемелік нұсқаудың титулдық парағы
umk -> Дәрістердің тірек конспектісі
umk -> Ф со пгу 18. 2/05 Қазақстан Республикасының білім және ғылым министрлігі
umk -> Пән бойынша оқыту бағдарламасының (Syllabus) титулдық парағы
umk -> БАҒдарламасы (Syllabus) pkya 2204 «Кәсіби қазақ тілі»
umk -> Бейнелеу өнерін оқыту әдістемесі» пәні бойынша 5В107000– «Бейнелеу өнері және сызу мамандығының студенттеріне арналған пәнді зерттеу әдістемесі арналған тапсырма
umk -> Лекционный комплекс
umk -> 1 Пәннің мақсаты мен міндеттері, және оқу үрдісінде алатын орны Пәннің мақсаты
umk -> ЖҰмыс бағдарламасы қазақ журналистикасының тарихы 5В050400 «Журналистика» мамандығының студенттеріне арналған Павлодар
umk -> Әдістемелік ұсыныстар мен нұсқаулардың; әдістемелік ұсыныстардың; әдістемелік нұсқаулардың титул парағы

ФФСО ПГУ 7.18.2/05

љаза›стан Республикасы Білім жЩне “ылым министрлігі
С. Торай“ыров атында“ы Павлодар мемлекеттік университеті
Физика, математика жЩне а›паратты› технологиялар факультеті
Информатика жЩне а›паратты› жЇйелер кафедрасы


ТІЛДЕР МЕН АВТОМАТТАР ТЕОРИЯСЫ

пЩні бойынша зертханалы› ж±мыстарды орындау“а арнал“ан Щдістемелік н±с›аулар


Павлодар

ФФСО ПГУ 7.18.2/05


  1. БЕКІТЕМІН

  2. ФМж/еАТ факультетініЈ деканы

___________ С.К.Тлеукенов

200 __ ж. «___»____________


љ±растырушы: Доцент Джарасова Г.С.
Информатика жЩне а›паратты› жЇйелер кафедрасы

050602 «Информатика» маманды“ыныЈ студенттері Їшін


«Тілдер мен автоматтар теориясы» пЩні бойынша зертханалы› ж±мыстар“а Щдістемелік н±с›аулар

Кафедра мЩжілісінде бекітілді, 200__ж. «___»____________ Хаттама №_____.


  • Кафедра меЈгерушісі _________________________ Н±рбекова Ж.љ.

ФакультеттіЈ Щдістемелік кеЈесінде ›±пталды,


200__ж. «___»____________ Хаттама №_____.

  • ШК тйрайымы _________________________ А.Т.Кишубаева


1 -2 зертханалы› ж±мыс. Толы› автоматтардыЈ эквиваленттілігі мен минимизациясы. Дербес автоматтар жЩне олардыЈ минимизациясы.

Ма›саты: Студентерді ба“дарламаны кезеЈмен ›±ру“а Їйрету
5.1 љыс›аша теориялы› мЩліметтер

Кнут – Моррис – Пратта алгоритмі (КМП)




Оларды оЈнан сол“а, Щріппен Щріпті ›арастырамыз, сонымен ›оса натурал сандардыЈ массивін толтырамыз , онда = сйз ±зынды“ы (l функциясы йткен пункте аны›тал“ан).

Сйзбен: сйз басынын ±зынды“ы , бір уа›ытта оныЈ соЈы болып келеді.

Б±л барлы“ы ба“ыЈын›ы сйзді іздестіруге ›андай ›атысы бар? Бас›а сйзбен айт›анда, сйзі сйзініЈ ба“ыЈ›ысы болады ма, соны аны›тау Їшін КМП алгоритмін ›олданамыз.

Шешімі. КМП алгоритмін сйзіне ›олданайы›, - арнайы Щріп, немесе кездеспейді. сйзі сйзініЈ ба“ыЈ›ысы болып келгенде “ана,сандар арасында массиві сйзініЈ ±зынды“ына теЈ болады.


Мысалы

кестені толтыру алгоритмін жазыЈыз.

Шешімі. I бірінші ма“ынасы табыл“ан деп есептейі. Біз сйздін кезекті Щріпін о›имыз (т.е. ) жЩне есептеуміз керек .

--------------------------------------------------------
| x | | о›ыл“ан бйлігі
--------------------------------------------------------
\-----------Z-----------/ \------------Z------------/
Бас›а сйзбен айт›анда, сйзініЈ бас жа“ы бізге керегі , Оны соЈы болып табылады – оныЈ ішінен еЈ ±зыныЈ таЈдауымыз керек. Б±л басталымдыр ›айдан алын“ан. Шр ›айсысы (босты санама“анда ) кейбір сйзінен Щріптерін ›ос›анда. пайда болады. сйзі сйздін басы жЩне ая› жа“ы болып келеді. Біра›та сйздіЈ басы мен ая“ы болып келетін сйздер келе бермейді, одан кейін Щріпі т±ру керек.

сйзін табу жолы пайда болады. Алдымен барлы› сйздердіЈ басын ›арастырайы›, сол уа›ытта ол олардыЈ ая› жа“ы болып табылады. ОлардыЈ ішінен Щріпінен кейін т±ратын сйзді таЈдайы›. љажеттініЈ ішінен еЈ ±зыныЈ таЈдайы›. ЕЈ соЈына жаз“анда, ізделетін сйзді аламыз.
Енді айт›андардыЈ бЩрін тйменде ›арастырайы›.

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

Берілген массивтердіЈ элементтері ішінен Щр тЇрлі сандарын табыЈыз. тЩртібіндегі Щрекеттер саны.

Шешімі. Сандарды с±рыптап, ал сосын Щр тЇрлі сандарды есептеу керек (тЩртіп бойынша массив элементтерін ›арап).
Тапсырма 5

кесіндісі берілген тура максималды табыЈыз, для которого существует точка прямой, кесіндісімен жабыл“ан, тура нЇктесі бар ("›абаттардыЈ максималды саны").

Шрекеттер саны - тЩртібінде.

Шешімі. КесінділердіЈ барлы› сол жа› жЩне оЈ жа› ая› жа›тарын белгілейік (сол тЇзу нЇктесінде орналас›ан, сол жа› ая› жа“ы оЈ жа“ына ›ара“анда ›ыс›а болып келеді). Ары ›арай солдан оЈ“а ›арай жылжып, ›абаттар саныЈ есептейміз. Кездескен сол жа› соЈы ›абаттар саныЈ 1-ге арттырады,ал оЈ жа› азайтады. Белгілейік, бір біріне жа›ын келген кесінділер д±рыс йЈделеді: еЈ бірінші сол жа› соЈы келеді (оЈ жа› кесіндініЈ), ал сосын оЈ жа› (сол жа› кесіндініЈ).
Тапсырма 6

Жазы›ты›та n нЇктелері берілген.



- сын“ан бекітілмеген йздігінен ›иыспа“ан тЇйінді белгілеЈіз, барлы› нЇктелерден йтетін. (Кйршілес кесінділерге бір тЇзу сызы›та жату“а болады) тЩртібіндегі Щрекеттер саны.
Тапсырма 7

Сол есеп, егерде сын“ан бекітілген болса.


Тапсырма 8

жазы›ты“ында“ы нЇктелер берілген. ОлардыЈ дйЈес ›аптамасын ›±рыЈыз- минималды дйЈес фигурасы бар. (Резенке са›ина, та›тай“а шегеленген шегелерге киілген – олардыЈ дйЈес ›аптамасы.) Операциялар саны .кем емес

Н±с›аулы›тар. НЇктелерді реттейік – алда“ы екі есепте ›олдан“ан тЩртіптер келе береді. Сосын, нЇктелерді кезегімен ›арастырайы›.љарастырыл“ан нЇктелердіЈ дйЈес ›аптамасын ›±рамыз (дйЈес ›аптаманы са›тау Їшін деректер тЇрлері туралы 6 тарауда“ы ›араЈыз).


Ба›ылау с±ра›тары
1 -грамматикасында ›андай атрибуттар ›олданылады?

2 Атрибут дегеніміз не?

3 љандай тарату грамматиканы - атрибутты› грамматика немесе -грамматикасы деп атайды?

3-4 зертханалы› ж±мыс. Шекті ай›ындауыштар. Формальды тілдер жЩне грамматикалар. Орын ауыстырулар. Жиынты›тар. Айырулар
Ма›саты: Студенттерді деЈгей бойынша ба“дарлама ›±руын Їйрету
1.1љыс›аша теориялы› мЩліметтер

Формалды› тіл мен грамматиканы аны›тау“а ›ажет ал“аш›ы жЩне еЈ жай тЇсінік болып алфавит пен алфавиттегі сйздер табылады.

СимволдардыЈ б±л ›арастыруда бйлінбейтін соЈ“ы жиыны сйздік немесе алфавит деп, ал жиын“а жататын символдар - алфавит Щріптері деп аталады.

Мысалы, Щрбіреуі екі символдан т±ратын алфавиті 5 Щріпті ›±райды, ал алфавиті 4 Щріпті ›±райды.

Алфавит ЩріптерініЈ реті б±л алфавиттегі сйз немесе шынжыр деп аталады. Сйздегі Щріптер саны жиыныныЈ ±зынды“ы деп аталады. Бос шынжыр – б±л бірді-бір Щріпі жо› шынжыр. ОЈ жа›тан немесе сол жа›тан шынжырына кез келген бос шынжырдыЈ ›осылуы шынжырын йзгертпейді

алфавитініЈ символдарынан ›±рыл“ан барлы› мЇмкін шынжыр жиындарын аны›тау Їшін белгісі ›олданылады.

формалды грамматика деп келесі тйрт объектініЈ жиынты“ы аталады: м±нда - терминалды› алфавит (сйздік); б±л алфавиттіЈ Щріптерін терминалды› символ дейді; олардан грамматиканы тудыратын шынжыр ›±рылады; терминалды› сйздік немесе терминалды› символ Щріптерін белгілеуді Щрі ›арай латын алфавитініЈ Щріптерімен белгілейтінімізді атап кетейік;

– терминалды› емес, кймекші алфавит (сйздік); б±л алфавиттіЈ Щріптері шынжыр ›±руда ›олданыла алады; олар аралы› шынжыр“а кіре алады, біра› ›±ру нЩтижесіне кіргізілмейді; терминалды› емес символдарды белгілеу Їшін латын алфавитініЈ жазба Щріптерінен т±ратын жЩне б±рышты› жа›шалар“а алын“ан идентификаторларды ›олданатынымызды атап кетейік; - грамматикасыныЈ бастап›ы символы немесе аксиомасы- .

шы“ару ережелерініЈ жиыны немесе тЇрініЈ ережелерін тудыру жиыны, б±нда жЩне , алфавитініЈ Щріптерінен ›±рыл“ан шынжырлар6 олар грамматикасыныЈ толы› алфавиті (сйздік) деп аталады.

Грамматика ережелерініЈ жиынына сондай-а› тЇрініЈ оЈ жа“ы бос ережелер де кіреді. ЕреженіЈ оЈ жа“ы бос бол“анды›тан, ›ателік тудырмау Їшін бос шынжыр символын тЇрінде белгілейміз. Грамматиканы шы“ару ережесі шынжыр ›±ру Їшін ›олданылады.

- грамматикасыныЈ ережесі жЩне символдар шынжыры, о“ан ›оса. Онда шынжыры (я“ни -де шынжырын  ауыстыру) ережесініЈ кймегімен шынжырдан алынуы мЇмкін. Б±л жа“дайда шынжырынан тікелей шы“арыл“ан жЩне білдіреді.

Егер шынжырыныЈ жиынты“ы берілгенде келесі шы“адыонда м±ндай реттік ›атарды грамматикасында –дан шы“ару деп атап, белгілейді.



грамматикасыныЈ терминалды› алфавитініЈ соЈ“ы шынжыр жиынын ал“аш›ы символынан шы“арамыз, ол грамматикасынан тЇ“ан тіл деп аталып, былайша белгіленеді.


1мысал грамматикасы берілген,

грамматикасы тудыратын тілді аны›тау ›ажет.

 Грамматика схемасында бір 5 “ана ереже бар, сонды›тан бір сйзінен “ана т±ратын тілді тудырады.

 

2 мысал

грамматикасы берілген, жЩне осы граммата тудыратын тілді аны›тау ›ажет.

 

Берілген грамматикада“ы барлы› тЇйіндерді ›±райы›. Оны екі Щдіспен істеуге болады. Алдымен 1, 2, 4 ережелерін ›олданамыз, ал содан соЈ 1 жЩне 3 ережелерін ›олданып екінші тЇйінді ›±рамыз.


НЩтижесінде

аламыз.

Я“ни б±л грамматика тудыратын тіл екі шынжырынан т±рады.


3 мысал

  грамматикасы берілген, жЩне осы граммата тудыратын тілді аны›тау ›ажет.



Келтірілген грамматика схемасыныЈ Їш ережесі бар. ЕреженіЈ оЈ жЩне сол жа› бйлігінде екінші ереженіЈ терминалды емес символы бар.Сондай ережелерді рекурсивті деп атайды. Терминалды емес нЇктесін белгілі бір тізбеде ›олдану, жаЈа Їлгідегі нЇктені алу“а мЇмкіндік береді. Сонымен ереженіЈ оЈ жа› бйлігініЈ терминалды емес нЇктесініЈ орнын бірнеше рет ауыстыру“а болады,ол Щр тЇрлі ±зын тізбектерді жасау“а мЇмкіндік береді. Рекурсивті ережені ›олдануда“ы нЩтиже шексіз болмау Їшін, грамматика тізбесінде оЈ жа“ында символы бар бір ереже болу керек. Осындай ереже рекурсияны ая›тап, йткізілген тізбектен нЇктесін алып тастайды. љарастырыл“ан грамматикада нЩтижені ая›тау Їшін ережесі ›олданылады. грамматикалы› ережелер кймегімен нЩтижелерді ›±растырып кйрейік. Бірінші жЩне Їшінші ережелерді ›олдан“анда, мынаны аламыз: .

Бірінші, екінші жЩне содан кейін Їшінші ережені ›олдан“анда, шы“атын нЩтиже:

Екінші ережесін бір рет ›олдан“анда, нЩтижесінде нйлдер жЩне бірліктері бар тізбекшелер аламыз. грамматикасын тудыратын тілде мЇмкіндігінше тізбекшелері бар болады, онда нйлдер саны бірліктер санына теЈ.

 

1Тапсырма

Екі толы› ауыспалыны аламыз.Ба“дарлама кесіндісін ›±растырыЈыз, оны орында“анннан кейін ауыспалымныЈ ма“ынасы орындарымен йзгеріске тЇсу Їшін (жаЈа ма“ына ескі ма“ынасына теЈ, керісінше ).

 Шешілімљосымша толы›  ауыспалымды енгіземіз



љосымшаныЈ ауыстырылымсыз болу мЇмкіндігі, жазамыз

ма›сат›а жеткізбейді ( ауыстырылымныЈ бастап›ы ма“ынасы айтарылымсыз жойылады)

Алдын“ы есепті шеш, ›осымша ауыстырылымдарды ›олданбай (толы› ауыстырылымдар ма“ынасы деп еркін толы› сандарды атаймыз.)


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   2   3


©netref.ru 2017
әкімшілігінің қараңыз

    Басты бет