Uy > Psixologiya > Foydali harakatlarni bajaradigan mavhum mashinalarga misollar. Avtomatik mashina - bu turli holatlarni qabul qilishga qodir, kirish signallari ta'siri ostida bir holatdan ikkinchisiga o'tadigan va chiqadigan diskret axborot konvertori.


Foydali harakatlarni bajaradigan mavhum mashinalarga misollar. Avtomatik mashina - bu turli holatlarni qabul qilishga qodir, kirish signallari ta'siri ostida bir holatdan ikkinchisiga o'tadigan va chiqadigan diskret axborot konvertori.




Mavzu 5.1. Davlat mashinalari yordamida ma'lumotlarni qayta ishlash

5-bob. Cheklangan avtomatika nazariyasi asoslari

Mavzuning qisqacha mazmuni

Takrorlash uchun savollar

1. Yo‘nalishni xohlaysizmi?

2. Qaysi holatda yo'nalish tsikl deb ataladi?

3.Zanjir nima?

4. Qaysi holatda zanjir oddiy zanjir?

5. Eyler tsikliga ta'rif bering?

6. Eyler va Gamilton tsikllari o'rtasidagi farq nima?

7. Graf qachon daraxt deb ataladi?

8. O'rmonning qanday bog'liq qismlari bor?

9. Yuqori qismi oxir deb ataladi, agar?

Ushbu mavzu marshrut, tsikl, kontur, kontur va hokazolar kabi tushunchalarni grafiklarga murojaat qilgan holda ko'rib chiqadi. Eyler va Gamilton davrlari berilgan. Daraxt sifatida belgilangan alohida grafik tuzilishi ko'rsatilgan. Ushbu tuzilmalarning kombinatsiyasi o'rmon sifatida tavsiflanadi.

Maqsad: cheklangan avtomatika nazariyasining asoslarini ko'rib chiqing.

Vazifalar:

1. Mavhum avtomat tushunchasini ko'rib chiqish.

2. Mashinalarni o'rnatish usullarini aniqlang.

3. Mil va Moore automata o'rtasidagi bog'liqlikni ko'rib chiqing.

Avtomatik  - kirish signallari ta'sirida holatdan holatga o'tish va chiqish signallarini ishlab chiqarishga qodir diskret axborot konvertori.

Mavhum avtomat quyidagi besh to'plam yordamida aniqlanadi:

A = (X, Y, S, d, l),

qayerda X = (X 1, X 2 ... X M)  - avtomatning kirish alifbosi yoki kiritish belgilarining to'plami;

Y = (Y 1, Y 2 ... Y N)  - avtomatning chiqish alifbosi yoki chiqish belgilarining to'plami;

S = (S 0, S 1 ... S K-1)  - alfavit yoki avtomatning ichki holatlari to'plami;

S 0  - mashinaning dastlabki holati (o'sha paytda) t = 0).

d  - o'tish funktsiyasi;

l- mashinaning funktsional chiqishi.

Mashina chaqiriladi davlat mashinasi agar to'plam bo'lsa X, Y, S  cheklangan (yoki hisoblash mumkin).

Mashina o'z vaqtida diskret nuqtalarda ishlaydi. t = 0, 1, 2 ... n(5.1-rasm) .

Shakl 5.1. Davlat mashinasi

Har qanday vaqtda, avtomat to'plam holatidan birida S.

O'tish funktsiyasi d tjoriy holatga va kirish signali yoki kirish alifbosi belgisiga qarab mashinaning keyingi holati. Boshqacha aytganda, funktsiya dhar bir "holat - kirish signali" mos keladigan holda quyidagi holatni o'rnatadi.

d: S´X ® S; d- karteziya mahsulotining xaritasi mavjud S´x  ichida S.

O'tish funktsiyasi quyidagicha yozilishi mumkin: S t + 1 = d (S t, X t).

Chiqish funktsiyasi lhar bir vaqt nuqtasida aniqlaydi tmashinaning chiqish signali.

Avtomatik mashinalarning ikkita modeli mavjud - Mile avtomati va Moore pulemyoti. Ular chiqish vazifalarida farqlanadi, bu quyidagicha aniqlanadi:


Y t = l (S t, X t)  - Mil uchun, yoki l: S´X®Y.

Y t = l (S t)  - Murning avtomati uchun.

Milda, chiqish vaqti signal t  Vaqtning ikkala kirish signaliga bog'liq t, va hozirgi holatdan.

Murning avtomatida chiqish signali kirishga aniq bog'liq emas va faqat joriy holat bilan belgilanadi.

Mashina holati- Bu o'tgan kirish effektlarining avtomatik xotirasi.

Automata ham deyiladi ketma-ket mashinalar   (Sequential Machines), chunki kirish ketma-ketligi holatlar va chiqish ketma-ketligiga aylantiriladi.

Aytish mumkinki, mavhum avtomat 1 kirish va 1 chiqishi bor. Mashinaning kirish qismi kirish alfavitining harflari ketma-ketligini oladi, chiqish ketma-ketliklari chiqishda hosil bo'ladi.

So'z  yoki zanjir   - Bu kirish alifbosidagi belgilar (harflar) ning oxirgi ketma-ketligi. Quyidagi shartlar bajarilishi kerak (avtomatizm shartlari):

1. Kirish va chiqish so'zlarining uzunligi bir xil;

2. Kirish so'zlarining bir xil boshlang'ich segmentlari chiqish so'zlarining bir xil boshlang'ich segmentlariga mos keladi.

  • 1.1 Asosiy tushunchalar
  • Xulosa
  • Adabiyotlar ro'yxati

Kirish

Nazorat ishining mavzusi "Raqamli avtomatlashtirishning amaliy nazariyasi" - "Mavhum raqamli avtomatika".

Ishning maqsadi - mavhum raqamli avtomatlashtirishning asosiy tushunchalari bilan tanishish; mavhum mashinalarning turlari; mavhum avtomatlashtirishni sozlash usullari; Mile va Moore modellari o'rtasidagi aloqa; ekvivalent avtomatika va avtomatika ekvivalent transformatsiyalari; Avtomat va Aufenkamp-Xon algoritmining ichki holatlari sonini minimallashtirish.

1. Mavhum raqamli mashinalar

1.1 Asosiy tushunchalar

Raqamli avtomatika ba'zi algoritmga muvofiq diskret ma'lumotlarni qabul qiladigan, saqlaydigan va o'zgartiradigan qurilma sifatida talqin qilinishi mumkin. Muayyan nuqtai nazardan, ikkala haqiqiy qurilmalarni (kompyuterlarni) va mavhum tizimlarni (matematik modellar) avtomatlashtirishga kiritish mumkin.

Avtomatik mashina bu turli holatlar qabul qilishga qodir, kirish signallari ta'siri ostida bir holatdan ikkinchisiga o'tadigan va chiqish signallarini chiqarishga qodir diskret axborot konvertori.

Avtomatlashtirishning umumiy nazariyasi mavhum va tarkibiy qismlarga bo'linadi.

Avtomatlashtirishning mavhum nazariyasi, avtomatning tuzilishidan chalg'itadi (ya'ni uni qurish usuliga qiziqmasdan), faqat tashqi muhitga nisbatan avtomatika xatti-harakatlarini o'rganadi. Avtomatlashtirishning mavhum nazariyasi algoritmlar nazariyasiga yaqin bo'lib, uni keyinchalik amalga oshirishga imkon beradi.

Avtomatizatsiyaning mavhum nazariyasidan farqli o'laroq, avtomatika tarkibiy nazariyasi avtomatning o'zi va avtomatning kirish harakatlari va reaktsiyalarining tuzilishiga qiziqadi. Strukturaviy nazariya avtomatika tuzish usullarini, kirish harakatlarini kodlash usullarini va ularga avtomat reaktsiyalarni o'rganadi. Avtomatlashtirishning tizimli nazariyasi mavhum nazariyaning davomi va rivojlanishi hisoblanadi. Boolean funktsiyalari apparati va avtomatlashtirishning mavhum nazariyasiga asoslanib, tizimli nazariya haqiqiy hisoblash qurilmalarini rivojlantirish bo'yicha samarali tavsiyalar beradi.

Mavhum raqamli avtomat (CA) bu diskret boshqaruv moslamasining matematik modelidir.

Xulosa CA olti elementdan iborat to'plam bilan aniqlanadi:

S = (X, A, Y, ao),

qayerda:

X = (x1, x2,. Xn) - kirish signallarining to'plami (kirish alifbosi);

Y = (y1, y2, ym) - chiqish signallarining to'plami (chiqish alifbosi);

A = (a0, a1, a2,. AN) - bu davlatlar to'plami (davlatlar alifbosi);

ao - boshlang'ich holat (aoA);

- (XXA) A xaritasini aniqlaydigan avtomatika o'tish funktsiyasi, ya'ni. Karteziya mahsulotining har qanday juftligini (XxA) A to'plamning elementi bilan bog'lash;

- xaritani (XxA) Y ni yoki AY xaritasini aniqlaydigan avtomatning chiqish funktsiyasi.

Boshqacha qilib aytganda, o'tish funktsiyasi S avtomati ajA holatida bo'lganda, xjX kirish signali paydo bo'lganda apA holatiga o'zgarishini ko'rsatadi. Buni quyidagicha yozish mumkin:

ap = (ai, Xj).

Chiqish funktsiyasi   avtomatika S ajA holatida bo'lganda, xjX kirish signali paydo bo'lganda ykY chiqish signalini chiqaradi. Buni quyidagicha yozish mumkin: uk = (ai) ,   Xj).

Avtomatika ta'rifida davlat tushunchasi ko'pincha chiqishlarning nafaqat ma'lum vaqtdagi holatiga, balki ma'lum bir tarixgacha bo'lgan tizimlarga bog'liq bo'lgan tizimlarning xatti-harakatlarini tavsiflash kerakligi sababli kiritildi. ilgari tizim kirishlariga kelgan signallardan. Holat shunchaki o'tmishdagi ba'zi xotiralarga mos keladi, bu sizga aniq o'zgaruvchan sifatida vaqtni yo'q qilishga va chiqish signallarini ma'lum bir vaqtning o'zida davlatlar va kirishlar funktsiyasi sifatida ifodalashga imkon beradi.

Diskret avtomat vaqtidagi mavhum avtomat t = 0,1,2,. va davlatdan davlatga o'tish bir zumda. Diskret vaqtning har bir lahzasida, avtomat A holatidan A (t) ma'lum bir holatda, va t = 0 boshlang'ich vaqtda u doimo boshlang'ich holatda bo'ladi ao. T vaqtida, a (t) ga ega bo'lganda, avtomat kirish kanalidagi x (t) X signalini sezadi va chiqish kanalida y (t) = (a (t), x (t)) signalni uzatadi. holatga a (t + 1) = = (a (t), x (t)). Chiqish signalining kirishga va holatga bog'liqligi uning xotiraga ega ekanligini anglatadi.

1.2 Mavhum mashinalarning turlari

Chiqish funktsiyalarini shakllantirish usuliga ko'ra, uchta mavhum avtomat ajralib turadi: milya avtomati, Mur avtomati, C avtomati. Mili avtomati quyidagi tenglamalar tizimi bilan tavsiflanadi:

y (t) = (a (t), x (t));

a (t + 1) = d (a (t), x (t)). (1-1)

Mur avtomati - tenglamalar tizimi:

y (t) = (a (t));

a (t + 1) = d (a (t), x (t)). (1-2)

S-avtomat - tenglamalar tizimi:

y = y1y2

y1 (t) = (a (t), x (t));

Y2 (t) = 2 (a (t));

a (t + 1) = d (a (t), x (t)).

O'zboshimchalik bilan mavhum mashina Miles yoki Mura (1.1-rasm) bitta kirish va bitta chiqish kanaliga ega. O'zboshimchalik bilan mavhum C-avtomat bitta kirish va ikkita chiqish kanaliga ega (1.2-rasm).

Shakl 1.1 - mavhum mashina

Rasm.1.2 Mavhum C-avtomat

Agar mavhum Mile yoki Moore avtomatining kiritilishi ao boshlang'ich holatiga o'rnatilgan bo'lsa, kirish alifbosi x (0), x (1), harflari ketma-ketligini harf bilan yuboring. - kirish so'zi, so'ngra mashinaning chiqishida chiqish alfavitining harflari y (0), y (1), paydo bo'ladi. - chiqish so'zi. C-avtomat uchun uning chiqishlarida ikkita ketma-ketlik paydo bo'ladi: y1 (0), y1 (1),. va y2 (0), y2 (1),. Xulosa C - avtomatiyada y2 (t) = (a (t)) chiqish signali avtomatik ravishda a (t) holatida bo'ladi. Chiqish signali y1 (t) = l1 (a (t), x (t)) C-avtomat a (t) holatida bo'lganida x (t) kirish signali davomida beriladi.

Shunday qilib, mavhum nazariya darajasida raqamli avtomatning ishlashi kirish so'zlarini chiqish so'zlariga aylantirish deb tushuniladi.

To'liq aniqlangan va qisman avtomatika ajralib turadi.

O'tish funktsiyasi yoki chiqish funktsiyasi yoki ushbu funktsiyalarning ikkalasi ham o'tishning barcha juftlari (xi, aj) uchun aniqlangan mavhum raqamli avtomatika to'liq aniqlangan deb nomlanadi.

Qisman - bu o'tish holati yoki chiqish funktsiyasi yoki ikkalasi ham barcha o'tish juftlari uchun aniqlanmagan mavhum raqamli avtomat (xi, aj).

Agar boshlang'ich holat ao uning A holatlari to'plamida ajralib tursa, mavhum raqamli avtomat deyiladi.

1.3 Mavhum avtomatlashtirishni sozlash yo'llari

Shtat mashinasini aniqlash uchun S ning barcha elementlarini tavsiflash kerak: S = (X, A, Y, ao). Mashinaning ishlashini belgilashning bir necha usullari mavjud, ammo eng ko'p ishlatiladigan - jadvalli (matritsa), grafik, analitik.

Jadval usulida avtomat ikkita jadval bilan belgilanadi: o'tish jadvali va chiqish jadvali yoki aralashmalarning matritsasi. O'zboshimchalik bilan to'liq aniqlangan avtomatika o'tish jadvali quyidagicha tuziladi: jadvalning satrlari avtomatning kirish alifbosi harflari bilan, jadvalning ustunlari - avtomat holati alfavitining harflari bilan belgilanadi; Bu erda joylashgan katakchalarga o'tish jadvali kirish signali xi va aj holati bilan belgilangan ustun bilan belgilangan chiziqning kesishishi ak = holati bilan belgilanadi, bu ak = (aj, xj) ifodasi bilan belgilanadigan kirish signali xi ta'siri ostida avtomatdan aj holatiga o'tadi.

1.1-jadval. O'tish jadvali mashinasi

1.2. Jadvalda ba'zi bir mavhum to'liq aniqlangan avtomatlashtirilgan o'tish alifbosi bilan X = (x1, x2) - va alfavit A = (a1, a2, a3) o'tish jadvalini to'ldirish misoli keltirilgan.

1.2-jadval

Agar mavhum avtomat qisman bo'lsa, u holda uning o'tish jadvali katakchasida, kirish signali va tegishli holat bilan belgilangan chiziqning kesishgan qismida (ushbu kirish signalining ta'siri ostida ushbu holatga o'tish aniqlanmagan bo'lsa), chiziqcha qo'yiladi va har qanday kirish so'zi mavjud. ko'rsatilgan o'tishning boshlanishiga yo'l qo'yilmaydi.

Qolgan hujayralarni to'ldirish to'liq aniqlangan avtomat holatiga o'xshaydi. O'tish jadvalining ko'rinishi ko'rsatilgan avtomat (Mili, Mura, C-avtomat) turiga bog'liq emas. Mile, Moore, C-automaton avtomatlarining chiqish jadvallarida farqlar mavjud.

To'liq aniqlangan Miles mashinasining chiqish jadvali quyidagicha tuzilgan: ustunlar va satrlarni identifikatsiyalash, shuningdek jadvalning formati to'liq aniqlangan mashinaning o'tish jadvaliga mos keladi. Kirish signali Xj va ak holati bilan belgilangan ustun bilan kesishgan chiziqning kesishmasida joylashgan chiqish stolining katakchasida Ym chiqish signali qo'yiladi, u mashinada ishlab chiqariladi, u Yj = (ak, xj) ifoda bilan aniqlanadi, kirish signali Xj bilan. ).

1.3-jadval mavhum Miles avtomatining chiqish jadvali.

1.1. Jadvalda ba'zi bir mavhum to'liq aniqlangan avtomatning kirish alifbosi X = (x1, x2), davlat alifbosi A = (a1, a2, a3) va chiqish alifbosi Y = (y1, y2, y3) bilan to'ldirish misoli 1.1-jadvalda keltirilgan.

1.4-jadval

Shubhasiz, to'liq aniqlangan C-avtomat ikkita chiqish jadvallari tomonidan berilgan, ularning birinchisi Mile mashinasining chiqish jadvali, ikkinchisi - Mura. Agar avtomat qisman bo'lsa, unda uning jadvalining ba'zi hujayralarida tire bo'lishi mumkin, bu chiqish signalini anglatmaydi.

Amalda, o'tish va chiqish jadvallari ko'pincha bitta jadvalga birlashtirilib, belgilangan avtomat o'tish jadvali deb nomlanadi. Belgilangan o'tish jadvallariga misollar 1.6-jadvalda keltirilgan. - 1.8 (Belgilangan o'tish stolining umumiy ko'rinishi - 1.6-jadval., Mili pulemyotining belgilangan o'tish jadvali - 1.7-jadval., Mur avtomatining belgilangan o'tish jadvali - 1-jadval. 1.8.).

Yuqorida muhokama qilingan o'tish va chiqish jadvallariga qo'shimcha ravishda ixtiyoriy mavhum avtomat birikmalar matritsasi bilan berilishi mumkin.

Murakkablarning matritsasi to'rtburchaklardir va ko'p sonli ustunlarni (qatorlarni) o'z ichiga oladi, chunki har xil shtatlar ushbu avtomat holatlarining alfavitiga ega. Murakkab matritsaning har bir ustunida (qatorida) mashinaning holati ko'rsatilgan. Aj harfi bilan va ustun bilan avtomashinaning harfi bilan belgilangan chiziqning kesishmasida joylashgan kamerada kirish signali (yoki kirish signallarining uzilishi) ta'sirida, bu o'tish sodir bo'ladi.

Miles mavhum avtomati uchun chiqish signali ushbu o'tish natijasida avtomat vujudga keltiradigan holatning yonidagi kameraga joylashtiriladi (1.9-jadval.) Murning avtomati uchun chiqish signali shtatning yonidagi qatorga qo'yiladi (bu holatlar avtomatning dastlabki holatlariga to'g'ri keladi).

1.6-jadval

1.8-jadval

Mavhum avtomatlashtirishni grafik usulida yo'naltirilgan grafikalar keltirilgan. Avtomat grafigi yo'naltirilgan bog'langan grafik bo'lib, uning uchlari avtomat holatiga to'g'ri keladi va ularning orasidagi yoylar davlatlar orasidagi o'tishni anglatadi. Agar ikkita avtomatika ak holatidan holatga o'tgan bo'lsa, ak va ikkita vertikal o'qlar boshq bilan bog'lanadi. Miles avtomati uchun kirish va chiqish signallari ushbu o'tish mos keladigan yoyga qo'yiladi (1.3-rasm), Moore mashinasi uchun kirish signali yoyga qo'yiladi va chiqish signali holatga mos keladigan cho'qqiga yaqinlashadi (1.4-rasm).

Bu erda biz faqat o'tish avtomatining yagona o'ziga xos shartiga ega bo'lgan deterministik avtomatiyani ko'rib chiqamiz: ma'lum bir holatda bo'lgan avtomat har qanday kirish signalining ta'siri ostida bir nechta holatga aylantirilishi mumkin emas. Avtomatni aniqlashning grafik usuliga murojaat qilsak, bu avtomat grafasida bir xil kirish signali bilan belgilangan ikki yoki undan ortiq yoylar har qanday tepadan chiqa olmaydi degan ma'noni anglatadi.

1.3-rasm - Milning avtograf grafigi 1.4-rasm - Murning avtograf grafigi

Mavhum avtomatlashtirishni analitik usulida to'rtta ob'ekt berilgan:

S = (X, A, Y, F), bu erda F xaritaning xar bir holati uchun xaritani o'rnatadi (XxA) - >   (AxY). Boshqacha qilib aytganda, avtomatizaning har bir holatini aniqlashning analitik usulida ar, xm, yk va uchliklarning yig'indisi bo'lgan Fai xaritasi ko'rsatilgan va shunday qilib kirish signali xm ta'siri ostida avtomat shtatdan o'tib ketadi. aj ichida  holat ar, chiqish signalini berganda yk.

Mavhum avtomatiyaning umumiy ta'rifiga kelsak, ikkinchisi g va l funktsiyalarining ifodasiga muvofiq: ap = g (ai, xm), yc = l (ai, xm).

Fai xaritasi quyidagicha yozilgan:

Fai (ap (Xm / yk), ai (Xf / yz) ...).

Miles mavhum avtomati uchun (1.7-jadval), analitik vazifa quyidagi shaklga ega:

S = (X, A, Y, F), X = (x1, x2), A = (a1, a2, a3), Y = (y1, y2, y3),

Fa1 = (a2 (x1 / y2), a1 (x2 / y3)),

Fa2 = (a3 (x1 / y3), a1 (x2 / y1)),

Fa3 = (a1 (x1 / y3), a2 (x2 / y2)).

Shuni ta'kidlash kerakki, Fai funktsiyasi doimo boshlang'ich holat uchun qayd etiladi.

Sinxron va asenkron avtomatika aniqlaymiz. Agar avtomat holati S holati barqaror holat deyiladi, agar har qanday kirish signali xjX uchun, masalan a = d (ai Xm) = d (as, xm) bo'lsa.

Agar S ning har bir holati barqaror bo'lsa, avtomat S asinxron deb ataladi. Agar avtomat S sinxron bo'lmasa, sinxron deb ataladi.

Ta'kidlash joizki, amalda yaratilgan avtomatika doimo asenkron bo'lib, ularning holati barqarorligi har doim qandaydir tarzda, masalan, sinxronizatsiya signallarini kiritish orqali ta'minlanadi. Biroq, avtomatlashtirishning mavhum nazariyasi darajasida, agar avtomat shunchaki matematik model bo'lsa, uni amalga oshirishning ko'pgina o'ziga xos xususiyatlarini aks ettira olmaydi, ko'pincha sinxron avtomatika bilan ishlash qulayroq bo'ladi.

1.4 Mile va Mura modellari o'rtasidagi aloqa

Yuqorida ta'kidlab o'tilganidek, mavhum avtomat kirish alifbosini chiqish alifbosi so'zlariga o'zgartiruvchi sifatida ishlaydi.

Miles mavhum mashinasi 1.5-rasmda grafik bo'yicha berilgan bo'lsin.

Kirish so'zi X = x1, x1, x2, x1, x2, x2, ushbu avtomatika boshlang'ich holatiga kiritilgan.

1.5-rasm - Graf Miles mashinasi

Xo'sh, qanday qilib? (a1, x1) = a3, a? (a1, x1) = y1, keyin x1 kirish signalining X harfining birinchi harfi ta'siri ostida avtomatika a3 holatiga o'tadi va y1 chiqish signali paydo bo'ladi. Keyingi? (a3, x1) = a1, a? (a3, x1) = y2, shuning uchun x1 ikkinchi signal kelganda, avtomat A1 holatida bo'ladi va y2 signali uning chiqishida paydo bo'ladi. Avtomatikning keyingi xatti-harakatlarini to'g'ridan-to'g'ri o'tish jadvallari va chiqishlari bo'yicha kuzatib, biz uni uchta satrda tasvirlaymiz, birinchisi X kirish so'ziga to'g'ri keladi, ikkinchisi - avtomat X so'zining harflari ta'siri ostida o'tadigan holatlar ketma-ketligi, uchinchisi - chiqishi Y-da. avtomatik mashina:

x1x1 x2 x1 x2 x2

a1a3 a1a1 a3 a2   a3

y1 y2 y1 y1 y1 y2

Qo'ng'iroq qilaylik = ? (a1, X) kirish kirish so'zidagi a1 holatdagi Mile avtomatiga javob berish orqali. Misoldan ko'rinib turibdiki, k uzunlikdagi kirish so'ziga javoban milya mashinasi k + 1 uzunlikdagi holatlar ketma-ketligini va k uzunlikning chiqish so'zlarini hosil qiladi. Umuman olganda, am milga o'rnatilgan Mile avtomatining ishlashini quyidagicha ta'riflash mumkin:

Xuddi shu tarzda, xi1, xi2,., Xik kiritish so'zi kelganida Murning avtomatining am holatdagi holatini tasvirlash mumkin. . Eslatib o'tamiz, (1-2) ga binoan, t (V (t)) vaqtidagi Murning avtomatidagi chiqish signali faqat t (a (t)) vaqtida avtomat joylashgan holatiga bog'liq:

Shubhasiz, chiqish signali ui = l (am) i1 vaqtidagi kirish xi1 kirish signaliga bog'liq emas, faqat am tomonidan belgilanadi.

Shunday qilib, yi1 signali i1 paytidan boshlab avtomat kirishiga kirish so'zlari bilan hech qanday bog'liq emas. Shu munosabat bilan, Murning avtomati reaktsiyasi bilan X = xi1, xi2 kiritish so'zida am holati o'rnatildi. , . ,   xik biz bir xil uzunlikdagi chiqish so'zini tushunamiz y = l (am, x) = ui2, ui3,., yik + 1.

Misol tariqasida, 1-6-rasmda ko'rsatilgan Mur S5 pulemyotini ko'rib chiqing va Mealy S1 pulemyotining xatti-harakatlarini tahlil qilishda biz ishlatgan bir xil kirish so'ziga dastlabki reaktsiyasini toping:

1-6-rasm - Murning mashina grafigi

Ushbu va oldingi misollardan ko'rinib turibdiki, S5 va S1 avtomatizatsiyasining X holatidagi so'zga bo'lgan javobi 1 tsiklning siljishi bilan mos keladi (Murning avtomatining reaktsiyasi bayon qilingan). Endi biz to'liq aniqlangan avtomatika ekvivalentligining qat'iy ta'rifini beramiz.

Bir xil kirish va chiqish alifbosi bo'lgan ikkita avtomatlashtirilgan SA va SB, agar dastlabki holatlarda o'rnatilgandan so'ng, har qanday kirish so'ziga reaktsiyalari bir-biriga to'g'ri kelsa, ekvivalent deb ataladi.

1.5 Ekvivalent avtomatika. Ekvivalent avtomat transformatsiyalar

Har qanday Mealy avtomatida ekvivalent Mur avtomati va aksincha, har qanday avtomat uchun Mealy avtomatining ekvivalenti borligini ko'rsatish mumkin.

Yuqoridagilarga muvofiq, Mili va Mur avtomatotalarining o'zaro transformatsiya algoritmlarini tavsiflashda, Murning avtomatikasida boshlang'ich holati (? (A1)) bilan bog'liq chiqish signalini e'tiborsiz qoldiramiz.

Avvalo Mur avtomatining Mile avtomatiga aylanishini ko'rib chiqamiz.

Murning avtomati berilsin: SA = (XA, AA, UA,? A,? A, aoA), bu erda:

XA = (x1, x2,. Xn); Y = (y1, y2, Um); A = (a0, a1, a2,. AN); a0A = a0 - bu dastlabki holat (a0AA); ! A - xaritani belgilaydigan avtomatika o'tish funktsiyasi (HAAAA) -\u003e AA; ? A - xaritani belgilaydigan avtomatning chiqish funktsiyasi AA-\u003e UA.

Millar mashinasini tuzing: SB = (XB, AB, YB, ?? B ,? B ,   a0B), bunda AB = AA; XB = XA; YB = UA; ? B =? A; a0B = a0A. Chiqishlarning funktsiyasi? B quyidagicha aniqlanadi. Agar Murning avtomatida? A (am, x1) = a va? A (a) = yg bo'lsa, Mealy avtomatida? B (am, x1) = yg

1.7-rasm - Murdan Milga o'tish to'g'risidagi rasm

Murning avtomatidan Mealy avtomatiga o'tishning grafik usuli bilan rasm 1–7 rasmda ko'rsatilgan: yg (yaqin) tepasida joylashgan qayd qilingan chiqish signali bu cho'qqiga kiruvchi barcha yoylarga o'tkaziladi.

Avtomatni aniqlashning jadvalli usulida, Mile avtomatining o'tish jadvali asl Moore avtomatining o'tish jadvali bilan mos keladi va chiqish jadvali x satr va x ustunlar kesishmasidagi belgini belgini SA o'tish jadvalidagi kabi ustunni belgilovchi chiqish belgisi bilan almashtirish orqali olinadi.

Mily SB avtomatizatsiyasini qurish usulidan ko'rinib turibdiki, u Mur SA avtomatiga tengdir. Induksiya yordamida am va amallangan SA va SB avtomatatlarining kirishlariga qo'llaniladigan har qanday cheklangan uzunlikdagi so'zlar bir xil chiqish so'zlarining paydo bo'lishiga olib keladi va shuning uchun SA va SB avtomatlari ekvivalent bo'ladi.

Mile avtomatining avtomatiga aylanishini ko'rib chiqishdan oldin Mura, biz milya avtomatiga quyidagi cheklovlarni qo'yamiz: mashinada vaqtinchalik holat bo'lmasligi kerak. O'tish davri orqali biz avtomat grafik ko'rinishida birorta boshq yoyga kirmaydigan, lekin kamida bitta chiquvchi yoyga ega bo'lgan holatni bildiramiz. Shunday qilib, Miles mashinasi o'rnatilsin:

SA = (XA, AA, YA ,? A,? A, a0A),

qayerda:

XA = (x1, x2,. Xn); Y = (y1, y2,. Ym); A = (a0, a1, a2,. AN); a0A = a0 - bu dastlabki holat (a0AA); ? A - xaritani belgilaydigan avtomatika o'tish funktsiyasi (XAxAA) -\u003e AA; ? A - xaritani (XAxAA) -\u003e YA belgilaydigan avtomatning chiqish funktsiyasi.

Mur avtomatini tuzing: SB = (XB, AB, YB,? B ,? B, a0B), buning uchun XB = XA; YB = YA.

AB ni aniqlash uchun har bir asAA holatini yozish uchun, biz barcha mumkin bo'lgan shakllar juftlarini (as, yg) belgilangan.

Chiqishlarning funktsiyasi? B quyidagicha aniqlanadi. Murning SB-ning har bir holatiga (masalan, yg) bir juftlik, biz yozishmalarga yg chiqish signalini beramiz.

Agar Miles SA avtomatiga o'tish sodir bo'lgan bo'lsa? A (am, xf) = bo'lgani kabi va chiqish signali A (am, xf) = yg ishlab chiqarilgan bo'lsa, u holda SBda am hosil bo'lgan holatlar to'plamidan am holatga o'tish bo'ladi (chunki) yg) xf kirish signali bilan.

A0B boshlang'ich holati sifatida SA avtomatining boshlang'ich holati a0 tomonidan yaratilgan A0 holatidan istalganini olamiz. Bunday holda, t = 0 vaqtidagi chiqish signali hisobga olinmasligi kerak.

Bir misolni ko'rib chiqaylik. Avtomatik Miles mashinasi o'rnatilsin (jadval.10.10).

B0 ni hisobga olgan holda har bir ai / xk juftligiga davlat bikini tayinlaymiz (holatning i-raqami, kirish signalining k-soni).

Quyidagi qoidalarga amal qilib, Mur o'tish jadvalining mashinasini yarating:

1) 1.11-jadvaldan Milly pulemyotining holatini va ularning har biriga mos keladigan Mur pulemyot (bik) holatini yozib chiqamiz:

a0 = (b0, b02, b11, b21); a1 = (b22); a2 = (b01, b12);

2) Agar Murning avtomat bik holati Mili avtomatining holatiga mos keladigan bo'lsa, u holda davlat avtomati uchun Mur avtomatining o'tish jadvalidagi chiziq mil holatiga mos keladigan mil mashinasining o'tish jadvalidagi satrda yozilishi kerak (1.10 dan boshlab).

3) Mur avtomatining chiqishlari funktsiyasi quyidagicha aniqlanadi:? B (bik) =? A (ai, xk). B0 boshlang'ich holati uchun chiqish signalining qiymati o'zboshimchalik bilan tanlanishi mumkin, ammo a0 boshlang'ich holati tomonidan yaratiladi (davlatlar ekvivalenti tushunchasini hisobga olgan holda). 1.10-jadvalda keltirilgan Mur mashinasining Mile mashinasiga ekvivalent bo'lgan natijalari va o'tish jadvallari 1.12-jadvalda keltirilgan.

4) 1.12-jadvalda ekvivalent holatlarni topamiz va ularni o'chirib tashlaymiz (ularni ekvivalentlik sinfining vakili bilan almashtiramiz).

Agar b0 yaqinidagi chiqish signali y1 bilan aniqlansa, u holda bu o'tish jadvalida 3 ta ekvivalent holat mavjud (b0, b11, b02). Ekvivalentlik sinfini bitta vakil bilan almashtirish (b0), biz oxirgi o'tish jadvalini olamiz (1.13-jadval).

1.12-jadval

Mily va Moore avtomatlarini o'zaro almashtirish usullari shuni ko'rsatadiki, Murning avtomatidagi shtatlar soni odatda Mur avtomatidan Mile avtomatiga o'tish paytida ko'payadi.

Shunday qilib, bir-biriga ekvivalent bo'lgan avtomatika turli xil holatlarga ega bo'lishi mumkin, shu sababli bir-biriga teng bo'lgan avtomat sinfida minimal avtomat (eng kam sonli holat) ni topish muammosi paydo bo'ladi. Har qanday mavhum avtomat uchun eng kam miqdordagi ichki holatlarga ega mavhum avtomatika borligini dastlab Mur isbotlagan.

1.6 Mashinaning ichki holatini minimallashtirish

Aufenkampa-Xona algoritmi.

Avtomat holatini minimallashtirish usuli asl, mavhum avtomatning barcha holatlarini ekvivalent holatlarning o'zaro kesishmaydigan sinflariga bo'lish va har bir ekvivalentlik sinfini bitta davlatga almashtirish g'oyasiga asoslanadi (ushbu sinf vakili). Ushbu transformatsiyalar natijasida hosil bo'lgan minimal avtomat shunchalik ko'p holatlarga ega, chunki ekvivalentlik sinflari dastlabki holatlarni ajratib turadi.

Avtomatikning ikki holati am va ular ekvivalent deb ataladi (am = as), agar? (am, X) =? (uzunligi X) barcha mumkin bo'lgan kiritish so'zlari uchun X uzunligi.

Agar va ular teng bo'lmasa, ular ajralib turadi. Kuchsiz ekvivalentlik K-ekvivalenti. Am va a holatlar K ga tengmi, agar? (am, xk) =? (uzunligi, Xk) mumkin bo'lgan barcha kiritish so'zlari uchun K uzunligi S = (X, Y, A,?) avtomatining ichki holatini minimallashtirish orqali. , ?, a0) Aufenkamp-Hon algoritmi ishlatiladi:

1. ketma-ket bo'ladigan qismlarni toping? 1,? 2, ...,? K,? K + 1, A, bitta, ikkita sinflarga bo'linadi -,., K-, (K + 1) - ekvivalent holatlar bo'lguncha. ba'zi bir (K + 1) bosqichda bu ko'rinmaydi? k =? k + 1. Bunday holda, K-ekvivalent holatlar ekvivalentdir. K bosqichlari soni? K =? K + 1 N-1 dan oshmaydi, bu erda N - avtomatning ichki holatlari soni.

2. Har bir ekvivalentlik sinfida? "Minimal avtomat S" holatlarining A to'plamini tashkil etadigan bitta elementni (sinf vakili) tanlang.

3. O'tish funktsiyasi? "Va natijalarmi?" avtomat S "A" xX to'plamida aniqlanadi.

Buning uchun o'tish jadvali va chiqishlarida "A" to'plamga kirmagan holatlarga mos keladigan ustunlarni o'chirib tashlang, o'tish jadvalining qolgan ustunlarida esa barcha "A" to'plamdagi (vakillar) ekvivalentlari bilan almashtiriladi.

4. "0" sifatida a0 holatiga teng bo'lgan holatlardan biri tanlangan. Xususan, a0 holatini o'zi qabul qilish qulay.

Mur avtomatizatsiyasini minimallashtirishda 0-ekvivalentlik va davlatlar to'plamini 0-sinflarga bo'lish tushunchasi kiritiladi: chiqish signallari bilan teng ravishda belgilangan Murning avtomatizatsiyasining har qanday holati 0-ekvivalent deb ataladi. Misol sifatida, o'tish va chiqishlar jadvali tomonidan berilgan Moore avtomatining minimallashtirilishini ko'rib chiqing (1.14-jadval).

1.14-jadval

Ajratish kerakmi? 0:

? 0 = (B1, B2, B3);

B1 = (a1, a2, a8), B2 = (a6, a9, a10, a11, a12), B3 = (a3, a4, a5, a7).

Bo'lim jadvalini tuzing? 0:

Ajratish kerakmi? 1:

1 = (C1, C2, C3, C4);

C1 = (a1, a2, a8), C2 = (a6, a9, a11), C3 = (a10, a12), C4 = (a3, a4, a5, a7).

Bo'lim jadvalini tuzing? 1:

Ajratishni bajaring? 2 .

1 = (D1, D2, D3, D4);

D1 = (a1, a2, a8), D2 = (a6, a9, a11), D3 = (a10, a12), D4 = (a3, a4, a5, a7).

Ajratish? 2 bo'linishni takrorlaydi? 1 - bo'linish jarayoni yakunlandi.

D1, D2, D3, D4 har bir ekvivalentlik klassidan bitta vakilni tanlang - bu holda minimal son: A "= (a1, a3, a6) ,   a10).

Dastlabki o'tish jadvalidan "qo'shimcha" holatlarni olib tashlab, biz eng kam Mur avtomatini aniqlaymiz (1.15-jadval).

1.15-jadval.

Xulosa

Sinovni amalga oshirish jarayonida biz mavhum raqamli avtomatlashtirishning asosiy tushunchalari bilan tanishdik; mavhum mashinalarning turlari; mavhum avtomatlashtirishni sozlash usullari; Mile va Moore modellari o'rtasidagi aloqa; ekvivalent avtomatika va avtomatika ekvivalent transformatsiyalari; Avtomat va Aufenkamp-Xon algoritmining ichki holatini minimallashtirish orqali misollar keltirdi.

Adabiyotlar ro'yxati

Samofalov KG, Romankevich AM va boshqalar Raqamli avtomatlashtirishning amaliy nazariyasi. - Kiev. "Oliy maktab" 1987 yil.

2. Solovyov G.N. Kompyuter arifmetik asboblari. - M. "Energiya". 1978 yil

3. Saveliev A.Ya. Raqamli avtomatlashtirishning amaliy nazariyasi - M. "Oliy maktab". 1987 yil

4. Kogon B.M. Elektron kompyuterlar va tizimlar. - M. Energoatomizdat. 1985 yil.

5. Lisikov B.G. Raqamli avtomatlashtirishning arifmetik va mantiqiy asoslari. - Minsk. "Oliy maktab". 1980 yil

Chiqishda, u boshqa alifboning belgilarini (umuman) ishlab chiqaradi.

Mavhum mashina

Rasmiy ravishda mavhum avtomat beshta deb belgilangan

Mavhum avtomat parametrlari sonining chegaralanishi cheklangan avtomat degan tushunchani aniqladi.

Avtomatning ishlashi ikkita ketma-ketlikni hosil qilishdan iborat: avtomatizatorning ketma-ket holatlari ketma-ketligi va chiqish belgilarining ketma-ketligi, ular t = 1, 2, 3, diskret vaqtli barqarorliklarda paydo bo'ladigan belgilar ketma-ketligi ... Diskret vaqtli doimiyliklar soat sikllari deb ataladi.

Vaqtning diskret o'zgarishlari vaqtida avtomatning ishlashini takroriy munosabatlar tizimi bilan tavsiflash mumkin:

Mavhum avtomatlashtirish xususiyatlarini tushuntirish uchun tasniflash kiritiladi.

Mavhum avtomatika diskret modellarning asosiy sinfini mustaqil model sifatida shakllantiradi va Turing mashinalari, do'kon tipidagi avtomatlar, cheklangan avtomatlar va boshqa ma'lumot konvertorlarining asosiy tarkibiy qismi sifatida shakllanadi.


Vikimedia Jamg'armasi. 2010 yil

  • Davlat diagrammasi (avtomatika nazariyasi)
  • Tog`li Qorabog`

Mavjud mashina boshqa lug'atlarda nima ekanligini ko'rib chiqing:

    mavhum mashina  - T-srit avtomatika atitikmenis holatida: angl. mavhum avtomat vok. abstraktsiya Avtomatik, m rus. mavhum avtomat, m pranc. avtomatlashtirish abstrait, m ... Automatikos terminų žodynas

    Avtomatik  - Vikilug'atda "avtomatik" degan maqola bor Automaton: Automaton bu mustaqil ravishda ba'zi harakatlarni bajaradigan qurilma ... Vikipediya

    Davlat mashinasi  - Davlat mashinasi - bu chiqish oqimi bo'lmagan mavhum avtomat, albatta mumkin bo'lgan holatlar soni. Mashinaning natijasi uning yakuniy holati bilan belgilanadi. Davlat mashinasini sozlash uchun turli xil variantlar mavjud. Masalan, ... ... Vikipediya

    TURING MASHINASI  - 1930 yillarda ingliz matematiki Alan M. Turing tomonidan nazariy jihatdan tavsiflangan mavhum avtomat (ya'ni kompyuter yoki boshqa aniq, aniq bir mexanizm). Aslida, Turing mashinasi lenta va o'qish boshidan iborat. Lenta ... ... Psixologiya lug'ati

    Avtomatik nazariya

    Avtomatik nazariya  - diskret tsikl yordamida diskret ma'lumotlarni qayta ishlaydigan haqiqiy yoki mumkin bo'lgan qurilmalarning matematik modellarini (bu erda avtomatik mashinalar yoki mashinalar deb yuritiladi) o'rganadigan nazariy kibernetika bo'limi. Asosiy ... ... Iqtisodiyot va matematik lug'at

    avtomatika nazariyasi  - diskret soat sikllaridan foydalanib diskret ma'lumotlarni qayta ishlaydigan haqiqiy yoki mumkin bo'lgan qurilmalarning matematik modellarini (bu erda avtomatik mashinalar yoki mashinalar deb yuritiladi) o'rganadigan nazariy kibernetika bo'limi. Ushbu nazariyaning asosiy tushunchalari ... ... Texnik tarjimon qo'llanmasi

    Avtomatik nazariya  - Avtomatika nazariyasi - mavhum kompyuterlar va kompyuter mashinalarini o'rganadigan, matematik modellar ko'rinishida taqdim etiladigan va ular hal qila oladigan muammolarni yorituvchi diskret matematikaning bo'limi. Avtomatika nazariyasi eng ... Vikipediya bilan chambarchas bog'liq

    Kompyuter  - Shaxsiy kompyuterning sxemasi: 1. Monitor 2. Anakart 3 ... Vikipediya

    Rasmiy usullar - Z notation yordamida rasmiy spetsifikatsiyaga misol. Informatika va dasturiy muhandislikda ... uchun Vikipediya matematik apparatga asoslangan metodlar guruhi.

Chiqish funktsiyalarini shakllantirish usuliga ko'ra, uchta mavhum avtomat ajralib turadi: milya avtomati, Mur avtomati, C avtomati. Mili avtomati quyidagi tenglamalar tizimi bilan tavsiflanadi:

y (t) = (a (t), x (t));

a (t + 1) = δ (a (t), x (t)). (1-1)

Mur avtomati - tenglamalar tizimi:

a (t + 1) = δ (a (t), x (t)). (1-2)

S-avtomat - tenglamalar tizimi:

y 1 (t) = (a (t), x (t));

2 (t) = 2 (a (t));

a (t + 1) = δ (a (t), x (t)).

O'zboshimchalik bilan mavhum mashina Miles yoki Mura (1.1-rasm) bitta kirish va bitta chiqish kanaliga ega. O'zboshimchalik bilan mavhum C-avtomat bitta kirish va ikkita chiqish kanaliga ega (1.2-rasm).

Shakl 1.1 - mavhum mashina

Rasm.1.2 Mavhum C-avtomat

Agar mavhum Mile yoki Moore avtomatining kirishlari a boshlang'ich holatiga o'rnatilgan bo'lsa, harflar bilan harflar ketma-ketligini x (0), x (1),. - kirish so'zi, so'ngra mashinaning chiqishida chiqish alfavitining harflari y (0), y (1), paydo bo'ladi. - chiqish so'zi. C-avtomat uchun uning chiqishlarida ikkita ketma-ketlik paydo bo'ladi: y 1 (0), y 1 (1),. va y 2 (0), y 2 (1),. Xulosa C - avtomatda, y 2 (t) = (a (t)) chiqish signali avtomatik ravishda a (t) holatida bo'ladi. Chiqish signali y 1 (t) = λ 1 (a (t), x (t)) C-avtomat a (t) holatida bo'lganida x (t) kirish signali davomida beriladi.

Shunday qilib, mavhum nazariya darajasida raqamli avtomatning ishlashi kirish so'zlarini chiqish so'zlariga aylantirish deb tushuniladi.

To'liq aniqlangan va qisman avtomatika ajralib turadi.

To'liq aniqlangan mavhum raqamli avtomat bo'lib, uning o'tish funktsiyasi yoki chiqish funktsiyasi yoki ikkalasi ham barcha o'tish juftlari uchun aniqlanadi (x i, a j).

Qisman - bu o'tish funktsiyasi yoki chiqish funktsiyasi yoki ikkalasi ham barcha o'tish juftlari uchun aniqlanmagan mavhum raqamli avtomatdir (x i, a j).

Agar a o holati A holatlari to'plamida ajralib tursa, mavhum raqamli avtomat boshlang'ich deyiladi.

1.3 Mavhum avtomatlashtirishni sozlash yo'llari

S davlat mashinasini aniqlash uchun to'plamning barcha elementlarini tavsiflash kerak: S = (X, A, Y ,, a o). Mashinaning ishlashini belgilashning bir necha usullari mavjud, ammo eng ko'p ishlatiladigan - jadvalli (matritsa), grafik, analitik.

Jadval usulida avtomat ikkita jadval bilan belgilanadi: o'tish jadvali va chiqish jadvali yoki aralashmalarning matritsasi. O'zboshimchalik bilan to'liq aniqlangan avtomatika o'tish jadvali quyidagicha tuziladi: jadvalning satrlari avtomatning kirish alifbosi harflari bilan, jadvalning ustunlari - avtomat holati alfavitining harflari bilan belgilanadi; O'tish jadvalining katakchasida joylashgan kirish signali x i va j holatida belgilangan ustun bilan belgilangan chiziqning kesishishi a k ​​= holatiga keltiriladi, bu k = (a j, x j) ifodasi bilan aniqlanadigan kirish signalining ta'siri ostida i j holatidan avtomatning j holatiga o'tishidir.

1.1-jadval. O'tish jadvali mashinasi

Shtatlar

kirish signallari

   (a k, x j)

1.2. Jadvalda ba'zi bir mavhum to'liq aniqlangan avtomatlashtirilgan o'tish alifbosi bilan X = (x 1, x 2) - va alfavit A = (a, a 2, va 3) o'tish jadvalini to'ldirishga misol keltirilgan.

1.2-jadval

Agar mavhum avtomat qisman bo'lsa, u holda uning o'tish jadvali katakchasida, kirish signali va tegishli holat bilan belgilangan chiziqning kesishgan qismida (ushbu kirish signalining ta'siri ostida ushbu holatga o'tish aniqlanmagan bo'lsa), chiziqcha qo'yiladi va har qanday kirish so'zi mavjud. ko'rsatilgan o'tishga olib kelishi taqiqlanadi.

Qolgan hujayralarni to'ldirish to'liq aniqlangan avtomat holatiga o'xshaydi. O'tish jadvalining ko'rinishi ko'rsatilgan avtomat (Mili, Mura, C-avtomat) turiga bog'liq emas. Mile, Moore, C-automaton avtomatlarining chiqish jadvallarida farqlar mavjud.

To'liq aniqlangan Miles mashinasining chiqish jadvali quyidagicha tuzilgan: ustunlar va satrlarni identifikatsiyalash, shuningdek jadvalning formati to'liq aniqlangan mashinaning o'tish jadvaliga mos keladi. Kirish signali X j bilan belgilangan va k holati bilan belgilangan ustunning kesishmasida joylashgan chiqish jadvalining katakchasida Y m chiqish signali qo'yiladi, u mashina ishlab chiqaradigan k k holatida, kirish signali Xj bilan belgilanadi, bu Ym = ifodasi bilan aniqlanadi. (a k, x j)

1.3-jadval mavhum Miles avtomatining chiqish jadvali.

Shtatlar

Kirish signallari

Ba'zi bir mavhum to'liq aniqlangan avtomatning chiqish jadvalini kirish alifbosi X = (x 1, x 2), davlat alifbosi A = (a 1, a 2, a 3) va chiqish alifbosi Y = (y 1, y 2, y 3) to'ldirish misoli 1-jadvalda keltirilgan.

1.4-jadval

Shubhasiz, to'liq aniqlangan C-avtomat ikkita chiqish jadvallari tomonidan berilgan, ularning birinchisi Mile mashinasining chiqish jadvali, ikkinchisi - Mura. Agar avtomat qisman bo'lsa, unda uning jadvalining ba'zi hujayralarida tire bo'lishi mumkin, bu chiqish signalini anglatmaydi.

Amalda, o'tish va chiqish jadvallari ko'pincha bitta jadvalga birlashtirilib, belgilangan avtomat o'tish jadvali deb nomlanadi. Belgilangan o'tish jadvallariga misollar 1.6-jadvalda keltirilgan. - 1.8 (Belgilangan o'tish stolining umumiy ko'rinishi - 1.6-jadval., Mili pulemyotining belgilangan o'tish jadvali - 1.7-jadval., Mur avtomatining belgilangan o'tish jadvali - 1-jadval. 1.8.).

Yuqorida muhokama qilingan o'tish va chiqish jadvallariga qo'shimcha ravishda ixtiyoriy mavhum avtomat birikmalar matritsasi bilan berilishi mumkin.

Murakkablarning matritsasi to'rtburchaklardir va ko'p sonli ustunlarni (qatorlarni) o'z ichiga oladi, chunki har xil shtatlar ushbu avtomat holatlarining alfavitini o'z ichiga oladi. Murakkab matritsaning har bir ustunida (qatorida) mashinaning holati ko'rsatilgan. J harfi va s harfi bilan belgilangan ustunning kesishmasida joylashgan kamerada avtomat s s harfi bilan belgilangan chiziqda, kirish ta'siri (yoki kirish signallarining uzilishi) ta'sirida, bu o'tish sodir bo'ladi.

Miles mavhum avtomati uchun chiqish signali ushbu o'tish natijasida avtomat vujudga keltiradigan holatning yonidagi kameraga joylashtiriladi (1.9-jadval.) Murning avtomati uchun chiqish signali shtatning yonidagi qatorga qo'yiladi (bu holatlar avtomatning dastlabki holatlariga to'g'ri keladi).

1.6-jadval

Shtatlar

Kirish signallari

 (a 2, x j)

 (a k, x j)

 (a 2, x j)

 (a k, x j)

1.7-jadval

1.9-jadval.

Mavhum avtomatlashtirishni grafik usulida yo'naltirilgan grafikalar keltirilgan. Avtomat grafigi yo'naltirilgan bog'langan grafik bo'lib, uning uchlari avtomat holatiga to'g'ri keladi va ularning orasidagi yoylar davlatlar orasidagi o'tishni anglatadi. Agar k va s s ikkita vertikallar, agar mashina a k holatidan s s holatiga o'tish holatida bo'lsa, boshq bilan bog'lanadi. Miles avtomati uchun kirish va chiqish signallari ushbu o'tish mos keladigan yoyga qo'yiladi (1.3-rasm), Moore mashinasi uchun kirish signali yoyga qo'yiladi va chiqish signali holatga mos keladigan cho'qqiga yaqinlashadi (1.4-rasm).

Bu erda biz faqat o'tish rejimining o'ziga xos shartiga ega bo'lgan deterministik avtomatiyani ko'rib chiqamiz: ma'lum bir holatda bo'lgan avtomat biron bir kirish signalining ta'siri ostida bir nechta holatga aylantirilishi mumkin emas. Avtomatni aniqlashning grafik usuliga murojaat qilsak, bu avtomat grafasida bir xil kirish signali bilan belgilangan ikki yoki undan ortiq yoylar har qanday tepadan chiqa olmaydi degan ma'noni anglatadi.

1.3-rasm - Milning avtograf grafigi 1.4-rasm - Murning avtograf grafigi

Mavhum avtomatlashtirishni analitik usulida to'rtta ob'ekt berilgan:

S = (X, A, Y, F), bu erda F har bir holat uchun j xaritadagi avtomatlashtirish j-ni belgilaydi (XXA) - >   (AxY). Boshqacha qilib aytganda, j j avtomatining har bir holatini sozlashning analitik usulida p, x m, y k ning barcha uchliklari yig'indisi bo'lgan F ai xaritasi ko'rsatilgan va shu bilan kirish signalining ta'siri ostida m m avtomatikadan chiqib ketadi. a j   ichida  p k holati, chiqish signalini berganda y k.

Mavhum avtomatiyaning umumiy ta'rifiga kelsak, ikkinchisi δ va functions funktsiyalarining ifodasiga muvofiq tavsifiga tengdir: a p = δ (a i, x m), y k = λ (a i, x m).

F ai xaritasi quyidagicha yozilgan:

F ai (a p (X m / y k), a i (X f / y z) ...).

Miles mavhum avtomati uchun (1.7-jadval), analitik vazifa quyidagi shaklga ega:

S = (X, A, Y, F), X = (x 1, x 2), A = (a 1, a 2, a 3), Y = (y 1, y 2, y 3),

F a1 = (a 2 (x 1 / y 2), a 1 (x 2 / y 3)),

F a 2 = (a 3 (x 1 / y 3), a 1 (x 2 / y 1)),

F a 3 = (a 1 (x 1 / y 3) va 2 (x 2 / y 2)).

Shuni ta'kidlash kerakki, F ai funktsiyasi har doim boshlang'ich holat uchun qayd etiladi.

Sinxron va asenkron avtomatika aniqlaymiz. Agar s = δ (a i X m) s = δ (a s, x m) bo'lsa, s j avtomatining s holati barqaror holat deyiladi.

Agar avtomat S, agar uning A holati barqaror bo'lsa, asinxron deyiladi. Agar avtomat S sinxron bo'lmasa, sinxron deb ataladi.

Ta'kidlash joizki, amalda yaratilgan avtomatika doimo asenkron bo'lib, ularning holati barqarorligi har doim qandaydir tarzda, masalan, sinxronizatsiya signallarini kiritish orqali ta'minlanadi. Biroq, avtomatlashtirishning mavhum nazariyasi darajasida, agar avtomat shunchaki matematik model bo'lsa, uni amalga oshirishning ko'pgina o'ziga xos xususiyatlarini aks ettirmasa, sinxron avtomatika bilan ishlash ko'pincha qulayroqdir.