Лекция 6 Тақырыбы: Шекті автоматтар

Лекция 6

Тақырыбы: Шекті автоматтар

b=

теңдігі орынды болады.

Бұл фунциялар сәйкесінше шығушы және өту (ауысу) функциялары деп аталады. Олар құрылғының енуші каналына әріптеп берілетін А алфавитіндегі сөздерді қайта өңдеу заңын анықтайды.

Шекті автоматтар үшін (А, S, B ,, ) жиынымен теңдестіріп, шекті автомат деп атауға болады. Шекті автомат мұндай формада берілсе – абстрактілі шекті автомат деп аталады. Композициялық ережелер қолдану арқылы абстрактілі шекті автоматтардан құралған жағдайда, құрылғыны құрылымдық шекті автомат деп атайды. Автомат жалпы алғанда – шекті автомат, немесе оның компонентін не функциясын өзгерту жолымен алынған басқа түрдегі шекті автомат болып табылатын басқарушы жүйе.

Шекті автомат ұғымы 20 ғасыр ортасында нерв жүйесінің жұмысын, әмбебап есептеуіш машиналардың және басқа автоматтардың жұмысын математикалық тілде бейнелеп көруге талпынудан келіп шықты. Мұндай бейнелеуге тиісті ерекшіліктің бірі – математикалық модельдің дискреттілігі және оның параметрлері мәндерінің шектілігі. Міне осы ерекшілік шекті автомат ұғымының тууына себеп болды.

және өтуші (ауысу) функцияларының орнына еркін алынған қатынас не кездейсоқ функция қойылуы мүмкін болған автоматтар жатады. Мысалы детерминирлі емес, автоматтар, ықтималды автоматтар, т.б. Үшінші топқа енуші объекттері спецификалық жиындар болып табылатын автоматтар жатады. Мысалы, өзгермелі құрылымды автоматтар осы топқа жатады.

_{Лекция 7}

_{Тақырыбы: Автоматтар теориясы}

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

Синтез мәселесінің мәні мынада: алдын – ала берілген функциясы яғни қызметі не әрекет ету құлқы бойынша автоматтарды құру.

_{Толықтық мәселесінің мәні мынада: автоматтар жиыны М}¹ _{М толықтық қасиетіне ие ме? деген сұраққа жауап береді, яғни, берілген М}¹ <sub>ішкі жиының автоматтарына қайсыбір шекті амалдарды қолданып алынған барлық автоматтар жиыны М жиынына сәйкес келе ме?

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

Автоматты әрекет ету құлқы (поведение) – бұл автоматтың сыртқы ортамен өзара әрекетін бейнелейтін математикалық ұғым. Шекті автоматтың сыртқы ортасына мысал ретінде енуші сөздер жиынын алуға болады. Ал, әрекет ету құлқы – бұл осы сөздерге қатысты автомат әрекеті.
2. Автоматтар теориясы математиканың басқа да облыстарында қолданылғаны сияқты, практикалық мәселелерді шешуде де қолданылады. Мысалы, автоматтар теориясы көмегімен кейбір формальді есептеулердің шешімі бар екендігі дәлелденді. Автоматтар теориясының ұғымдары мен әдістерін формальді және табиғи тілдерге қолдану математикалық лингвистиканың пайда болуына себеп болды.</sub>

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

Мысал 1. Мынадай нақты шекті автомат берілсін. М=[А, S, B ,, , ]. Енуші алфавит А={0,1}; шығушы алфавит В={0,1}; үш ішкі жағдай S={S₀ S₁ S₂}; шығу және өту (ауысу) функциялары:

түрінде берілген.

(S_0,1) a S₀ (S_0, 1) a 1

(S_1,0) a S₂ (S_1, 0) a 1

(S_1,1) a S₁ (S_1, 1) a 0

(S_2,0) a S₀ (S_2, 0) a 1

(S_2,1) a S₂ (S_2, 1) a 0

Автомат кірісіне 0, 1, 0, 1 тізбегін береміз. Егер автомат бастапқыда S₀ жағдайында тұрса, онда бірінші символ 0 – ді оқып, S₁ жағдайына өтеді де шығысында 0 – ді шығарады. Одан соң 1 – ді оқып, S₁ жағдайында қалады да 0 – ді шығарады. Келесі 0 –ді оқып, S₂ жағдайына өтеді де 1 – ді шығарады. Соңғы 1 символын оқып, S₂ жағдайында автомат жұмысын аяқтайды. Бұл кезде шығушы лентада 0, 0, 1, 0 тізбегі бар болады. Осылайша автомат 0, 1, 0, 1 түрдегі енісін 0, 0, 1, 0 – ге түрлендірді (0101→ 0010)