Кіріспе

Есептеудің математикалық моделі

Шекті күйдегі машина (FSM) немесе шекті күйдегі автомат (FSA, көпше: автоматтар), шекті автомат немесе жай ғана күйдегі машина – есептеудің математикалық моделі. Бұл кез келген уақытта шекті сандардағы күйлердің бірінде бола алатын абстрактілі машина. FSM кейбір кіріс мәліметтеріне жауап ретінде бір күйден екіншісіне өте алады; бір күйден екінші күйге өту – өтпелі деп аталады. FSM өз күйлерінің тізімімен, бастапқы күйімен және әрбір өтпеліні тудыратын кірістермен анықталады. Шекті күйдегі машиналар екі типке бөлінеді: детерминистік шекті күйдегі машиналар және детерминистік емес шекті күйдегі машиналар. Кез келген детерминистік емес шекті күйдегі машина үшін эквивалентті детерминистік машинаны құруға болады. Күйдегі машиналардың мінез-құлқы қазіргі қоғамдағы көптеген құрылғыларда байқалады, олар ұсынылған оқиғалар тізбегіне байланысты алдын ала белгіленген әрекеттер тізбесін орындайды. Мысалдар: дұрыс монеталардың комбинациясы салынғанда тауарды беретін автоматтары; жолаушылардың сұраған қабаттарына сәйкес тоқтау ретін анықтайтын лифттер; көлік күтіп тұрғанда реттілігін өзгертетін жол қозғалысы шамдары; дұрыс ретпен енгізілген сандар тізбесін қажет ететін комбинациялық құлыптар. Шекті күйдегі машинаның есептеу қуаты Тьюринг машинасы сияқты басқа есептеу модельдеріне қарағанда төмен. Есептеу қуатының айырмашылығы Тьюринг машинасы орындай алатын, бірақ FSM орындай алмайтын есептеу тапсырмалары бар екенін білдіреді. Өйткені FSM-нің жадысы оның күйлерінің санымен шектеледі. Шекті күйдегі машинаның Тьюринг машинасымен салыстырғанда есептеу қуаты бірдей, егер Тьюринг машинасының басы тек "оқу" операцияларын орындайтын және әрқашан солдан оңға қарай жылжысатын болса. FSM-дер автоматтар теориясының кеңірек саласында зерттеледі.

Мысал: монетамен жұмыс істейтін турникеті

Мемлекеттік машинамен модельдеуге болатын қарапайым механизмнің мысалы – турникет. Метроға және ойын-сауық парктеріне кіруді бақылау үшін қолданылатын турникет – бел биіктігінде үш айналмалы қолдары бар қақпа, олардың біреуі кіреберістің алдында орналасқан. Бастапқыда қолдар құлыпталған, кіруге кедергі келтіріп, адамдардың өтуіне жол бермейді. Турникеттегі ойыққа монета немесе жетон салынғанда қолдар ашылады, соның арқасында бір адам өте алады. Адам өткеннен кейін, тағы бір монета салынғанша қолдар қайтадан құлыпталады. Мемлекеттік машина ретінде қарастырылған турникеттің екі мүмкін күйі бар: құлыпталған және құлыпталмаған.

Қабылдаушылар

Қабылдағыштар (сонымен қатар детекторлар немесе танушылар деп аталады) бинарлық шығыс береді, алынған кіріс қабылданды ма, жоқ па, соны көрсетеді. Қабылдағыштың әрбір күйі қабылдаушы немесе қабылдамайтын күй болып табылады. Барлық кіріс алынғаннан кейін, егер ағымдағы күй қабылдаушы күй болса, кіріс қабылданады; әйтпесе, қабылданбайды. Әдетте, кіріс – символдар (әріптер) тізбегі болады; әрекеттер қолданылмайды. Бастапқы күй қабылдаушы күй болуы мүмкін, мұндай жағдайда қабылдағыш бос тізбекті қабылдайды. 4-суретте "nice" тізбегін қабылдайтын қабылдағыш мысалы көрсетілген. Бұл қабылдағышта тек 7-ші күй ғана қабылдаушы күй болып табылады. Символдар тізбектерінің (мүмкін шексіз) жиынтығы, егер дәл сол жиынтықты қабылдайтын қабылдағыш болса, ресми тіл деп аталады. Мысалы, нөлдердің жұп саны бар бинарлық тізбектер жиынтығы – тұрақты тіл (қ. 5-сурет), ал ұзындығы жай сан болатын тізбектер жиынтығы тұрақты тіл емес. Қабылдағышты қабылдағыш қабылдаған барлық тізбекті, бірақ қабылдамаған тізбектерді қамтымайтын тілді анықтау ретінде де сипаттауға болады; осы тілді қабылдағыш қабылдайды. Анықтама бойынша, қабылдағыштар қабылдайтын тілдер – тұрақты тілдер. Берілген қабылдағыш қабылдайтын тілді анықтау мәселесі – алгебралық жол мәселесінің бір мысалы, бұл ең қысқа жол мәселесін (кез келген) жартылай сақина элементтерімен салмақталған қабырғалары бар графтарға жалпылау болып табылады. Қабылдаушы күйдің мысалы 5-суретте көрсетілген: екілік кіріс тізбегінде жұп санда 0 бар ма, жоқ па, анықтайтын детерминистік шекті автомат (DFA). S1 (ол бастапқы күйдің өзі) жұп санда 0 енгізілген күйді көрсетеді. Сондықтан S1 – қабылдаушы күй. Бұл қабылдағыш егер бинарлық тізбекте жұп санда 0 болса (0 жоқ бинарлық тізбектерді қоса алғанда) қабылдау күйінде аяқталады. Бұл қабылдағыш қабылдайтын тізбектердің мысалдары: ε (бос тізбек), 1, 11, 00, 010, 1010, 10110 және т.б.

Классификаторлар

Классификаторлар – n саны екіден артық болатын n-арлық шығыс тудыратын қабылдағыштардың жалпылама түрі.

Секвенсерлер

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

Альтернативті семантика

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

Оңтайландыру

FSM-ді оңтайландыру – бірдей функцияны орындайтын ең аз күй санына ие машинаны табуды білдіреді. Бұл жұмысты орындайтын ең жылдам алгоритм – Хопкрофтың минималдау алгоритмі. Басқа техникаларға импликациялық кесте қолдану немесе Мурдың азайту процедурасы жатады. Сонымен қатар, ациклді FSA-ны сызықтық уақытта минималдауға болады.

Жабдықтардағы қолданбалар

Цифрлық схемада FSM бағдарламаланатын логикалық құрылғыны, бағдарламаланатын логикалық контроллерді, логикалық шлюздерді және триггерлерді немесе релелерді пайдалана отырып құрастырылуы мүмкін. Нақтырақ айтқанда, аппараттық іске асыру үшін күй айнымалыларын сақтауға арналған регистр, күй өтуін анықтайтын комбинациялық логика блогы және FSM шығысын анықтайтын комбинациялық логиканың тағы бір блогы қажет. Классикалық аппараттық іске асырудың бір мысалы – Ричардс контроллері. Медведев машинасының құрылымында шығыс тікелей күй триггерлеріне қосылады, бұл триггерлер мен шығыс арасындағы уақыт кешігуін азайтады. Төмен қуатты автоматтарды қуат тұтынуын азайту үшін күй кодилеу арқылы оңтайландыруға болады.

Аяқтық күйдегі машиналар мен компиляторлар

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

Жалпы

Вагнер, Ф., "Түкілді күй машиналарымен бағдарламалық жасақтаманы модельдеу: практикалық тәсіл", Ауербах басылымдары, 2006, ITU-T, Z.100 ұсынысы, Күйді сипаттау тілі (SDL)
Самек, М., C/C++ тіліндегі практикалық күй диаграммалары, CMP кітаптары, 2002, Самек, М., C/C++ тіліндегі практикалық UML күй диаграммалары, 2-ші басылым, Newnes, 2008, Гарднер, Т., Күйде басқару, 2007
Cassandras, C., Lafortune, S., "Дискреттік оқиғалар жүйелеріне кіріспе". Kluwer, 1999, Тимоти Кам, Шекті күй машиналарының синтезі: Функционалдық оңтайландыру. Kluwer Academic Publishers, Бостон, 1997,
Tiziano Villa, Шекті күй машиналарының синтезі: Логикалық оңтайландыру. Kluwer Academic Publishers, Бостон, 1997,
Carroll, J., Long, D., Формальді тілдерге кіріспемен шекті автоматтар теориясы. Prentice Hall, Энглвуд Клифс, 1989. Kohavi, Z., Коммутация және шекті автоматтар теориясы. McGraw Hill, 1978. Gill, A., Шекті күй машиналары теориясына кіріспе. McGraw Hill, 1962. Ginsburg, S., Математикалық машина теориясына кіріспе. Addison Wesley, 1962.

Марковтың шекті тізбекті процестері

Марков тізбегін күйлер жиыны s1, s2, ..., sr арқылы біртіндеп өтетін процесс ретінде қарастыруға болады. Егер ол si күйінде болса, онда келесі қадамда sj күйіне pij ықтималдығымен өтеді. Бұл ықтималдықтарды өтпелі матрица түрінде көрсетуге болады (Кемени (1959), 384 б.). 6-тарау "Шектелген Марков тізбектері".