Главная | Случайная
Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






Формалды грамматика 5 страница




Вирттің синтаксистік диаграммалары – бұл түзу сызықтар мен біріктірілген блоктарды пайдаланып, тілді графикалық түрде сипаттау. Мұнда терминалдар дөңгелектер көмегі мен, ал терминал ,еместер тікбұрыштар көмегі мен белгіленеді. Бэкус – Наурдың әр құрастырушысы үшін эквиваленттік синтаксисін диаграмма құруға болады

Өзін-өзі тексеру сұрақтары:

1. Программалау тілдерінің даму тарихы?

2. Тілдерді өрнектеу жолдары қандай?

3. Синтаксис, семантика және программалау тілдерінің грамматикасы түсініктеріне тоқталыңыз?

4. Формализациялау проблемалары қандай?

Ұсынылған әдебиеттер:

1.Б. Страуструп Язык программирования. 1991 г Москва

2.Ивани А. Элементы теоритического программирования. Учебное пособие для вузов. М. МГУ. 1985 Г

Дәріс 3. Граматика

Мақсаты:Студенттерді формальды граматика ұғымымен таныстыру, тілдің құрылымын көрсету

Жоспары:

· Формальді грамматика

· Тілдің құрылымы

Формальді грамматика - программалау тіліндегі синтаксисті жазу үшін математикалық аппараттар көптеп қолданылады. Тілдің құрылымы көптеп қолдануы, екінші жағынан, программалардың синтаксистік анализіндегі грамматикаларды алдын алу.

Формальді грамматика шекті көптік ережелер арқылы және екінші сөздік арқылы табылады. Олар генерациялардың процесіндегі тілдің тізбегін жазады.

Бірінші сөздік терминалды сөздік деп аталады және ол тілдің басты символдарынан тұрады, олар формальді грамматикалардың теориясында- терминальді символдар немесе терминальдар деп аталады. Терминальдарды латынның a, b, c,…t әріптерімен белгілейміз, терминальді сөздік ∑ символымен , терминальді символдар тізбегін латынның U, V, W, X, Y, Z ,белгілейді.

Екінші сөздік грамматика- терминальді емес деп аталады және символдардың көмегімен қолданылады. Оны жазғанда латынның бас әріптерімен А, В, С,.......Т белгіленеді. Терминальді емес сөздікте N әріпімен аталады. N сөздікте терминальді емес ерекшеленеді, оны бастапқы символ грамматикасы деп атайды және соңынан S орындалады. Бастапқы символ грамматикада қиылысады көп жағдайда конструкция тілінде жазылады. Терминальді және терминальді емес сөздік грамматикалық сөздік мына формулада толығымен орындалады V=∑UN.

Ілім қатарын аксиомаландырған, олардың логикасын, ішкі құрылымын оқып үйрену – математиканың метатіл ғылымының дамуында математикалық логика маңызды роль атқарды.

Информатиканың, әсіресе оның мынандай бөлімдерінің: формальды тілдер теориясы, грамматикасы, құрылымы, алгоритмдік тілдері және трансляциялау әдісінің мәліметтер қоры және білім деңгейі және тағы басқаларының дамуы, ғылым салаларының дамуына, тереңдетілуіне, орындалуына және құрылымдауына әкеледі. Өз кезегінде, тілдің құрылымдарын модельдеу, формализациялау, байланысу тілдер қатарының құрылымдау, әр түрдегі мәтіндер мен сөздіктердің анализі жәе орналасуы, сонымен бірге, олардың автоматты түрде орналасуы.

Алфавит көмегімен анықталған тіл, Х={ } – бұл қандай да бір ауызша, дыбысты, жазбаша немесе х-ке тәуелді сөздердің берілу түрі, синтаксисті қосқанда, сөздерден және сөз тіркесінен алынатын құрылым тәртібі, семантиканы – дұрыстығын тексеретін ереже, мәнді біртектікті және лексемнен тұратын тілдің қалыбының синтаксистік орналасуы. Ауызша байланыс үшін фонетика – сөйлем мүшелерін дұрыс айту ережесі, яғни, фонем.

Тіл хабар алмасу құралы ретінде берілген алфавитке сай, сөздердің құрылымын анықтау сипаты болу керек. Сөздерден құралған сөйлемдердің грамматикалық тәртібі және синтаксистікәрі семантикалық ережелер бойынша аталатын осы сөйлемдердің сол құбылыстарға және процестерге сай келуі.

Мысал. «бүтін х саны у бүтін санына қалдықсыз бөлінеді» деген фактіні қысқа әрі нақты (дәл) жазайық. Математикалық тілде ол мына түрде беріледі:

«х саны у санынан кіші». х,у – бүтін, жоғарыда айтылғандай, яғни олар факт, аксиома қабылдайтындай, ол математикалық кіші мән.

Енді одан да қысқа әрі дәл түрде алгоритмдік Паскаль тілінде жазайық:

“x mod y=0”.

Мұнда кіші шарты аргументтің өзгеру облысы туралы айтпауға болады – олар Паскаль тілінде ресми жарияланған (mod операциясын айтуда және типтердің атағанда) пайдаланылады.

Табиғи тілдер болады, (мысалы, байланысу тілдері) және жасанды тілдер немесе формалды тілдер, адамдардың компьюермен байланысы үшін жасалынған не болмаса, білім алу үшін және оны атап көрсеті үшін.

Х – қандай да бір алфавит болсын, x={ }, ал S(x) – х алфавитінде сөздердің көптігі, онда S(x) – шексіз және сандық көпмүше.

L(x) формалды тілі - S(x) –тің қайталама көпмүшесі.

Бақылау сұрақтары:

1. Формальді грамматика деген не?

2. Бірінші, екінші сөздік деп нені атайды?

Ұсынылған әдебиеттер:

1.Женон Ф. Языки программирование М.Мир. 1972 г

2.Климова Л.М. Паскал. Практика программирования. М. 2000 г

 

Дәріс 4. Граматиканың классификациясы.

Мақсаты: Граматиканың түрлері және негізгі проблемаларын көрсету.

Жоспары:

Формалды грамматика

2. Грамматикаларды классификациялау: регулярлық, контексті

Формалды тіл табиғи тілді оған кіретін абстрактілі объектінің лексикалық қалыбы ретінде, метатіл немесе басқа тілдердің синтаксисін белгілеу үшін пайдаланылады. Метатілмен жазылған тіл, бұл жағдайда объектілі тіл деп аталады.

G формалды грамматикасы: T={ } – тілдің терминалдық символдарының көпшілігі немесе тілдің негізгі мағынасы тізбектерінен тұрады;

N={ } – бұл терминдік емес символдардың көптігі немесе көмекші ұғымдардың, нақты бір сөздің класын белгілеу, мысалы, етістіктерді немесе жалғауларды, және де N-де N-нің алғашқы символы n болады;

P={ } – бұл s (x) Ì S(X) түрінің s (x) Ì S(X)-ке ауыстыру системасы немесе s (x) қарастырылып отырған s (x) қатынасына ауыстырылуы.

S(x)-тің барлық сөздерін тудыруға мүмкіндік беретін тіл (көбіне сөзі) G(S) – тәртіп құрылымы грамматикасымен беріледі.

Грамматикалық анализ – терминдік емес немесе сөзге бәсеңдеу процесі.

Көпшілік W=N ÈT – G грамматикасының сөздігі. Шығару тәртібі – бұл f,gÎW болғанда f®g болатын тәртіп, ал “®” – бұл түрдің байланысы «сол жақты оңға ауыстыруға болады».

Егер, болғанда, сөзі сөзінен ережесінің көмегімен шығады.

Мысал. Табиғи, мысалы, формалды грамматика терминіндегі орыс тілінің элементтерін жазайық. X={А,а,Б,б, ... , Я, я, ., ,, :, ;, , ., !, ?, “, ”, (, )}, T={<түбірлер>, <рпиставкалар> және т.б.}, N={сөйлем, бастауыш, баяндауыш, етістік, пысықтауыш және т.б.}, n = “сөйлем”.

Операциялардың және операндтардың метатілде оң сандармен жазылған берілуі – тұрақты берілу деп аталады.

Формалды грамматикада үш негізгі проблемалар қарастырылады:

Енгізу проблемасы – берілген грамматикаға сай алгоритм құру және ол сол тілге сай келетінін мүмкіндік береді;

Анализдің проблемасы – әрбір сөз үшін грамматикаға сай алгоритм құру және оның мәнін шығару;

Бағалау проблемасы – алгоритм мәнінің дұрыстығын тексеру шарты.

Егер бірінші екі тапсырмалар көбіне грамматикалық сипатта болса, онда үшінші тапсырма, көбіне «алгоритмдік» сипатта болады.

Компьютердің пайда болуына байланысты, алгоритмнің нақты және құрылымына талаптар қойылады. Бұл мақсатты қанағаттандыру үшін алгоритмдік тілдер өндірілуде. Өзіне математикалық символиканы, мысалы, сандар, операциялы белгілері, айнымалы шамалар, берілулер және т.б. қосатындықтан, бұл формальды тіл, формальданған тіл болып саналады.

5. Грамматикаларды классификациялау: регулярлық, контексті

Грамматикада анықталған 3,2 разрядында a®b-ға шығу ережесінде екеуінің біреуі a тізбегінде терминальды емес болуы керек. Праграммалау тілінің сипаттамасы және оларды оқып білу көбінесе грамматика тілінде қызықты болады және шығару ережесі дәлелдеуді талап етеді

Формальды грамматиканың анықталу облысында [3, 6, 9, 34, 35,48] Хамаскидің классификациясы қабылдайды, грамматиканы ереже түріне байланысты 4 класқа бөледі:грамматиканың түрі және грамматиканың жалпы түрі G=(N, SP, S) бұл грамматика У шығу ережесінің түрінде a®b, ол a V*NV*,ab V* .

Грамматиканың жалпы түрі мәннің қызықтысын қабылдайды, олар тым бос, бұларды программалау тіліндегі синтаксисті жазуда қолдануға болады. Табиғи тілге арналған синтаксисте қолданылады. 0 грамматикалық түрдегі мысал G=( {A, S}, {0,1}, P, S) программасына негіз болады және P={S®0A1, 0A® 00F1,A ®e}.

Бірінші грамматика түрі немесе конспект- тәуелді грамматика бұл G=(N, SP, S) граммтикасы шығу ережесі түрінің g1А g2®g1bg2 одан g1, g2 V,A N,ab V+. Конспект оң және сол жақ g1және g2 аталуы бойынша сәйкестендіріледі және тізбектеледі. Олар шығу ережесінің тапсырмасы бойынша шарт орындалады: конспект g1,g2 тізбектері әр уақытта терминальды емес грамматикада a және b тізбегімен ауыстырылады.

Конспект тәуелді грамматика тілде конспект тәуелді тіл деп те аталады. Грамматикада конспект тәуелді грамматика мен тіл кластарын сәйкестендіреді, оны [9] -бен дәлелдеуге де болады. Ол грамматикада қысқартылмайтын деп те аталады, шығару ережесінің a®b орындау кезінде мына шартты қанағаттандырады½a£½b½.

Демек бұл алгоритмде немесе шекті сандарды анықтау кезінде терминалды тілде не жатады немесе жатпайды. Қысқартылмаған грамматика мына мысалда көрсетілген: G=( {B,C,S} ), {a,b,c},P,S) P={S aS,B,C, S abc; CB BC, bB bb, bC bc, cC cc).

Екінші грамматикалық түрі немесе конспект бос грамматика – бұл G=(N, S,P,S) грамматика шығару ережесінің мынадай түрін береді. А®В , немесе АÎN,abÎV*.

Келесі тіл Конспект тәуелді грамматиканы жеңіл оқиды және толық тексереді, сосын тілден бос тізбек шығады. Шығу ережесін жазғанда Конспект тәуелді грамматикасы лингвистикалық формуламен сәйкес келеді. Нақтырақ айтсақ, конспект тәуелді грамматикада шығу ережесінің терминалды емес грамматикасының сол жақ бөлігі лингвистикалық грамматиканың сол жақ бөлік формасымен сәйкес келеді.

Қатынас (®) - метолингвистикалық байланыста былай белгіленеді: (::=) шығу ережесінің терминалды және терминалды емес тізбектерінің бөлігі – метолингвистикалық формулада екіге бөлінеді: математикалық қоңырау тізбегі және тілдің басты символдарының оң жақ бөлігі.

Үшінші грамматикалық түрі – автоматты және регулярлы грамматика бұл G=(N, S,P,S) шығару ережесінің түрі А®ab немесе А®a, онда А,ВÎN, aÎSU{E}.Автоматты грамматика тілде конспект тәуелді тілі немесе автоматты және регулярлы грамматика деп аталады

Бақылау сұрақтары:

1. Формальды граматика деп нені атаймыз және граматикалық анализ дегеніміз не?

2. Граматиканы жіктеу әдістері деген не?

Ұсынылған әдебиеттер:

1. Бурин Е.А. Введение в основы информатики Алматы-1989 г Мектеп

2. Козыров А.А. Информатика для вузов СПб 2002 г

Дәріс 5. Алгоритмдік проблемалар: бос, иденцификациялау, тілдердің эквивалентілігі

Мақсаты:Алгоритм заңдылықтарын, Тьюренг машинасы жұмысын, алгоритмдер теориясы ұғымдарын көрсету.

Жоспары:

· Граматика түрлері

· Келтірілген грамматикалар.

Алгоритмдер теориясында дәлелденгендей, алгоритмнің бір мәнді түсінілуі, ал оның қадамдары қарапайым және орындалатын болуы үшін осы талаптарды орындайтын машина болуы тиіс. Мұндай машиналардың бірі – абстрактілі (теория жүзіндегі) Тьюрингмашинасы. Алгоритмнің қатаң заңдылықтарымен жұмыс істейтін Тьюринг машинасының құрылымы суретте көрсетілген (аі – енгізілген символдар, і = 1, 2, 3,...).
Машина құрамындағы таспажеке ұяшықтардан тұрады (таспа шексіз болуы мүмкін). Әрбір ұяшыққа алфавитке сәйкес тек бір символ енгізіледі (суретте символ енгізілмеген ұяшық бос символ (<< >>) арқылы белгіленеді. Бастиекміндетті түрде бір ұяшықтың үстінде орналасулы тұрады. Ол символды оқи және енгізе алады, қажет болса оны өшіреді. Бастиектің ерекшелігі – ол таспа бойынша еркін жылжи алатын етіп орналастырылған.
БҚ таспа басқару құрылғысы
бастиек

 

... ... ак ... << >> аі-1 аі аі+1 ... ...


Тьюринг машинасының негізгі құрылымдық бөлімдері
Тьюринг машинасының қарапайым бір қадамдық әрекеті мынадай іс-әрекеттерден тұрады:

  • Бастиекбір тактілі уақытта өзі тұрған ұяшыққа енгзілген символды оқиды;
  • Оқыған символ және бастиектің ағымдық орны басқару құрылғысының жағдайын ( жаңа күйге өтуін, жаңа жазылатын символды, бастиектің жылжуын және т.с.с.) бір мәнбі анықтайды;
  • Басқару құрылғысымашинаға берілген команданы орындайды және сақтайды;
  • Автоматтың соңғы қалып-күйге өтуіне байланысты, машина өз жұмысын тоқтатады не алгоритм дұрыс құрылмаған болса, еш уақытта тоқтамайды.

Жұмыс басында бастиек таспа ұяшығына бір машиналық сөз жазады да, келесі ұяшықтың үстіне орналастырылып қойылады, т.с.с.
Алгоритмдер теориясында құрылған алгоритмдер өзінің мүмкіндігі бойынша Тьюринг машинасына және алгоритм ұғымын дәлелдейтін басқа үлгілерге (модельдерге) баламалы екені дәлелденген. Алгоритмнің мұндай ұғымы арқылы шешлмейтін проблемаларды алгоритмдеу мүмкін емес екені де дәлелденді. Яғни есепті Тьюринг машинасы арқылы шешуге мүмкін болмаса, оның алгоритмі шешімсіз.
Егер кейбір жалпы мәселені шешу үшін алгоритм белгілі Тъюринг машинасы деп аталатын айтылған машиналардың варианттарының бірін Тьюринг машинасының үш алфавиті бар:
1. Бос символмен берілген сыртқы алфавит – А((((.
2. Ішкі алфавит немесе жағдайлар алфавиті Q
3. Қозғалыстар алфавиті S = (-1, 0, +1(.
Машинаның құрылымына кіреді:
а) шексіз таспа (ұяшықтарға бөлінген). Әрбір ұяшыққа тек
б) оқып-жазушы құрылғы. Оқып-жазушы құрылғының шолу жасау,
г) машинаның бір конфигурациясынан басқасына өтулерін анықтайтын машинаның егер шолу жасалған ұяшық пен машинаның жағдайы белгілі машинаның программасы бұл әрбір (а, qi ) қадам болып табылады.
Машинаның жұмыс істеу ережелері.
Машина дискретті түрде жұмыс істейді (қадам қадам машинаның жұмыстары машинаның қадамы q0 ға жеткенше жалғаса береді.
Машина мысалдары
Мысал 1. Келесі Тьюринг машинасы унарлық санақ жүйесінде
q1 q2 q3
| |q1+1 (q3-1 |q3-1
+ |q1+1
( ( q2-1
(q0+1
Мысал 2. Келесі Тьюринг машинасы унарлық санақ жүйесінде
q1 q2 q3
| (q1+1 |q2-1 |q3+1
( |q3+1 ( ( q2-1 (q0+1 |q2

Грамматиканың төрт түрінің ішінде мәнмәтінді–бос грамматика бағдарламамлау тілдеріне қосымша мен компиляциялар көз қарасынан ең негізгі болып келеді. –грамматика көмегімен бағдарламамлау тілі құрылымының үлкен бөлігін анықтауға болады.

Бағдарлама тілінің конструкциясын беретін грамматикаларды құру кезінде олардың өзгеруіне сүйенуге жиі тура келеді, сондықтан алдымен –грамматиканың жай, бірақ та негізгі бірнеше өзгерулерін қарастырайық. Өзгерудің бірінші түрі грамматикадан пайдасыз символдарды жоюмен байланысты. Символдар грамматикада пайдасыз болып қалуы келесі жағдайларда болады:

а) егер символ шығару кезінде алына алмаса

б) егер символдан соңғы терминалды шынжыр алына алмаса.

Алдымен соңғы шынжырды шығаруға мүмкін емес символдарды айқындау алгоритімін қарастырайық. Егер символынан соңғы терминалды шынжыр шығарылмаса ол тудырылмайтын деп аталады.

Грамматикалардың ережесін қарастырып отырғанда оң жақ символдарының барлығы тудыратын деген шешімге келсек, онда сол жақта тұрған символдар да тудыратын болып келеді. Ақырғы тұжырым тудырмайтын символдарды байқау процедурасын келесі түрде жазуға мүмкіндік береді:

1 Оң жағы терминал еместерді құрамынды ұстайтын бір болсын ереже табылатын терминал еместер тізімін құру.

2 Егер жоғарыда айтылған ереже табылатын болса, онда терминалдар емес тізіміне оның сол жақында тұрғандарды енгізу.

3 Егер 2 қадамда тізім толықтырылмаса, грамматиканың барлық тудыратын терминал емес тізімі алынады, ал оның құрамына енбеген барлық терминал еместер тудырмайтын болып келеді.

грамматикасына сәйкес талдай келе бұндажәне символдары тудырмайтын екеніне көз жеткіземіз. Тудырмайтын символдары құрамында бар ережелерді жойған соң аламыз.

Егер ешбір шығарылатын шынжырда болмаса, онда – грамматикада символы жетпейтіндеп аталады.

Егер сол жақтағы терминал емес символы жететін болса, онда оң жақтағылар да сондай болатынына көз жеткіземіз. бұл ереже қасиеті жетпейтін символдарды анықтау процедурасының негізі болып келеді де, оны келесі түрде жазуға болады: Бастауыш символдан тұратын бір элементті тізім құру.

1 . Егер сол жағы тізімге енгізілген болса, онда оның оң жағындағыларда тізімге енгізілетін ереже табылса.

2 . Егер 2 – қадамда тізімге жаңа терминал еместер қосылмаса, онда барлық жеткен терминал еместер тізімі жетпейтін болып келеді.

Грамматикалардың пайдасыз символын келесі әдіспен анықтауға болады: жататын символы -грамматикасында жетпейтін немесе тудырмайтын болып келсе, онда ол пайдасыздеп аталады.

Пайдасыз символдарды алдымен тудырмайтын, ал содан соң жетпейтін символдары құрамында бар ережелерді грамматикадан жоя келе шығарып тастауға болады. Иллюстрация ретінде келтірілген ережелерге дәлел түрінде келесі грамматикалардағы өзгерулерден орындаймыз:

 

 

Алдымен және тудырмайтын символ екенін байқап, тудырмайтын символдары бар ережелерді жоя келе аламыз.

Алынған схемада символы жетпейтін символ болып келеді. Бұл символды құрамында ұстайтын ережені шығара келе аламыз.

Келтірілген грамматикалар.

Егер –грамматикасының құрамында пайдасыз символдар болмаса, онда ол келтірілген деп аталады.

түріндегі ереже оң жақты рекурсивті, ал түріндегі ереже – сол жақты рекурсивті деп аталады.

Бақылау сұрақтары:

1. Тьюренг машинасы құрамында не бар?

2. Граматикалар ережесі неден тұрады?

Ұсынылған әдебиеттер:

1. Симонович С.В. Базовый курс. Информатика. Питер. 2003 г

2. Ивани А. Элементы теоритического программаирования. М. 1985 г.

 

 

Дәріс 6. Автоматтар.

Мақсаты:Тілдер және автоматтар теориясы алғашқы ұғымымен таныстыру.

Жоспары:

· Автомат түсінігі

· Автомат құрылысы

Тiлдер және автоматтар теориясы абстрактiлi есептеуiш құрылымдарды немесе "Машиналарды" зерттеумен шұғылданады.
1930-шi жылдарда, компьютерлердiң пайда болуына дейiнгі көп уакыт бұрын, А.Тьюринг абстрактiлi машинаны зерттедi, кем дегенде есептеулердiң төңiрегiнде,қазiргi есептеу машиналарының барлық мүмкiндiктерiне ие болды. Тьюрингтiң мақсаты есептеу машинасы iстей алатын, не алмайтын шекарасын сипаттау болды. Алынған нәтижелер абстрактiлi тьюринг машиналарына ғана емес, сонымен катар,қазiргi кездегі компьютерлерге қолдануға болады.
1940-шi және 1950-шi жылдардағы бiраз зерттеушiлер ең оңай машиналарды зерттеумен шұғылданды, бүгiн олар "Шектi автоматтар" деп аталады. Мұндай автоматтар бастапқыда адам миының жұмыс жасау үлгiсі ретiнде ұсынылған. Соңында1950-шi жылдарда лингвист Н.Хомский формалды"Грамматик" зерттеуімен шұғылданды. Дәл мағынасында сөздер машиналар болмай, грамматикалар, әйтсе де, тығыз байланған абстрактiлi автоматтармен және кейбiр ең маңызды программалық қамтамасыз етуді негiзiмен құрайтын қызмет көрсетедi, жеке алғанда, компиляторлардың компоненттері менде.
1969 жылда С.Кук Тьюрингтің есептелу және есептелмеу туралы нәтижелерiн дамытты. Оған есеп бөлудi негiзiнен шешiлетін есепті, есептеу машинасы да шешетіндей бөлді,бiрақ ол үшiн машина уақыты көп талап етедi екен және компьютер дәл осылай есептiң түгелдей дерлiк даналарының шешiмдерi үшiн пайдасыз басқаларын қоспағанда. Соңғы класстың есептерi "Қиын есептелетiн" деп атайды"Қиын болатын" ) немесе "NP-қиын". Тiптi экспоненталық өсуде есептеу машиналарының жылдамдықтары("Мур заңы") тiптi күмәнді, ол бізге бұл сыныптың есептерiнiң шешiмiнде түбегейлi жетiстiктерге жетудiң сәтi түседi.
Бұның барлығы теориялық құрастырулар бүгiнгі кездегі ғалымдардың информатиканың төңiрегiдегi шұғылдануына тiкелей байланысты. Енгiзiлген ұғымдардың кейбiрi, мысалы,мұндай шектi автоматтар және үстiрт грамматикалардың кейбiр түрлерi ,программалық қамтамасыз етудің жобалау және маңызды компоненттердiң жасауында қолданылады.
Басқа ұғымдары, мысалы, Тьюринг машинасы, бiзге программалық қамтамасыз етудi маңызды мүмкiндiктерін анықтауға көмектеседі. Жеке алғанда, есептеулердiң күрделілер теориясы бізге есептi шеше алатынымызды"маңдайға" және оған тиiстi бағдарламаны жазуды ( егер буль есебі "Қиын рұқсат етiлетiн" сыныпқа жатса )немесе бiзге қиын есептелетін, жақын, эвристикалық немесе әйтеуiр бiр көмегiмен жұмсалатын уақытты шектеудiң сәтi түсетiн басқа әдiс қолдана шешiмді iздеукерек.
Автоматтардың теориясы және күрделiлiктiң теориясының себептерi қатарына байланысты ең маңызды информатиканың ядроның бiр бөлiктерi болып табылады.
Шектi автоматтардың теориясына кiрiспе
Шектi автоматтар көп компоненттер және программалық қамтамасыз етулер үшiн үлгi аппаратты болып табылады:
1. Өңдеу және тексеру үшiн цифрларға қолданылатын программалық қамтамасыз ету
2. Үйреншiктi компилятор "Лексикалық анализатор", яғни сол компилятордың компоненті, мұндайға түпнұсқаның бөлуiне логикалық бірліктер, идентификаторлар, түйін сөздер, жауап беретiн және тыныс белгiнiң таңба бiрлiктері осыларға жауап береді.
3. Сүзiп шығу үшiн программалық қамтамасыз ету мұндай үлкен мәтiндiк массив,Web- беттер, берілген сөздерді, сөйлемдердiң, (үлгiлер ) нышандардың тiзбектерiн іздеу мақсатымен.
4. Байланыстың хаттамалары жүйелердiң әр түрлi тектiң тексеруi үшiн программалық қамтамасыз ету(немесе қорғауға алған ақпар алмасу үшiн хаттамалар ), түпкi санда әр түрлi күйлерді болатын.
Әр түрлi жүйелер және олардың компоненттерiнiң жиыны бар, мысалы,дәл кәзiр есептелгені, әрбiр моментте оларды "Күйлердің" түпкi санның бiрiнен қарауға болады. Әрбiр күйдi тағайындау мен жүйенiң тарихының нақтылы моментiнiң есте сақтауы болып табылады. Сан болғандықтан, онда жүйенiң барлық тарихын еске сақтау мүмкiн емес, демек, жүйенi тек қана мұқият салу керек, ең маңызды мәлiметтi сақтап, жеңiл-желпiні ұмыту үшiн.
Күйлердi санның шектiлiгiнiң артықшылығы жүйенi шектелген қорлар арқылы жүзеге асыруға болатындығында. Мысалы, оны"темiрде" жүзеге асыруға болады схема түрінде немесе жай бағдарлама түрінде, негiзiнде шектелген санының мәлiметтерiн немесе ағымдағы машина кодының командалары шешiм қабылдауы.
Осыған ұқсас барлық жағдайларда лексемаларды оқып – тану үшін шектік автомат (ША) немесе қалыптар (жағдайлар) машинасы деп аталатын қарапайым модель қолданылады. Қай жағдайда екенімізді біле отырып, біз келесі енгізілетін символдың ізделінді лексема бөлігі болуы мүмкіндігін анықтай аламыз. Келесі суретте бірлерінің саны тақ болатын екілік байламды байаныстыр
1-шi мысал. Ең оңай қарапайым шектi автомат "Қосылу-өшірілу"ауыстырып қосқышы болып табылады. Бұл құрылымдар өз ағымдағы күйiн еске сақтайды, және бұдан батырманың басуынан күйі нәтижеге тәуелдi болады. "Өшiрген" күйлерден батырмаларды басу арқылы "Қосылған" күйге ауыстырып қосқыш ауыстырады және керiсiнше.
Кiретiн сигналдарға әрiптер сәйкес келедi. Лексикалық анализатор әрдайым бiр-бiрнышаннан құрастырылатын бағдарламаларды қарап шығады деп бiз мәлiмет санай аламыз. Әрбiр келесi нышан автомат үшiн мәлiмет кiретiн сигнал сияқты қаралады.
Автоматтың бастапқы күйі бос тiркеске сәйкес келедi, және әрбiр күй күйге then-ның сөзiнiң кезектi әрiбi бойынша өте алады, келесi префикске тиiстi. Белгi қойылған "Then" күйі әрiптерден барлық осы сөздер енгiзiлген бойынша жетедi. Автоматты функция болатындығы then-ның сөздерi айырып тану, онда соңғы рұқсат ететiн күйдi жалғыз санаймыз






Не нашли, что искали? Воспользуйтесь поиском:

vikidalka.ru - 2015-2019 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных