Зертханалық жұмыс



жүктеу 0.57 Mb.
бет1/4
Дата25.10.2017
өлшемі0.57 Mb.
  1   2   3   4







ФФСО ПГУ 7.18.2/05



Қазақстан Республикасы Білім және ғылым министрлігі
С. Торайғыров атындағы Павлодар мемлекеттік университеті
Физика, математика және ақпараттық технологиялар факультеті
Информатика және ақпараттық жүйелер кафедрасы


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

пәні бойынша зертханалық жұмыстарды орындауға арналған әдістемелік нұсқаулар


Павлодар








ФФСО ПГУ 7.18.2/05





БЕКІТЕМІН

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

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

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   4


©kzref.org 2019
әкімшілігінің қараңыз

    Басты бет