Cheklangan mashina: nazariya va amalga oshirish. Cheklangan holat mashinalarining turlari Holat mashinalarining amaliy qo'llanilishi

Avtomatlar nazariyasi diskret matematikaning diskret axborotni o'zgartiruvchi modellarini o'rganuvchi bo'limidir. Bunday konvertorlar ham haqiqiy qurilmalar (kompyuterlar, tirik organizmlar), ham xayoliy qurilmalar (aksiomatik nazariyalar, matematik mashinalar). Aslini olganda, cheklangan holat mashinasini qurilma sifatida tavsiflash mumkin M , kirish va chiqish kanallariga ega va soat momentlari deb ataladigan vaqtning har bir diskret momentida u yakuniy holatlardan birida bo'ladi.

Har bir daqiqada kirish kanali bo'yicha t =1, 2, ... qurilmaga M kirish signallari keladi (ba'zi chekli signallar to'plamidan). Keyingi vaqtda holatni o'zgartirish qonuni kirish signaliga va qurilmaning joriy vaqtdagi holatiga qarab o'rnatiladi. Chiqish signali joriy vaqtdagi holat va kirish signaliga bog'liq (1-rasm).

Cheklangan holat mashinasi axborotni qayta ishlash uchun haqiqiy diskret qurilmalarning matematik modelidir.

Davlat mashinasi tizim deb ataladi A= (X , Q , Y ,  ,  ), Qayerda X , Q , Y ixtiyoriy bo'sh bo'lmagan chekli to'plamlar va  Va  - funktsiyalari, ulardan:

bir guruh X ={a 1 , ..., a m ) deyiladi kirish alifbosi , va uning elementlari kirish signallari , ularning ketma-ketligi mavjud umumiy so'zlarda ;

bir guruh Q ={q 1 , ..., q n ) deyiladi ko'p davlatlar avtomat va uning elementlari - davlatlar ;

bir guruh Y ={b 1 , ..., b p ) deyiladi chiqish alifbosi , uning elementlari chiqish signallari , ularning ketma-ketligi chiqish so'zlari ;

funktsiyasi  : X  Q Q chaqirdi o'tish funktsiyasi ;

funktsiyasi  :X  Q Y chaqirdi chiqish funktsiyasi .

Shunday qilib,  (x , q )Q ,  (x , q )Y  uchun x X , q Q .

Cheklangan holat mashinasi xayoliy qurilma bilan bog'langan bo'lib, u quyidagicha ishlaydi. Bu ko'plab shtatlardan birida bo'lishi mumkin Q , turli signallarni idrok etish X va turli xil signallarni chiqaradi Y .

2. Cheklangan holat mashinasini ko'rsatish usullari

Mavhum avtomatlarni aniqlashning bir nechta ekvivalent usullari mavjud, ulardan uchtasini nomlash mumkin: jadvalli , geometrik Va funktsional .

2.1 Mashinaning jadval vazifasi

Avtomatning ta'rifidan kelib chiqadiki, u har doim ikkita kirishni o'z ichiga olgan jadval bilan belgilanishi mumkin T chiziqlar va P ustunlar, bu erda ustunning kesishmasida q va iplar A funksiya qiymatlaridir  (a i , q j ),  (a i , q j ).

2.2. Mur diagrammasi yordamida avtomatni belgilash

Cheklangan holat mashinasini aniqlashning yana bir usuli - grafik, ya'ni grafik yordamida. Avtomat yorliqli yo'naltirilgan grafik sifatida tasvirlangan G(Q , D ) ko'p uchlari bilan Q va ko'plab yoylar D ={(q j ,  (a i , q j ))| q j Q , a i X ), yoy esa ( q j ,  (a i , q j )) juftligi bilan belgilangan ( a i ,  (a i , q j )). Shunday qilib, bu usul bilan mashinaning holatlari davlat ramzlari yozilgan doiralar bilan tasvirlangan q j (j = 1, …, n ). Har bir doiradan u amalga oshiriladi T kirish alifbosi belgilariga mos keladigan o'qlar (yo'naltirilgan qirralar) X ={a 1 , ..., a m ). Harfga mos keladigan o'q a i X va doirani tark etish q j Q , juftlikka tegishli ( a i ,  (a i , q j )) va bu o'q mos keladigan doiraga olib keladi  (a i , q j ).

Olingan chizma deyiladi avtomat grafigi yoki, Mur diagrammasi . Juda murakkab bo'lmagan mashinalar uchun bu usul ko'proq ingl jadvalli.

Cheklangan holat mashinasi - bu biror narsaning chekli sonli holatlarini o'z ichiga olgan mavhum model. Har qanday buyruqlarni bajarish jarayonini ifodalash va boshqarish uchun foydalaniladi. Shtat mashinasi o'yinlarda sun'iy intellektni qo'llash, katta hajmli va murakkab kod yozmasdan toza yechim ishlab chiqarish uchun idealdir. Ushbu maqolada biz nazariyani ko'rib chiqamiz, shuningdek, oddiy va stekga asoslangan holat mashinasidan qanday foydalanishni o'rganamiz.

Biz allaqachon chekli holat mashinasidan foydalangan holda sun'iy intellekt yozish bo'yicha bir qator maqolalarni nashr etgan edik. Agar siz ushbu seriyani hali o'qimagan bo'lsangiz, buni hozir qilishingiz mumkin:

Cheklangan holat mashinasi nima?

Cheklangan holat mashinasi (yoki oddiygina FSM - Finite-state machine) gipotetik holat mashinasiga asoslangan hisoblash modelidir. Bir vaqtning o'zida faqat bitta holat faol bo'lishi mumkin. Shuning uchun har qanday harakatni bajarish uchun mashina o'z holatini o'zgartirishi kerak.

Davlat mashinalari odatda biror narsa oqimini tashkil qilish va ifodalash uchun ishlatiladi. Bu, ayniqsa, o'yinlarda AIni qo'llashda foydalidir. Masalan, dushmanning "miyasini" yozish uchun: har bir holat qandaydir harakatni (hujum, qochish va hokazo) ifodalaydi.

Cheklangan holat mashinasini grafik sifatida tasvirlash mumkin, uning uchlari holatlar, qirralari esa ular orasidagi o'tishlardir. Har bir chekkada o'tish qachon sodir bo'lishi kerakligini ko'rsatadigan yorliq mavjud. Masalan, yuqoridagi rasmda, agar o'yinchi yaqin joyda bo'lsa, mashina "ayyorlik" holatini "hujum" holatiga o'zgartirishini ko'rishingiz mumkin.

Rejalashtirish davlatlari va ularning o'tishlari

Cheklangan holat mashinasini amalga oshirish uning holatlari va ular orasidagi o'tishlarni aniqlashdan boshlanadi. Chumoli uyasiga barglar olib ketayotgan chumolining harakatlarini tasvirlaydigan davlat mashinasini tasavvur qiling:

Boshlanish nuqtasi chumoli bargni topgunga qadar faol bo'lgan "bargni topish" holatidir. Bu sodir bo'lganda, davlat "uyga qaytish" ga o'zgaradi. Xuddi shu holat bizning chumolimiz chumoli uyasiga yetib borguncha faol bo'lib qoladi. Shundan so'ng, holat yana "barg topish" ga o'zgaradi.

Agar "bargni topish" holati faol bo'lsa, lekin sichqoncha kursori chumolining yonida bo'lsa, u holda holat "qochish" ga o'zgaradi. Chumoli sichqoncha kursoridan etarlicha xavfsiz masofada bo'lgandan so'ng, holat yana "bargni topish" ga o'zgaradi.

E'tibor bering, uyga yoki uydan uzoqqa ketayotganda, chumoli sichqoncha kursoridan qo'rqmaydi. Nega? Ammo mos keladigan o'tish yo'qligi sababli.

Oddiy chekli holat mashinasini amalga oshirish

Cheklangan holat mashinasi bitta sinf yordamida amalga oshirilishi mumkin. Keling, buni FSM deb ataymiz. G'oya har bir holatni usul yoki funktsiya sifatida amalga oshirishdir. Shuningdek, faol holatni aniqlash uchun activeState xususiyatidan foydalanamiz.

Ommaviy klass FSM ( private var activeState:Function; // mashinaning faol holatiga ko‘rsatgich umumiy funksiya FSM() ( ) umumiy funktsiya setState(state:Function) :void (activState = state; ) public function update() :void ( agar (activeState != null) (activeState(); ) ) )

Har bir davlat funksiyadir. Bundan tashqari, u har safar o'yin ramkasi yangilanganda chaqiriladi. Yuqorida aytib o'tilganidek, activeState faol holat funksiyasiga ko'rsatgichni saqlaydi.

FSM sinfining update() usuli o'yinning har bir ramkasi deb nomlanishi kerak. Va u, o'z navbatida, hozirda faol bo'lgan davlat funktsiyasini chaqiradi.

setState() usuli yangi faol holatni o'rnatadi. Bundan tashqari, avtomatning qandaydir holatini belgilaydigan har bir funktsiya FSM sinfiga tegishli emas - bu bizning sinfimizni yanada universal qiladi.

Davlat mashinasidan foydalanish

Keling, chumoli AIni amalga oshiraylik. Yuqorida biz uning bir qator holatlari va ular orasidagi o'tishlarni ko'rsatdik. Keling, ularni yana bir bor ko'rsatamiz, lekin bu safar biz kodga e'tibor qaratamiz.

Bizning chumolimiz miya maydoniga ega bo'lgan chumolilar sinfi bilan ifodalanadi. Bu faqat FSM sinfining namunasidir.

Ommaviy klass Ant ( ommaviy var pozitsiyasi:Vector3D; ommaviy var tezlik:Vector3D; umumiy var miya:FSM; umumiy funksiya Ant(posX:Raqam, posY:Number) (pozitsiya = yangi Vector3D(posX, posY); tezlik = yangi Vector3D( -1, -1); // bargni topish bilan boshlang.setState(findLeaf); anthill */ public function goHome() :void ( ) /** * "runAway" holati / public function runAway() :void ( ) public function update():void ( // Davlat mashinasini yangilash. Bu funksiya chaqiriladi. // faol holat funksiyasi: findLeaf(), goHome() yoki runAway() // Chumoli harakatiga tezlikni qo'llash.

Ant klassi tezlik va joylashish xususiyatlarini ham o'z ichiga oladi. Ushbu o'zgaruvchilar Eyler usuli yordamida harakatni hisoblash uchun ishlatiladi. Update() funktsiyasi har safar o'yin ramkasi yangilanganda chaqiriladi.

Quyida findLeaf() dan boshlab har bir usulning amalga oshirilishi keltirilgan - barglarni topish uchun javobgar davlat.

Ommaviy funktsiya findLeaf() :void ( // Chumolini bargga siljitadi. velocity = new Vector3D(Game.instance.leaf.x - position.x, Game.instance.leaf.y - position.y); if (masofa) (O'yin .instance.leaf, bu)<= 10) { // Муравей только что подобрал листок, время // возвращаться домой! brain.setState(goHome); } if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { // Курсор мыши находится рядом. Бежим! // Меняем состояние автомата на runAway() brain.setState(runAway); } }

goHome() holati - chumolini uyiga qaytarish uchun ishlatiladi.

Umumiy funktsiya goHome() :void ( // Chumolini uy tezligiga o'tkazadi = yangi Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y); if (distance( instance.home, bu)<= 10) { // Муравей уже дома. Пора искать новый лист. brain.setState(findLeaf); } }

Va nihoyat, runAway() holati sichqoncha kursoridan qochishda ishlatiladi.

Umumiy funktsiya runAway() :void ( // Chumolini kursor tezligidan uzoqlashtiradi = yangi Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y); // Kursor hali ham yaqinmi? ? if ( masofa(Game.mouse, this) > MOUSE_THREAT_RADIUS) ( // Yoʻq, u allaqachon uzoqda. Bargni qidirishga qaytish vaqti keldi. brain.setState(findLeaf); ) )

FSM takomillashtirish: stekga asoslangan avtomat

Tasavvur qiling-a, uyga ketayotgan chumoli ham sichqoncha kursoridan qochishi kerak. FSM shtatlari shunday ko'rinadi:

Bu arzimas o'zgarishga o'xshaydi. Yo'q, bu o'zgarish biz uchun muammo tug'diradi. Tasavvur qiling, hozirgi holat "qochib ketgan". Sichqoncha kursori chumolidan uzoqlashsa, nima qilish kerak: uyga boring yoki bargni qidiring?

Ushbu muammoni hal qilish stekga asoslangan holat mashinasidir. Yuqorida biz amalga oshirgan oddiy FSM dan farqli o'laroq, bu turdagi FSM holatlarni boshqarish uchun stekdan foydalanadi. Stackning yuqori qismida faol holat joylashgan bo'lib, o'tishlar stekdan qo'shilgan/olib tashlanganda sodir bo'ladi.

Va bu erda stekga asoslangan holat mashinasining ishlashining vizual namoyishi:

Stack asosidagi FSMni amalga oshirish

Bunday davlat mashinasi oddiy mashina bilan bir xil tarzda amalga oshirilishi mumkin. Farqi talab qilinadigan holatlarga ko'rsatgichlar majmuasidan foydalanishda bo'ladi. Bizga endi activeState xususiyati kerak emas, chunki stekning yuqori qismi allaqachon faol holatga ishora qiladi.

Umumiy sinf StackFSM ( private var stack:Array; public function StackFSM() ( this.stack = new Array(); ) public function update() :void (var currentStateFunction:Function = getCurrentState(); if (currentStateFunction != null) ( currentStateFunction(); ) ) umumiy funktsiya popState() :Funktsiya ( return stack.pop(); ) umumiy funktsiya pushState(state:Function) :void ( if (getCurrentState() != state) ( stack.push(state) ) ) umumiy funktsiya getCurrentState() :Funktsiya ( stack.length > 0 qaytish ? stek: null; ) )

E'tibor bering, setState() usuli pushState() (stekning yuqori qismiga yangi holat qo'shish) va popState() (stekning yuqori qismidagi holatni olib tashlash) bilan almashtirildi.

Stack-asoslangan FSM-dan foydalanish

Shuni ta'kidlash kerakki, stekga asoslangan holat mashinasidan foydalanilganda, har bir holat kerak bo'lmaganda stekdan olib tashlanishi uchun javobgardir. Misol uchun, agar dushman allaqachon yo'q qilingan bo'lsa, hujum() holati o'zini stekdan olib tashlashi kerak.

Umumiy klass Ant ((...) public var brain:StackFSM; public function Ant(posX:Number, posY:Number) ((...) brain = new StackFSM(); // Barg miyasini qidirishdan boshlang. pushState( findLeaf (...)); Vector3D(Game.instance. leaf.x - position.x, Game.instance.leaf.y - position.y if (distance(Game.instance.leaf, this));<= 10) { //Муравей только что подобрал листок, время // возвращаться домой! brain.popState(); // removes "findLeaf" from the stack. brain.pushState(goHome); // push "goHome" state, making it the active state. } if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { // Курсор мыши рядом. Надо бежать! // Состояние "runAway" добавляется перед "findLeaf", что означает, // что состояние "findLeaf" вновь будет активным при завершении состояния "runAway". brain.pushState(runAway); } } /** * Состояние "goHome". * Заставляет муравья идти в муравейник. */ public function goHome() :void { // Перемещает муравья к дому velocity = new Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y); if (distance(Game.instance.home, this) <= 10) { // Муравей уже дома. Пора искать новый лист. brain.popState(); // removes "goHome" from the stack. brain.pushState(findLeaf); // push "findLeaf" state, making it the active state } if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { // Курсор мыши рядом. Надо бежать! // Состояние "runAway" добавляется перед "goHome", что означает, // что состояние "goHome" вновь будет активным при завершении состояния "runAway". brain.pushState(runAway); } } /** * Состояние "runAway". * Заставляет муравья убегать от курсора мыши. */ public function runAway() :void { // Перемещает муравья подальше от курсора velocity = new Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y); // Курсор все еще рядом? if (distance(Game.mouse, this) >MOUSE_THREAT_RADIUS) ( // Yo'q, u allaqachon uzoqda. Barglarni qidirishga qaytish vaqti keldi. brain.popState(); ) ) (...) )

Xulosa

Davlat mashinalari, albatta, o'yinlarda sun'iy intellekt mantiqini amalga oshirish uchun foydalidir. Ular osongina grafik sifatida taqdim etilishi mumkin, bu esa ishlab chiquvchiga barcha mumkin bo'lgan variantlarni ko'rish imkonini beradi.

Davlat funktsiyalariga ega davlat mashinasini amalga oshirish oddiy, ammo kuchli texnikadir. FSM yordamida davlatlarning yanada murakkab to'qnashuvlarini amalga oshirish mumkin.

Cheklangan holat mashinasining murakkabligi mezonlaridan biri uning holatlari sonidir. Bu raqam qanchalik kichik bo'lsa, ushbu mashinani amalga oshiradigan diskret qurilma shunchalik sodda bo'ladi. SHuning uchun ham chekli avtomatlar nazariyasining muhim vazifalaridan biri eng kam holatlarga ega avtomatni qurishdir.

Zamonaviy kompyuterlarda har qanday ma'lumot ikkilik kodlar ko'rinishida taqdim etilganligi sababli, avtomat qurish uchun faqat ikkita turli barqaror holatga ega bo'lgan elementlardan foydalanish mumkin, ulardan biri 0 raqamiga, ikkinchisi esa 1 raqamiga to'g'ri keladi.

Cheklangan holat mashinalariga misollar keltiraylik.

Misol 1. Kechiktirish elementi (xotira elementi).

Kechikish elementlari - bitta kirish va bitta chiqishga ega bo'lgan qurilma. Bundan tashqari, vaqt momentida chiqish signalining qiymati t oldingi momentdagi signal qiymatiga to'g'ri keladi. Sxematik ravishda kechikish elementini quyidagicha tasvirlash mumkin (2-rasm).

Faraz qilaylik, kirish va demak, chiqish alifbosi X ={0, 1}, Y =(0, 1). Keyin Q =(0, 1). Kechikish elementining vaqtidagi holati ostida t ma'lum bir daqiqada xotira elementining mazmuni tushuniladi. Shunday qilib q (t )= X (t 1), a Y (t )= q (t )=X (t 1).

Keling, kechikish elementini jadval bilan o'rnatamiz, bu erda A 1 =0, A 2 =1, q 1 =0, q 2 =1,

(a 1 , q 1)= (0, 0)=0,  (a 1 , q 1)= (0, 0)=0;

(a 1 , q 2)= (0, 1)=0,  (a 1 , q 2)= (0, 1)=1;

(a 2 , q 1)= (1, 0)=1,  (a 2 , q 1)= (1, 0)=0;

(a 2 , q 2)= (1, 1)=1,  (a 2 , q 2)= (1, 1)=1;

Mur diagrammasi rasmda ko'rsatilgan. 3

Ushbu avtomatni mantiqiy funktsiyalar tizimi sifatida ko'rsatish uchun biz avtomat jadvali va yuqoridagi algoritmdan foydalanamiz. Bunday holda, kodlashni amalga oshirishning hojati yo'q, chunki kirish va chiqish alifbolari va holatlar allaqachon kodlangan.

Keling, shunga e'tibor qarataylik t=p=p =2. Keyin k =r =s =1, va shuning uchun kechikish elementi ikkita funktsiya bilan beriladi  Va  . Ushbu funktsiyalarning haqiqat jadvali 2 ni o'z ichiga oladi k + r =2 2 =4 qator va k +r +r +s =4 ustun:

2-misol. Ikkilik ketma-ket qo‘shuvchi.

Ushbu ketma-ket qo'shuvchi ikkilik tizimda ikkita raqamni qo'shadigan qurilma. Raqamlar qo'shimchaning kirishlariga beriladi X 1 va x 2, eng kam ahamiyatli raqamlardan boshlab. Chiqish raqam kiritishiga mos keladigan ketma-ketlikni hosil qiladi X 1 +x 2 ikkilik tizimda (4-rasm).

Kirish va chiqish alifbolari o'ziga xos tarzda belgilanadi: X ={00; 01; 10; 11}, Y =(0,1). Holatlar to'plami raqamlarning mos keladigan raqamlarini qo'shganda tashish qiymati bilan belgilanadi X 1 va x 2. Agar ba'zi bitlarni qo'shganda, tashish hosil bo'lsa, biz qo'shuvchi holatga kirdi deb taxmin qilamiz. q 1 . Tashish yo'q bo'lsa, biz qo'shimchani holatda deb hisoblaymiz q 0 .

Qo'shuvchi jadval bilan belgilanadi.

Ketma-ket qo'shimchaning Mur diagrammasi rasmda ko'rsatilgan. 5.

Kirish va chiqish belgilari allaqachon kodlanganligini unutmang. Biz shtatlarni quyidagicha kodlaymiz:  (q 0)=0,  (q 1)=1. Shunday qilib, ketma-ket qo'shuvchi ikkita mantiqiy funktsiya bilan belgilanadi, ularning haqiqat jadvali quyidagicha:

Misol 3. Tenglikni taqqoslash sxemasi.

Tenglikni taqqoslash sxemasi ikki raqamni taqqoslaydigan qurilma X 1 va x 2, ikkilik sanoq sistemasida berilgan. Ushbu qurilma quyidagicha ishlaydi. Raqamlar raqamlari qurilmaning kirish qismiga eng muhimlaridan boshlab ketma-ket kiritiladi. X 1 va x 2. Bu raqamlar taqqoslanadi. Agar zanjirning chiqishida bitlar bir-biriga to'g'ri kelsa, 0 ga teng chiqish signali hosil bo'ladi, aks holda chiqishda 1 ning ko'rinishi raqamlarning solishtirilishini bildirishi aniq X 1 va x 2 har xil. Agar chiqish ketma-ketligi nolga teng bo'lsa va uning uzunligi taqqoslangan raqamlarning raqamlari soniga to'g'ri kelsa, u holda X 1 va x 2 .

Ushbu mashina uchun X ={00, 01, 10, 11}; Y ={0,1}.

Devrenning ishlashi ikki holat bilan belgilanadi. Davlat q 0 hozirgi taqqoslanayotgan raqamlarning tengligiga mos keladi. Bunday holda, mashina bir xil holatda qoladi. Agar keyingi daqiqada taqqoslangan raqamlar boshqacha bo'lsa, mashina yangi holatga o'tadi q 1 va unda qoladi, chunki bu raqamlar boshqacha ekanligini anglatadi. Shunday qilib, taqqoslash sxemasi jadval bilan belgilanishi mumkin:

Tenglikni taqqoslash sxemasining Mur diagrammasi rasmda ko'rsatilgan. 6.

Biz shtatlarni quyidagicha kodlaymiz:  (q 0)=0,  (q 1)=1. Mashina ikkita funktsiya bilan belgilanadi.

Misol 4. Tengsizlikni taqqoslash sxemasi.

Tengsizlikni taqqoslash sxemasi - bu taqqoslanayotgan narsalarning teng yoki yo'qligini aniqlash imkonini beruvchi qurilma. X 1 va x 2, agar ular teng bo'lmasa, qaysi biri ikkinchisidan katta ekanligini aniqlang. Ushbu qurilma ikkita kirish va ikkita chiqishga ega. Chiqish signallari y 1 (t ) Va y 2 (t ) quyidagi qoidalarga muvofiq belgilanadi:

y 1 (t )=y 2 (t )=0, agar x 1 (t )=x 2 (t );

y 1 (t )=1, y 2 (t )=0, agar x 1 (t )>x 2 (t ), ya'ni x 1 (t )=1, x 2 (t )=0;

y 1 (t )=0, y 2 (t )=1, agar x 1 (t )<x 2 (t ), ya'ni x 1 (t )=0, x 2 (t )=1.

Shunday qilib, raqamlarning tengsizligi uchun taqqoslash sxemasining kirishiga oziqlanganda x 1 =x 1(l)… x 1 (t ) Va x 2 =x 2(l)… x 2 (t )bu raqamlarning raqamlari eng muhimlaridan boshlab ketma-ket taqqoslanadi. Chiqish signallari yuqoridagi qoidalarga muvofiq tuzilgan. Bundan tashqari, agar chiqish ketma-ketligi nol juftlikdan iborat bo'lsa, u holda x 1 =x 2. Agar birinchi nolga teng bo'lmagan juftlik shaklga ega bo'lsa , () Bu x 1 >x 2 (x 1 <x 2).

Sxemaning tavsifidan kelib chiqadiki

X ={00, 01, 10, 11}, Y ={00, 01, 10}.

Sxemaning holati quyidagicha aniqlanadi. Tasavvur qilaylik, vaqtning dastlabki momentida t =1 ta mashina holatda q 1 . Agar raqamlarning taqqoslangan raqamlari X 1 Va X 2 mos keladi, keyin mashina shu holatda qoladi. E'tibor bering, agar raqamning raqami bo'lsa, chiqishda 00 signali paydo bo'ladi X 1 raqamning mos keladigan raqamidan kichik (katta) bo'ladi X 2, keyin mashina holatga o'tadi q 2 (q 3). Bunday holda, chiqishda 01 (10) signal paydo bo'ladi. Keyinchalik, raqamlarning qolgan raqamlarini topshirishda X 1 Va X 2 mashinaning kirishlariga, mashina holatda qoladi q 2 (q 3) va 10 (01) chiqish belgisini hosil qiling. Yuqoridagilardan kelib chiqadiki, tengsizlikni taqqoslash sxemasi jadval orqali aniqlanishi mumkin:

Tegishli Mur diagrammasi rasmda ko'rsatilgan. 7.

Kirish va chiqish alifbolari bu yerda allaqachon kodlangan. Shtatlar q 1 , q 2 va q Keling, 3 ni kodlaymiz:  1 (q 1)=00,  (q 2)=01,  (q 3)=10.

Shuning uchun, bu sxema to'rtta o'zgaruvchiga bog'liq bo'lgan to'rtta mantiqiy funktsiyadan tashkil topgan tizim tomonidan aniqlanishi mumkin. Bu funksiyalar qisman aniqlanadi va haqiqat jadvali bilan beriladi

Jadvalda * belgilari o'zgaruvchilar to'plamini belgilaydi x 1 , x 2 , z 1 , z 2, qaysi funksiyalar  1 ,  2 ,  1 ,  2 aniqlanmagan. Keling, qo'ying funktsiya qiymatlari  1 ,  2 ,  1 ,  Ushbu to'plamlarda 2 1 ga teng.

Cheklangan holat mashinalari nazariyasi

Avtomatlar nazariyasi kompilyatorni qurish nazariyasi asosida yotadi. Cheklangan holat mashinasi asosiy tushunchalardan biridir. Avtomat deganda biz haqiqatda mavjud bo'lgan texnik qurilmani nazarda tutmaymiz, garchi bunday qurilmani qurish mumkin bo'lsa-da, lekin uning xususiyatlari va xatti-harakatlari kompyuterdagi dastur yordamida taqlid qilinishi mumkin bo'lgan ma'lum bir matematik modeldir. Cheklangan avtomat avtomatlar nazariyasining eng oddiy modeli bo'lib, qoida tariqasida, boshqa barcha turdagi avtomatlar uchun boshqaruv qurilmasi bo'lib xizmat qiladi. Cheklangan holat mashinasi bir qator xususiyatlarga ega:

· Davlat mashinasi bir qator engil kompilyatsiya muammolarini hal qilishi mumkin. Leksik blok deyarli har doim chekli holat mashinasi asosida quriladi.

· Cheklangan holat mashinasining ishlashi yuqori unumdorligi bilan tavsiflanadi.

· Davlat mashinasini modellashtirish uchun qattiq xotira hajmi talab qilinadi, bu esa xotirani boshqarishni osonlashtiradi.

· chekli holat mashinalarini qurish va soddalashtirish imkonini beruvchi bir qancha teorema va algoritmlar mavjud.

Adabiyotda chekli holat mashinasining turli xil ta'riflari mavjud. Biroq, ularning umumiy tomoni shundaki, cheklangan holat mashinasi ma'lum bir kirish to'plamiga tegishli kirish belgilarining ketma-ketligini o'qiydigan qattiq xotira hajmiga ega hisoblash qurilmasini modellashtiradi. Ta'riflardagi asosiy farqlar mashinaning chiqishda nima qilishi bilan bog'liq. Mashinaning chiqishi ma'lum bir kirish zanjiri "qabul qilinadi" yoki yo'qligini ko'rsatishi mumkin. "Qabul qilinadi" - bu to'g'ri tuzilgan yoki sintaktik jihatdan to'g'ri zanjir. Masalan, raqamli konstantani ifodalashi kerak bo'lgan zanjir, agar u ikkita kasrdan iborat bo'lsa, noto'g'ri tuzilgan hisoblanadi.

Ta'rif: Cheklangan holat mashinasi - bu quyidagi ob'ektlar yordamida aniqlangan rasmiy tizim:

· kirish belgilarning chekli to'plami;

· holatlarning chekli to'plami;

· har bir juftlikka (joriy holat, kirish belgisi) yangi holatni tayinlaydigan o'tish funktsiyasi;

· boshlang'ich holati;

· ruxsat beruvchi yoki yakuniy deb belgilangan davlatlar kichik to'plami.

Misol. Nol va birliklardan tashkil topgan ixtiyoriy zanjirda birliklar sonining juft yoki toq ekanligini tekshiradigan kontroller ishini tahlil qilaylik. Faraz qilaylik, mos keladigan chekli avtomat toq sonli barcha zanjirlarni "qabul qilishi" va juft sonli zanjirlarni "rad etishi" kerak. Keling, ushbu mashinani "paritet boshqaruvchisi" deb ataymiz. Ishonamizki, 0 va 1 dan boshqa belgilarni mashina kiritishiga kiritish mumkin emas. Shunday qilib, boshqaruvchining kirish alifbosi to'plamdir (0, 1) . Biz ishonamizki, ma'lum bir vaqtda cheklangan avtomat faqat bitta kirish belgisi bilan ishlaydi va chekli holatlar to'plamidan foydalangan holda kirish zanjirining oldingi belgilari haqidagi ma'lumotlarni saqlaydi. To'plamni (juft, toq) holatlar to'plami sifatida ko'rib chiqamiz, bu holatlardan biri boshlang'ich sifatida tanlanishi kerak; Bu holat (juft) bo'lsin, chunki birinchi bosqichda o'qilganlar soni nolga teng, nol esa juft son. Keyingi kirish belgisini o'qiyotganda, mashinaning holati o'zgaradi yoki bir xil bo'lib qoladi va uning yangi holati kirish belgisi va joriy holatga bog'liq. Ushbu holat o'zgarishi o'tish deb ataladi.

Mashinaning ishlashini d(Scurrent, x) = Snew ko'rinishidagi o'tish funksiyasi bilan matematik tarzda tasvirlash mumkin. Aks holda u quyidagicha yozilishi mumkin:

d(juft, 0) = juft. d (juft, 1) = toq.

d (toq, 0) = toq. d(toq, 1) = juft.

Tekshirgich yagona qabul qiluvchi holatga ega, ODD va EVEN "rad etuvchi" holatdir. 1101 zanjiri uning kirishiga etkazib berilganda, mashinaning o'tish ketma-ketligini aks ettiramiz.

EVEN ® ODD ® EVEN ® EVEN ® ODD

Bunday avtomatning o'tish jadvali quyidagi shaklga ega:

Ta'rif. Cheklangan holat mashinasi rasmiy tizimdir

S = ( A, Q, d, l, V ),

ularning ob'ektlari quyidagilar:

* A - kirish belgilarining cheklangan to'plami (to'plam

terminallar);

* Q - avtomatning ichki holatlarining chekli to'plami

(terminal bo'lmaganlar to'plami);

* V - chiqish belgilarining chekli to'plami (chiqish alifbosi);

* d - A ´ Q ® Q bilan tavsiflangan o'tish funktsiyasi;

* l - ko'rinishning ko'rinishini aniqlaydigan chiqish funktsiyasi.

Avtomatlar nazariyasi

Mashinaning ta'rifi va uning xilma-xilligi. O'tish va chiqishlarning jadvallari va grafiklari. Sub-avtomatik mashinalar. Qisqartirilgan avtomat teoremasi

Mashinalar bilan operatsiyalar

Mealy mashinasini Mur mashinasiga va Mur mashinasini Mealy mashinasiga aylantirish. Avtomatlarning ekvivalenti. Avtomatlarning holatini farqlash. Avtomatlarni minimallashtirish. Avtomatlarning sintezi. Tanish mashinalari

Avtomatik mashina - bu energiya, materiallar va ma'lumotlarni qabul qilish, aylantirish va uzatish jarayonlari to'liq avtomatlashtirilgan mexanizmlar va qurilmalar tizimi "Avtomatik mashina" atamasi ikki jihatdan ishlatiladi:

1) texnik,

2) matematik.

Matematik yondashuvda avtomat deganda texnik qurilmaning matematik modeli tushuniladi, u kirishlar, ichki holatlar va chiqishlarga ega bo'lishi kerak. Qurilmaning tuzilishi tafsilotlari haqida hech qanday ma'lumot bo'lmasligi kerak.

Texnik yondashuvda mashina deganda juda haqiqiy qurilma tushuniladi, masalan, telefon kabinasi, savdo avtomati va boshqalar.Bu holda, tabiiyki, qurilmaning ichki tuzilishining tafsilotlari ma'lum.

Avtomatning alohida va muhim holati raqamli avtomat (DA) bo'lib, unda raqamli ma'lumotlarni qabul qilish, o'zgartirish, saqlash va berish jarayonlari to'liq avtomatlashtirilgan.

DA signallari nuqtai nazaridan kirish signallarini qabul qila oladigan, ularning ta'siri ostida bir holatdan ikkinchi holatga o'tadigan, keyingi kirish signali kelguncha uni saqlab turadigan va chiqish signallarini ishlab chiqaradigan tizimni aniqlash foydalidir.

Agar X kirish signallari, S holatlari va Y chiqish signallari to'plami chekli bo'lsa, DA chekli hisoblanadi. Kompyuter kiruvchi kirish ma'lumotlarini chiqish ma'lumotlariga (natijaga) qayta ishlaydi, lekin bu natija nafaqat kirish ma'lumotlariga, balki kompyuterning joriy holatiga ham mos keladi, ya'ni. kompyuter xotirasida saqlanadigan ma'lumotlar, masalan, oldingi hisob-kitoblar natijalari, hisoblash dasturlari.

Maqsadli auditoriyaning ishi kirish signallarini qabul qilish davrlari soni bilan belgilanadigan avtomatik vaqtda amalga oshiriladi.

Mavhum avtomat - bu bitta kirish kanaliga ega bo'lgan, til belgilarining ketma-ketligini, bitta chiqish kanaliga ega bo'lgan, boshqa biron bir tilning belgilar ketma-ketligi olinadigan va har bir daqiqada qandaydir holatda bo'lgan diskret qurilmaning matematik modeli. diskret vaqt. Grafik jihatdan mavhum avtomat tasvirda keltirilgan.

Kiritish tilidagi so'zlar X=(x 1 ,x 2 ,...x n ) to'plamning belgilari bilan ifodalanishi mumkin, bu deyiladi. kirish alifbosi, va chiqish tilining so‘zlari Y=(y 1 ,y 2 ,...y p ) to‘plamning belgilari bo‘lib, ular deyiladi. chiqish alifbosi. Avtomatning S=(s 1 ,s 2 ,...s m ) holatlar to‘plami deyiladi. davlatlar alifbosi.

Kontseptsiya mashina holati chiqish signallari faqat ma'lum bir vaqtda kirish signallariga emas, balki ba'zi bir oldingi tarixga bog'liq bo'lgan tizimlarni tavsiflash uchun ishlatiladi, ya'ni. tizim kirishlarida ilgari qabul qilingan signallar. Shuning uchun, raqamli avtomatlar, yuqorida aytib o'tilganidek, xotiraga ega bo'lgan ketma-ket sxemalarni anglatadi. Avtomatning holati tushunchasi o'tmishdagi ba'zi xotiralarga mos keladi, shuning uchun bu kontseptsiyaning kiritilishi vaqtni aniq o'zgaruvchi sifatida yo'q qilishga va natijalarni holatlar va kirishlar funktsiyasi sifatida ifodalashga imkon beradi.

Mavhum avtomatning ishlashi muayyan vaqt oraliqlariga nisbatan ko'rib chiqilishi kerak, chunki har bir diskret interval t uning chiqish signaliga y(t) mos keladi. Shunday qilib, mashinaning ishlashi cheklangan davomiylikdagi diskret vaqt oraliqlari orqali ko'rib chiqiladi. Raqamli avtomatlarning mavhum nazariyasida kirish signallari har birining boshida sinxron avtomatda ishlaydi, deb ishoniladi. i- mos keladigan sinxronizatsiya impulsi (tsikl) tomonidan ajratilgan vaqt oralig'i (kvantalari) va mashinaning ichki holatidagi o'zgarishlar kirish signallarining ta'siri bo'lmaganda, qo'shni sinxronlash impulslari orasidagi vaqt oralig'ida sodir bo'ladi.

"Holat" tushunchasi mashina tomonidan yaratilgan chiqish tilining belgilari va/yoki so'zlarining kirish tilining belgilari va/yoki so'zlariga funktsional bog'liqligini, mashina berilgan algoritmni amalga oshirishda o'rnatish uchun ishlatiladi. Avtomatning har bir holati uchun sOS va diskret vaqt [t] momentidagi har bir xOX belgisi uchun qurilma chiqishida yOY belgisi hosil bo'ladi. Bu bog'liqlik j avtomatining chiqish funksiyasi bilan aniqlanadi. Avtomatning har bir joriy holati uchun sOS va har bir xOX belgisi uchun diskret vaqt [t] momentida avtomat keyingi sOS holatiga o'tadi. Bu bog'liqlik y avtomatining o'tish funksiyasi bilan aniqlanadi. Avtomatning ishlashi ikkita ketma-ketlikni yaratishdan iborat: avtomatning keyingi holatlari ketma-ketligi (s 1[ s 2 s 3 ...) va chiqish belgilarining ketma-ketligi (y 1 y 2 y 3 ...), Belgilar ketma-ketligi uchun (x 1 x 2 x 3...) diskret vaqt momentlarida ochiladi t = 1,2,3,.... To'rtburchaklar qavslarda diskret vaqt momentlari ko'rsatiladi, ular aks holda soat sikllari deb ataladi. , qavs ichida - X, Y va S alifbolari belgilari ketma-ketligi.

Demak, chekli avtomatning matematik modeli uch asosli algebra bo‘lib, uning tashuvchilari uchta X, Y va S to‘plamlar, amallari esa ikkita j va y funksiyalardir.