Abstrakt avtomat. Umumiy avtomatlar nazariyasi mavhum va strukturaga bo'linadi
Raqamli (diskret) avtomatni qandaydir algoritm bo'yicha diskret ma'lumotlarni qabul qiluvchi, saqlaydigan va o'zgartiruvchi qurilma sifatida talqin qilish mumkin. Muayyan nuqtai nazardan, ham real qurilmalar (kompyuterlar, tirik organizmlar va boshqalar), ham mavhum tizimlar (matematik mashinalar, aksiomatik nazariyalar)
Avtomatlarning umumiy nazariyasi mavhum va strukturaga bo'linadi. Ularning orasidagi farq shundan iboratki, mavhum nazariya avtomatning tuzilishidan mavhumlashtirilgan (ya'ni, uni qurish usuli bilan qiziqmaydi) faqat avtomatning tashqi muhitga nisbatan xatti-harakatlarini o'rganadi. Avtomatlarning mavhum nazariyasi shuning uchun algoritmlar nazariyasiga yaqin bo'lib, mohiyatan uning keyingi tafsiloti hisoblanadi. Mavhum nazariyadan farqli o'laroq, strukturaviy nazariyani avtomatning o'zi ham, kirish harakatlarining tuzilishi va avtomatning ularga bo'lgan javoblari qiziqtiradi. Strukturaviy nazariyada avtomatlarni qurish usullari, avtomatning kirish harakatlari va reaktsiyalarini kodlash usullari o'rganiladi. Shunday qilib, avtomatlarning strukturaviy nazariyasi davomi va yanada rivojlantirish mavhum nazariya. Mantiqiy funksiyalar apparati va avtomatlarning mavhum nazariyasiga asoslanib, strukturaviy nazariya haqiqiy hisoblash qurilmalarini ishlab chiqish uchun samarali tavsiyalar beradi.
Mavhum raqamli avtomat A besh ob'ekt to'plami bilan aniqlanadi, bu erda A avtomatining kirish signallari to'plami (A avtomatining kirish alifbosi); - avtomatning A holatlar to'plami (avtomatning holatlar alifbosi - A avtomatining chiqish signallari to'plami (A avtomatining chiqish alifbosi); - o'tish funktsiyasi
xaritalashni belgilaydigan, ya'ni to'plamlarning dekart mahsulotining har qanday juft elementlariga to'plam elementini tayinlaydigan A avtomatining - A avtomatining chiqishlari funktsiyasi, bu xaritalash yoki xaritalashni belgilaydi.
Boshqacha qilib aytganda, o'tish funktsiyasi shuni ko'rsatadiki, A avtomati kirish signali paydo bo'lganda ma'lum bir holatda bo'lib, ma'lum bir holatga o'tadi.. chiqish signalini beradi Ikkinchisini ifoda bilan yozish mumkin.
Chiqish funktsiyasini yaratish usuliga ko'ra, mavhum avtomatlarning uch turi ajralib turadi: Mealy avtomati, Mur avtomati va C-avtomat. Mavhum Miles avtomatida X chiqish funktsiyasi xaritalashni belgilaydi. Abstrakt Mur avtomatida chiqish funksiyasi mavhum C-avtomatiga xaritalashni belgilaydi, ikkita chiqish funksiyasi X kiritiladi va mos ravishda xaritalashni belgilaydi. Bunday holda, C-avtomatining chiqishlari alifbosi yoki
Ixtiyoriy mavhum avtomat Milan yoki Mur bitta kirish va bitta chiqish kanaliga ega (10.1-rasm). O'zboshimchalik bilan mavhum C-avtomat bitta kirish va ikkita chiqish kanaliga ega (10.2-rasm).
To'liq aniqlangan va qisman avtomatlar ajralib turadi.
Mavhum raqamli avtomat to'liq aniqlangan deb ataladi, unda barcha juftliklar uchun o'tish funktsiyasi va chiqish funktsiyasi aniqlanadi.
Mavhum raqamli avtomat, agar u o'tish funktsiyasi yoki chiqish funktsiyasiga ega bo'lsa yoki bu funktsiyalarning ikkalasi ham barcha juftliklar uchun aniqlanmagan bo'lsa, qisman deyiladi.
Mavhum raqamli avtomat boshlang'ich deb ataladi, agar uning 5 holatlari to'plamida maxsus boshlang'ich holat ajratilgan bo'lsa, ya'ni boshlang'ich mavhum avtomat oltita ob'ekt to'plami bilan aniqlansa. tez-tez yuzaga keladigan avtomat ishini boshlash shartlarini tuzatish zarurati bilan bog'liq.
Aytishlaricha, mavhum avtomat diskret avtomat vaqtida ishlaydi va holatdan holatga o'tish bir zumda amalga oshiriladi. Diskret vaqtning har bir lahzasida avtomat holatlar to'plamidan ma'lum bir holatda bo'ladi.Agar avtomat boshlang'ich bo'lsa, u holda vaqtning boshlang'ich momentida u doimo boshlang'ich holatda bo'ladi. Hozirgi holatda avtomat X chiqish funktsiyasiga muvofiq kirish alifbosining harfini kiritishda idrok eta oladi, u bir vaqtning o'zida chiqish alifbosining harfini chiqaradi va shunga muvofiq. o'tish funktsiyasi, u keyingisiga o'tadi
holat Mavhum avtomatning ta'rifiga ko'ra, Mealy avtomati bu holda tenglamalar tizimi bilan tavsiflanadi:
Mur avtomati - tenglamalar tizimi bo'yicha;
va C-avtomat tenglamalar tizimidir:
Boshqacha qilib aytadigan bo'lsak, agar kirish so'zi Mealy yoki Mur avtomatining boshlang'ich konspektining kirishiga harfma-harf berilsa, dastlabki holatga o'rnatiladi, kirish alifbosi harflarining ma'lum bir ketma-ketligi, chiqishda ketma-ket chiqish so'zi paydo bo'ladi. avtomatdan. C-avtomatining ishi uchun, uning chiqishlarida ikkita tekshiruv paydo bo'ladi: mavhum C-avtomat uchun, lntomit holatda bo'lganda, chiqish signaliga barcha bonuslar beriladi.
Shunday qilib, mavhum nazariya darajasida raqamli avtomatning ishlashi kirish so'zlarini chiqish so'zlariga aylantirish sifatida tushuniladi.
Mavhum avtomatni ta'riflashda holat tushunchasi haqiqatda qurilgan raqamli avtomatlar tomonidan boshqariladigan real jarayonlarning aksariyati ularning to'g'ri oqimi uchun o'z vaqtida jarayonning rivojlanish tarixini bilishni talab qilishi sababli kiritilgan. Boshqacha qilib aytganda, mashina tomonidan chiqarilgan chiqish signali bu daqiqa vaqt, nafaqat avtomatga kirish harakati bilan, balki avtomatning o'sha paytdagi holati bilan ham belgilanadi. Mashinaning to'g'ri ishlashini tashkil qilish vaqti, kirish signalidan tashqari "svetoforni o'zgartirish" ", svetoforning oldingi lahzadagi holati haqida ma'lumotga ega bo'lish kerak. Bu ma'lumot mavhum avtomatning turli holatlari mavjudligi bilan ta'minlanadi. Mavhum avtomatning kiritilgan ta'rifiga mos keladigan mavhum raqamli avtomatlar xotiraga ega mavhum avtomatlar deb ham ataladi, chunki avtomatda uning turli xil holatlarining mavjudligi faqat avtomat xotiraga ega bo'lgan taqdirdagina mumkin.
Haqiqiy avtomatlar tomonidan boshqariladigan bir qator jarayonlar, ularning to'g'ri oqimi uchun o'z vaqtida jarayonning rivojlanish tarixini bilishni talab qilmaydi. Bunday jarayonlarni boshqaradigan mashinalarda,
10.1-jadval
chiqish signali faqat mashinadagi kirish harakati bilan aniqlanadi. Mavhum taqdimot darajasidagi yuqoridagi avtomatlar triplet yordamida aniqlanadi, bu erda chiqish funktsiyasi xaritalashni belgilaydi va ahamiyatsiz xotiraga ega mavhum avtomatlar yoki kombinatsiyalangan avtomatlar deb ataladi. Kombinatsiyalangan mashinaning eng oddiy analogini oddiy elektr chiroqni o'qish mumkin, agar kirish harakati "On" tugmasini bosgan bo'lsa va chiqish signali chiroq lampochkasining yonishi bo'lsa.
Avtomatlarning kirishlari, holatlari va chiqishlari alifbolari oddiy to'plamlar sifatida, masalan, ularning elementlarini sanab o'tish orqali belgilanadi. O'tish va chiqish funktsiyalari matritsani grafik va analitik tarzda aniqlash mumkin. Shuning uchun har qanday mavhum avtomatni uchta usulda ko'rsatish mumkin! matritsa, grafik va analitik
Matritsa usulida avtomat ikkita jadval bilan ifodalanadi: o'tish jadvali va chiqish jadvali yoki avtomat chiqishlarining ulanish matritsasi funktsiyasi.
Ixtiyoriy to'liq aniqlangan mavhum avtomatning sakrash jadvali quyidagicha tuzilgan. Jadval ustunlari avtomatning kirish alifbosi harflari bilan, jadval qatorlari esa avtomat holatlari alifbosi harflari bilan belgilanadi. Kirish signali bilan belgilangan ustun va holat bilan belgilangan chiziqning kesishmasida joylashgan o'tish jadvalining katakchasida avtomatning ta'siri ostidagi holatdan o'tishi natijasi bo'lgan holat qo'yiladi. ifoda yorlig'i bilan belgilanadigan kirish signali. 10.1. Agar mavhum avtomat qisman bo'lsa, u holda kirish signali bilan belgilangan ustun va davlat tomonidan belgilangan chiziq kesishmasida joylashgan uning o'tishlari jadvalining katakchasida (agar kirish ta'siri ostida holatdan o'tish bo'lsa). signal aniqlanmagan), chiziqcha qo'yiladi va belgilangan o'tishga olib keladigan har qanday kirish so'zi taqiqlanadi. Hujayralarning qolgan qismini to'ldirish to'liq aniqlangan avtomat bilan bir xil. Ba'zi mavhum qisman avtomatlarning kirish alifbosi va holatlar alifbosi bilan o'tish jadvaliga misol jadvalda keltirilgan. 10.2. O'tish jadvalining ko'rinishi tayinlangan avtomatning turiga bog'liq emas (Mur avtomati, Miles, S-avtomat). Mur, Miles va S-avtomat chiqishlarining jadvallari farqlarga ega. To'liq aniqlangan Miles mashinasining natijalari jadvali quyidagicha tuzilgan. Ustunlar va satrlarning identifikatsiyasi, shuningdek, jadval formati to'liq aniqlangan avtomatning o'tish jadvaliga mos keladi. Natijalar jadvalining katagida,
10.2-jadval
10.3-jadval
10.4-jadval
kirish signali bilan belgilangan ustun va holat bilan belgilangan chiziq kesishmasida joylashgan, chiqish signali o'rnatiladi, Mealy avtomati uni chiqaradi, kirish signali mavjud bo'lgan holatda bo'lib, ifoda bilan aniqlanadi. tab. 10.3.
To'liq aniqlangan Mur avtomatining chiqishlar jadvali oddiyroq tuzilgan: avtomatning har bir holatiga o'z chiqish signali beriladi. Holatlar alifbosi va chiqish alifbosi bilan Mur avtomatining chiqishlari jadvaliga misol 10.4-jadvalda keltirilgan.
Shubhasiz, mavhum to'liq aniqlangan C-avtomat ikkita natijalar jadvali bilan berilgan, ulardan birinchisi Mealy avtomatining chiqish jadvali, ikkinchisi - Mur avtomatining chiqish jadvali.
Agar Miles avtomati qisman bo'lsa, uning chiqish jadvalining ba'zi kataklarida chiziqcha bo'lishi mumkin, ya'ni chiqish signali yo'q. Bunday holda, Miles avtomatining o'tish jadvalidagi tire bilan bir xil katakchalarga mos keladigan chiqish jadvalining kataklariga chiziq qo'yilishi kerak. Ikkinchisi, agar Mealy qisman avtomatida juftlik mavjud bo'lsa va kirish signali ta'sirida holatdan o'tish noaniq bo'lsa, tabiiyki, bunday () da chiqish signalining qiymati. mavjud bo'lmagan) o'tish ham aniqlanmagan. Chiqish alifbosi bilan o'tish jadvali (10.2-jadval) tomonidan berilgan qisman Mealy avtomatining natijalari jadvaliga misol Jadvalda keltirilgan. 10.5
Mur qisman avtomatining chiqish jadvalining ba'zi katakchalaridagi chiziqlar uning o'tish jadvalining katakchalaridagi tire bilan bog'liq emas. Bu Mur avtomatining chiqish signali faqat avtomat joylashgan holatga bog'liqligi bilan aniqlanadi. Masalan, o'tish jadvali bilan berilgan qisman Mur avtomatining chiqish jadvali (10.2-jadval),
10.5-jadval
10.6-jadval.
10.7-jadval
jadval sifatida taqdim etilishi mumkin. 10.4, agar uning har bir holatida avtomat qandaydir chiqish signalini chiqaradi va Jadval kabi. 10.6, agar ba'zi holatlar uchun mashinaning chiqish signalining qiymati aniqlanmagan bo'lsa.
Amalda, mashina o'tish va chiqish jadvallari ko'pincha belgilangan mashina o'tish jadvali deb ataladigan bitta jadvalga birlashtiriladi. O'tish jadvali (10.1-jadval) va natijalar jadvali (10.3-jadval) bilan ifodalangan to'liq aniqlangan Mealy avtomatining o'tishlarining belgilangan jadvali Jadvalda jamlangan. 10.7. Qisman Mur avtomatining o'tishlarining qayd etilgan jadvali (10.2-jadval) va natijalar jadvali (10.4-jadval) Jadvalda jamlangan. 10.8.
Yuqorida muhokama qilingan o'tish va chiqish jadvallariga qo'shimcha ravishda, ixtiyoriy mavhum avtomatni ulanishlar matritsasi bilan tasvirlash mumkin. Bunday tavsif matritsadagi mavhum avtomatlarni aniqlash usullaridan biridir. Ixtiyoriy mavhum avtomatning ulanishlar matritsasi kvadrat bo'lib, ko'rib chiqilayotgan avtomatning turli holatlari soni qancha ustun bo'lsa, shuncha ko'p ustunlarni (qatorlarni) o'z ichiga oladi. Ulanishlar matritsasining har bir ustuni (qatori) mashina holatining harfi bilan belgilanadi. Agar avtomat boshlang'ich bo'lsa, u holda chapdagi birinchi ustun va uning ulanishlari matritsasining yuqori qismidagi birinchi qator avtomatning boshlang'ich holatining harfi bilan belgilanadi. , uning ta'siri ostida avtomatning o'tishi holatdan holatga amalga oshiriladi.Agar mavhum Milne avtomati ulanish matritsasi bilan ko'rsatilgan bo'lsa, u holda chiqish signalining harfi kirish signali harfi yonidagi qavs ichida ko'rsatiladi, Mealy avtomati chiqaradi, o'tish Matritsasini qiladi. Belgilangan o'tish jadvali bilan ifodalangan ba'zi Mealy avtomatlarining ulanishlari (10.7-jadval) 10.7-rasmda ko'rsatilgan. 10.3.
Agar mavhum Mur avtomati ulanish matritsasi tomonidan ko'rsatilgan bo'lsa, u holda chiqish signallari ulanish matritsasining qatorlarini aniqlaydigan avtomatning holatini belgilaydi.
10.8-jadval
O'rnatishning grafik usulida mavhum avtomatlar yo'naltirilgan grafiklar bilan ifodalanadi; avtomatning holatlari grafikning cho'qqilari bilan, holatlar orasidagi o'tishlar esa mos keladigan cho'qqilar orasidagi yoylar bilan tasvirlangan. Bunday holda, grafikning har bir yoyi uchun avtomatning kirish alifbosining ma'lum bir harfi belgilanadi, bu avtomatning bu o'tishini faqat kirish signali paydo bo'lganda va grafikning har bir cho'qqisining harfi bo'lganda amalga oshirilishini ko'rsatadi. avtomatning tegishli holati. Agar grafik Mila avtomatini ko'rsatsa, u holda avtomatning chiqish signallari kirish signali harfi yonidagi grafik yoylariga (avtomat chiqishlari jadvaliga muvofiq) qo'yiladi. O'tish jadvali (10.1-jadval) va chiqish jadvali (10.3-jadval) tomonidan berilgan Mealy avtomati grafigiga misol rasmda ko'rsatilgan. 10.4. Agar Mur avtomati grafik bilan tasvirlangan bo'lsa, u holda avtomatning chiqish signallari grafik uchlari yaqinida joylashtiriladi (avtomatning chiqish jadvaliga muvofiq). O'tish jadvali (10.2-jadval) va chiqish jadvali (10.4-jadval) tomonidan berilgan Mur avtomati grafigiga misol rasmda ko'rsatilgan. 10.5.
O'rnatishning analitik usulida mavhum avtomatlar to'rtta ob'ekt bilan ifodalanadi, bu erda u avtomatning har bir holati uchun xaritalashni o'rnatadi. Boshqacha qilib aytadigan bo'lsak, avtomatning har bir holatini sozlashning analitik usulida barcha uchliklarning to'plami bo'lgan displey ko'rsatiladi va kirish signali ta'sirida avtomat holatdan holatga o'tadi, chiqish signalini chiqarishda. umumiy ta'rif mavhum avtomat, ikkinchisi funksiyalar tavsifiga va ifodalarga muvofiq X ga teng: Xaritalash quyidagicha yoziladi:
Belgilangan o'tish jadvali (10.7-jadval) bilan ifodalangan Mealy avtomatining analitik vazifasi quyidagi shaklga ega.
Avtomatlarning ekvivalent o'zgarishini ko'rib chiqing. Ekvivalent avtomatlar - kirish alifbosidagi so'zlar to'plamining chiqish alifbosidagi so'zlar to'plamiga bir xil xaritalashiga olib keladiganlar. Faqat Mur avtomatining ekvivalent Mealy avtomatiga aylanishini ko'rib chiqing. Mealy avtomatini uning ekvivalenti Mur avtomatiga aylantirish biroz murakkabroq.
Mur avtomatidan ekvivalent Mealy avtomatiga o'tish avtomatlarni aniqlashning grafik usuli yordamida amalga oshirish uchun qulaydir. Bu holatda, Mur avtomati tomonidan chiqarilgan chiqish signalini holatda harf bilan belgilangan cho'qqiga kiruvchi yoylarga o'tkazishga qisqartiriladi.O'rnatishning matritsa usulida Mealy avtomatining o'tish jadvali o'tish bilan mos keladi. Mur avtomatining jadvali va Mealy avtomatining chiqish jadvali uning o'tish jadvalidan kirish signali bilan belgilangan ustunning kesishmasida joylashgan harf holatini va Mur avtomati tomonidan chiqarilgan chiqish signaliga chiziqni almashtirish orqali olinadi. davlatda
Haqiqiy avtomatlarni ishlab chiqish (hech bo'lmaganda fundamental darajada taqdim etilgan elektr zanjirlari) avtomat sxemasida qo'llaniladigan mantiqiy elementlar va ular orasidagi bog'lanishlarni hisobga olgan holda, keyinchalik strukturaviy darajaga o'tish bilan birinchi navbatda ularni mavhum darajada belgilashni talab qiladi. Shu munosabat bilan, mavhum avtomatni sintez qilish muammosi, ba'zi bir dastlabki, masalan, uning ishining og'zaki tavsifidan kelib chiqadi. Mavhum avtomatlarni sintez qilishning mavjud algoritmlari, odatda, hisob-kitoblarning murakkabligi va og'irligi tufayli amaliyotda qo'llanilmaydi va shuning uchun darslik materialiga kiritilmaydi. Biroq, mavhum avtomat tushunchasini va uni aniqlash usullarini yaxshiroq tushunish uchun bu erda biz sof spekulyativ mulohazalar asosida mavhum avtomat sintezi misolini ko'rib chiqamiz.
Misol. Avtomatik qurilmaning kirishida faqat "svetoforni o'zgartirish" signali qabul qilingan taqdirda, svetoforni almashtirish uchun mavhum raqamli avtomatik boshqaruvni yarating. Keling, bu signalni harf bilan va uning yo'qligini - harf bilan belgilaymiz
Shubhasiz, bunday avtomatning X kirish alifbosi ikkita harfdan iborat bo'ladi: Sintezlangan avtomat svetoforning qizil, sariq va qizil rangga o'tishini ta'minlashi kerak. yashil rang, keyin uchta mos chiqishni boshqarish signalini kiritamiz.Shuningdek, ish boshlanishi momentida avtomat holatda bo'lsin deb faraz qilaylik.Ishlash algoritmi ahamiyatsiz; Mealy mashinasi uchun mumkin bo'lgan yechim shaklda ko'rsatilgan. 10.6, va Mur avtomati uchun - rasmda. 10.7. (Soddalashtirish uchun, biz taxmin qilamizki, Mur avtomati vaqtning dastlabki daqiqasida "yashil rangni yoqing" chiqish signalini chiqaradi. Avtomat grafigini yaratish uchun siz to'rt xil holatni kiritishingiz kerak bo'ladi. Holatlar soni mumkin. masalan, avtomatning kirish signallari sonini ko'paytirish yoki boshqaruv jarayonining rivojlanish tarixini o'z vaqtida yodlash nuqtai nazaridan kengaytirish yo'li bilan qisqartirilishi mumkin (bu misolda faqat oxirgi chiqish signalini berish momenti yodlanadi. ).
Xulosa qilib shuni ta'kidlaymizki, biz faqat deterministik avtomatlarni ko'rib chiqamiz, ular uchun o'tishlarning yagonaligi sharti bajariladi: ma'lum bir holatdagi avtomat har qanday kirish signali ta'sirida bir nechta holatga o'tishi mumkin emas. O'tish jadvali tomonidan ko'rsatilgan avtomat har doim deterministikdir, chunki o'tish jadvalining ustuni va qatori kesishgan joyda, agar o'tish aniqlangan bo'lsa, faqat bitta holat yoziladi va o'tish aniqlanmagan bo'lsa, chiziqcha qo'yiladi. Avtomatni aniqlashning grafik usulida qo'llaniladigan yagonalik sharti bir xil kirish signali bilan belgilangan ikki yoki undan ortiq yoylar avtomat grafigidagi biron bir cho'qqidan chiqib keta olmasligini bildiradi.
1.1 Asosiy tushunchalar
1.4 Mealy va Mur modellari o'rtasidagi munosabat
1.5 Ekvivalent mashinalar. Avtomatlarning ekvivalent transformatsiyalari
1.6 Mashinaning ichki holatlari sonini minimallashtirish
Adabiyotlar ro'yxati
Kirish
Mavzu sinov ishi“Raqamli avtomatlarning amaliy nazariyasi” fanidan – “Abstrakt raqamli avtomatlar”.
Ishning maqsadi - mavhum raqamli avtomatlarning asosiy tushunchalari bilan tanishish; mavhum avtomatlar turlari; mavhum avtomatlarni aniqlash usullari; Mealy va Mur modellari o'rtasidagi aloqa; ekvivalent avtomatlar va avtomatlarning ekvivalent transformatsiyalari; avtomatning ichki holatlari sonini minimallashtirish va Aufenkamp-Hon algoritmi.
1. Abstrakt raqamli avtomatlar
1.1 Asosiy tushunchalar
Raqamli avtomatni qandaydir algoritmga muvofiq diskret ma'lumotlarni qabul qiluvchi, saqlaydigan va o'zgartiruvchi qurilma sifatida talqin qilish mumkin. Muayyan nuqtai nazardan, real qurilmalar (kompyuterlar) ham, mavhum tizimlar ham (matematik modellar) avtomatlar sifatida tasniflanishi mumkin.
Avtomat deyiladi diskret konvertor turli holatlarni qabul qilish, kirish signallari ta'sirida bir holatdan ikkinchi holatga o'tish va chiqish signallarini ishlab chiqarishga qodir bo'lgan axborot.
Avtomatlarning umumiy nazariyasi mavhum va strukturaga bo'linadi.
Avtomatning mavhum nazariyasi avtomatning strukturasidan abstraktsiyalash (ya'ni, uni qurish usuli bilan qiziqmaslik) faqat avtomatning tashqi muhitga nisbatan xatti-harakatlarini o'rganadi. Avtomatlarning mavhum nazariyasi algoritmlar nazariyasiga yaqin bo'lib, mohiyatiga ko'ra uning keyingi amalga oshirilishi hisoblanadi.
Avtomatlarning mavhum nazariyasidan farqli o'laroq, avtomatlarning strukturaviy nazariyasi ham avtomatning tuzilishi, ham avtomatning kirish harakatlari va ularga bo'lgan javoblarining tuzilishi bilan qiziqadi. Strukturaviy nazariyada avtomatlarni qurish usullari, kirish harakatlarini kodlash usullari va avtomatning ularga bo'lgan javoblari o'rganiladi. Avtomatlarning strukturaviy nazariyasi mavhum nazariyaning davomi va rivojlanishi hisoblanadi. Mantiqiy funksiyalar apparati va avtomatlarning mavhum nazariyasiga asoslanib, strukturaviy nazariya haqiqiy hisoblash qurilmalarini ishlab chiqish uchun samarali tavsiyalar beradi.
Mavhum raqamli avtomat (DA) diskret boshqaruv qurilmasining matematik modelidir.
Mavhum CA oltita elementdan iborat to'plam bilan belgilanadi:
, a o),X = (x 1, x 2,. X n) - kirish signallari to'plami (kirish alifbosi);
Y = (y 1, y 2, y m) - chiqish signallari to'plami (chiqish alifbosi);
A = (a 0, a 1, a 2,. A N) - holatlar to'plami (shtatlar alifbosi);
a o - boshlang'ich holat (a o
A); - xaritalashni ko'rsatuvchi avtomatning o'tish funktsiyasi (XxA) A, ya'ni. Dekart ko‘paytmasining (XxA) har qanday juft elementlarini A to‘plam elementi bilan bog‘lash;- xaritalash (XxA) ni ko'rsatuvchi avtomat chiqishlarining funksiyasi
Y yoki xaritalash AY.Boshqacha aytganda, o'tish funktsiyasi
avtomat S ma'lum a j A holatda bo'lib, kirish signali x j X paydo bo'lganda, ma'lum a p A holatga o'tishini ko'rsatadi. Buni quyidagicha yozish mumkin: (a i, X j).Chiqish funktsiyasi avtomat S qandaydir a j holatda bo'lishini ko'rsatadi
Va, x j X kirish signali paydo bo'lganda, u chiqish signalini beradi y k Y. Buni yozish mumkin: y k = (a i , X j).Avtomat ta'rifiga holat tushunchasi ko'pincha chiqishi nafaqat ma'lum bir vaqtdagi kirish holatiga, balki ba'zi bir omillarga ham bog'liq bo'lgan tizimlarning xatti-harakatlarini tavsiflash zarurligi sababli kiritilgan. tarixdan oldingi, ya'ni avvalroq tizim kirishlariga kelgan signallardan. Holat shunchaki o'tmish xotirasiga to'g'ri keladi, bu sizga vaqtni aniq o'zgaruvchi sifatida yo'q qilish va chiqish signallarini ma'lum bir vaqtda holatlar va kirishlar funktsiyasi sifatida ifodalash imkonini beradi.
Mavhum avtomat diskret avtomat vaqtida t = 0,1,2 , ishlaydi. va davlatdan shtatga o'tish bir zumda sodir bo'ladi. Diskret vaqtning har bir t lahzasida avtomat avtomatning holatlari to'plamidan ma'lum a (t) holatda bo'ladi va t = 0 boshlang'ich vaqtda u doimo boshlang'ich a o holatda bo'ladi. t vaqtida, a (t) holatida, avtomat kirish kanalida x (t) signalini idrok eta oladi.
X, va a (t + 1) = (a (t), x (t)) holatiga o'tib, chiqish kanalida y (t) = (a (t), x (t)) signalini yuboring. Chiqish signalining kirish signaliga va holatga bog'liqligi uning xotirani o'z ichiga olganligini bildiradi.1.2 Abstrakt avtomatlarning turlari
Chiqish funktsiyasini yaratish usuliga ko'ra, mavhum avtomatlarning uch turi ajralib turadi: Mealy avtomati, Mur avtomati va C-avtomat. Mealy avtomati tenglamalar tizimi bilan tavsiflanadi:
(a (t), x (t));a (t + 1) = d (a (t), x (t)). (1-1)
Mur avtomati - tenglamalar tizimi bo'yicha:
(da));a (t + 1) = d (a (t), x (t)). (1-2)
S-avtomat - tenglamalar tizimi bo'yicha:
y 2 (a (t), x (t)); 2 (a (t));a (t + 1) = d (a (t), x (t)).
Ixtiyoriy abstrakt Mealy yoki Mur avtomati (1.1-rasm) bitta kirish va bitta chiqish kanaliga ega. Ixtiyoriy abstrakt C-avtomatida bitta kirish va ikkita chiqish kanali mavjud (1.2-rasm).
1.1-rasm - Abstrakt avtomat
1.2-rasm Abstrakt C-avtomat
Agar abstrakt Mealy yoki Mur avtomati kiritilsa, boshlang'ich a o holatiga o'rnatilgan bo'lsa, kirish alifbosidagi harflarning ma'lum bir ketma-ketligi x (0), x (1) , harflar bilan yuboriladi. kirish so'zi bo'lsa, u holda avtomatning chiqishida y (0), y (1) , chiqish alifbosining harflari paydo bo'ladi. chiqish so‘zidir. C-avtomatining holati uchun uning chiqishlarida ikkita ketma-ketlik paydo bo'ladi: y 1 (0), y 1 (1) ,. va y 2 (0), y 2 (1) ,. Mavhum C - avtomatda chiqish signali y 2 (t) =
(a (t)) har doim avtomat a (t) holatida bo'lganda chiqariladi. Chiqish signali y 1 (t) = l 1 (a (t), x (t)) kirish signalining x (t) ta'sirida C-mashina a (t) holatda bo'lganda chiqariladi.Shunday qilib, mavhum nazariya darajasida raqamli avtomatning ishlashi kirish so'zlarini chiqish so'zlariga aylantirish sifatida tushuniladi.
To'liq aniqlangan va qisman avtomatlar ajralib turadi.
Mavhum raqamli avtomat, agar u oʻtish funksiyasi yoki chiqish funksiyasiga ega boʻlsa yoki bu funksiyalarning ikkalasi ham barcha oʻtish juftliklari (x i, a j) uchun aniqlangan boʻlsa, toʻliq aniqlangan deb ataladi.
Mavhum raqamli avtomat, agar u o'tish funktsiyasi yoki chiqish funktsiyasiga ega bo'lsa yoki bu funktsiyalarning ikkalasi ham barcha o'tish juftliklari (x i, a j) uchun aniqlanmagan bo'lsa, qisman deyiladi.
Mavhum raqamli avtomat, agar uning A holatlar to'plamida a o boshlang'ich holati ajratilgan bo'lsa, boshlang'ich deyiladi.
1.3 Mavhum avtomatlarni aniqlash usullari
S chekli holat mashinasini aniqlash uchun to‘plamning barcha elementlarini tavsiflash kerak: S = (X, A, Y,
,, a o). Mashinaning ishlashini sozlashning bir necha usullari mavjud, lekin eng ko'p ishlatiladigan jadval (matritsa), grafik va analitik.Jadval rejimida avtomat ikkita jadval bilan belgilanadi: o'tish jadvali va chiqish jadvali yoki ulanishlar matritsasi. O'zboshimchalik bilan to'liq aniqlangan avtomatning o'tish jadvali quyidagicha tuziladi: jadvalning qatorlari avtomatning kirish alifbosi harflari bilan, jadval ustunlari esa davlat alifbosi harflari bilan belgilanadi. avtomat; O'tish jadvalining xi kirish signali bilan belgilangan qator va aj holati bilan belgilangan ustun kesishmasida joylashgan katakchasiga avtomatning aj holatidan o'tish natijasi bo'lgan ak holati qo'yiladi. xi kirish signali ta'sirida, u ak = ifodasi bilan aniqlanadi
(a j, x j).6 Mavhum avtomatlar nazariyasining asosiy tushunchalari va ta'riflari (9-ma'ruza)
Raqamli (diskret) avtomat (DA) - bu qandaydir algoritmga muvofiq diskret ma'lumotlarni qabul qiluvchi, saqlaydigan va/yoki o'zgartiruvchi qurilma. CA ga misollar tirik organizmlar, protsessorlar, maishiy texnika, kalkulyatorlar bo'lishi mumkin - bular haqiqiy qurilmalar va mavhumlar ham mavjud, masalan, algoritmlar modellari. Maqsadli auditoriyaga murojaat qiling ketma-ket qurilmalar. Ushbu qurilmalar sinfi chiqishlarning qiymati nafaqat kirish qiymatlariga, balki qurilmaning joriy holatiga ham bog'liqligi bilan belgilanadi. Bular. tushunchasi kiritildi - holat... Maqsadli auditoriyada qurilmaning holati to'g'risidagi ma'lumotlarni saqlash uchun saqlash elementlari - triggerlar qo'llaniladi.
6.1 Raqamli avtomatning matematik modeli
Raqamli avtomat - bu o'rnatilgan dastur buyruqlari ta'siri ostida tushadigan ichki holatlar to'plami bilan tavsiflangan qurilma. Avtomatning bir holatdan ikkinchisiga o'tishi ma'lum bir vaqtda amalga oshiriladi.
Maqsadli auditoriyaning matematik modeli (va har qanday diskret qurilmaning umumiy holatida) 6 komponentli kortej sifatida aniqlangan mavhum avtomat deb ataladi: S = (A, X, Y, , , a 1) unda:
A = (a 1, a 2, ..., a m) - davlatlar alifbosi - loyihalashtirilgan raqamli avtomat bo'lishi mumkin bo'lgan holatlar to'plami. Davlatlar soni maqsadli auditoriyani amalga oshirishda muhim rol o'ynaydi. Qanchalik ko'p holatlar bo'lsa, maqsadli auditoriyani yaratish uchun shunchalik ko'p xotira elementlari (triggerlar) talab qilinadi.
X = (x 1, x 2, ..., x f) - kirish qiymatlari alifbosi - CA kirishiga berilishi mumkin bo'lgan qiymatlar to'plami. Misol uchun, agar mashinada ikki raqamli ikkilik kiritish bo'lsa, u holda alifboning elementlari 00, 01, 10 va 11 bo'lishi mumkin.
Y = (y 1, y 2, ..., y g) - chiqish qiymatlari alifbosi - CA chiqishida o'rnatilishi mumkin bo'lgan qiymatlar to'plami.
: A • XA - o'tish funksiyasi a (t + 1) = (x (t), a (t))... O'tish funktsiyasi qaysi holatni aniqlaydi a (t + 1) mashina kirish signali ta'sirida o'zgaradi x (t), agar hozirgi vaqtda avtomat holatda bo'lsa da).
: A • ZW - chiqishlarning funksiyasi y(t)= (a(t), x(t)). Chiqishlarning funktsiyasi qaysi chiqish qiymatini aniqlaydi y(t) kirish qiymatiga qarab mashinaning chiqishiga o'rnatiladi x(t) va hozirgi holat a(t) .
a i A - mashinaning dastlabki holati - quvvat yoqilgandan keyin yoki qayta o'rnatilgandan keyin DA o'rnatiladigan holat
6.1-rasm - Abstrakt avtomat
Mavhum avtomat (6.1-rasm) bitta kirish va bitta chiqishga ega. Avtomat diskret vaqtda ishlaydi, manfiy bo'lmagan butun son qiymatlari t = 0,1,2, ... Diskret vaqtning har bir t lahzasida avtomatika holatlar to'plamidan qandaydir a (t) holatda bo'ladi. avtomat va dastlabki lahzada t = 0 u har doim a (0) = a1 boshlang'ich holatda bo'ladi. Hozirgi vaqtda t, a (t) holatida, avtomat kirishda X (t) alifbosining harfini idrok eta oladi. Z. Chiqishlarning vazifasiga muvofiq, u bir vaqtning o'zida t chiqadigan alifbo harfini y (t) = (a (t), z (t)) va o'tishga mos ravishda chiqaradi. funktsiyasi bo'lsa, u keyingi holatga o'tadi a (t + 1 ) = , a (t) A, y (t) Y.
Mavhum avtomat tushunchasining ma’nosi shundan iboratki, u X kirish alifbosidagi so‘zlar to‘plamini Y chiqish alifbosi so‘zlari to‘plamiga ma’lum bir xaritalashni amalga oshiradi. Ya’ni, agar kirish alifbosidagi harflar ketma-ketligi x (0), x (1), ... kirish so'zi avtomatning kirishiga a1 boshlang'ich holatiga o'rnatilgan bo'lsa, u holda chiqish alifbosining harflari y. (0 ), y (1), ... chiqish so‘zi. Bu. chiqish so'zi = (kirish so'zi), bu erda - abstrakt avtomat tomonidan bajariladigan xaritalash.
Mavhum nazariya darajasida "avtomatning ishi" tushunchasi kirish so'zlarini chiqishga aylantirish sifatida tushuniladi. Aytishimiz mumkinki, mavhum avtomatda biz uning tuzilishidan - to'rtburchakning tarkibidan mavhumlashamiz (6.1-rasm), uni "qora quti" deb hisoblaymiz, ya'ni. biz tashqi muhitga nisbatan avtomatning xatti-harakatiga e'tibor qaratamiz.
Avtomatni ta'riflashda holat tushunchasi ko'pincha chiqishlari nafaqat ma'lum bir vaqtning o'zida kirish holatiga, balki ba'zi bir omillarga ham bog'liq bo'lgan tizimlarning xatti-harakatlarini tavsiflash zarurati tufayli kiritilgan. tarixdan oldingi, ya'ni ilgari tizim kirishlarida qabul qilingan signallardan. Davlatlar shunchaki o'tmishdagi xotiraga mos keladi, bu sizga vaqtni aniq o'zgaruvchi sifatida yo'q qilish va chiqish signalini ma'lum bir vaqtda holat va kirish funktsiyasi sifatida ifodalash imkonini beradi.
6.2 Raqamli mashinalarning tasnifi
Yuqorida muhokama qilingan mavhum avtomatlarni quyidagilarga bo'lish mumkin:
to'liq aniqlangan va qisman;
deterministik va ehtimollik;
sinxron va asinxron;
Qisman o‘tish funksiyasi yoki chiqish funksiyasi yoki bu funksiyalarning ikkalasi ham barcha juftliklar (a i, z j) uchun aniqlanmagan mavhum avtomat deb ataladi.
TO deterministik O'tishlarning yagonaligi sharti bajariladigan avtomatlar mavjud: ma'lum a i holatidagi avtomat har qanday kirish signali z j ta'sirida bir nechta holatga o'ta olmaydi.
Aks holda bo'ladi ehtimolli avtomat , bunda berilgan a i holati va berilgan kirish signali z j uchun berilgan ehtimollik bilan turli holatlarga o‘tish mumkin.
Aniqlash uchun sinxron va asinxron avtomat kontseptsiyani taqdim etadi barqaror holat ... Avtomatning a s holati, agar har qanday a i holat va kirish signali z j uchun (a i, z j) = a s (a s, z j) = a s bo‘lsa, barqaror deyiladi. agar bu holatga qandaydir zj signali taʼsirida kirsa, avtomat uni faqat z j dan farq qiladigan boshqa z k signali taʼsirida qoldirsa, holat barqaror hisoblanadi.
Barcha holatlar barqaror bo'lgan avtomat - asinxron .
Mashina chaqiriladi sinxron agar u asinxron bo'lmasa.
Mavhum avtomat deyiladi final
to'plamlar A = (a 1, a 2, ..., am), Z = (z 1, z 2, ..., zf), W = (w 1, w 2, ..., wg ) . Mashina chaqiriladi boshlang'ich
agar unda boshlang'ich holat 1 tanlangan bo'lsa.
6.3 Raqamli mashinalarning turlari
Amalda eng keng tarqalgan mashinalarning ikki klassi - Mealy va Mur mashinalari.
Mealy avtomatining ishlash qonuni tenglamalar bilan berilgan:
a (t + 1) = (a (t), z (t)); w (t) = (a (t), z (t)), t = 0,1,2, ...
Mur avtomatining ishlash qonuni tenglamalar bilan berilgan:
a (t + 1) = (a (t), z (t)); w (t) = (a (t)), t = 0,1,2, ...
Ishlash qonuniyatlarini taqqoslash shuni ko'rsatadiki, Mealy avtomatidan farqli o'laroq, Mur avtomatidagi chiqish signali faqat avtomatning hozirgi holatiga bog'liq va kirish signaliga aniq bog'liq emas. Mealy yoki Mur avtomatining to'liq tayinlanishi uchun, ish qonunlariga qo'shimcha ravishda, dastlabki holatni ko'rsatish va ichki, kirish va chiqish alifbolarini aniqlash kerak.
Mealy va Mur avtomatlariga qo'shimcha ravishda, ba'zida C-avtomat deb ataladigan birlashtirilgan avtomat modelidan foydalanish qulay bo'lib chiqadi.
Mavhum C-avtomatni bitta kirishga ega bo'lgan, X kirish alifbosidan signallarni qabul qiluvchi va ikkita chiqishga ega bo'lgan qurilma sifatida ifodalash mumkin, ularda Y va U alifbolaridan signallar paydo bo'ladi.S-avtomat va Mealy va o'rtasidagi farq Mur modellari shundan iboratki, u bir vaqtning o'zida 1 va 2 chiqishlarning ikkita funktsiyasini amalga oshiradi, ularning har biri alohida ushbu modellarga xosdir. S-avtomatining ishlash qonunini quyidagi tenglamalar bilan tavsiflash mumkin:
a (t + 1) = (a (t), z (t)); w (t) = 1 (a (t), z (t)); u (t) = 2 (a (t)); t = 0, 1, 2, ...
Chiqish signali U h = 2 (a m) har doim avtomat a m holatda bo'lganda chiqariladi. Chiqish signali Wg = 1 (a m, z f) avtomat a m holatda bo'lganda kirish signali Z f ta'sirida chiqariladi.
7 Mashinalarni tavsiflash va belgilash usullari (10-ma'ruza)
Avtomatni aniqlash uchun S = (A, X, Y, , , a 1) kortejning barcha komponentlarini tavsiflash kerak. A, X, Y to'plamlar ularning elementlarini oddiy sanab o'tish orqali tavsiflanadi va ko'rsatiladi. va funktsiyalarini (shuning uchun butun avtomatni) belgilashning turli xil usullari orasida jadval va grafik usullar eng keng tarqalgan.
7.1 Raqamli mashinalarni tavsiflashning jadval usuli
Raqamli mashinalarni tavsiflashning jadval usulida ikkita turdagi jadvallar qo'llaniladi - o'tish jadvali va chiqish jadvali.
O'tish stoli o‘tish funksiyasini ko‘rsatadi. Jadvalning chiziqlari mashinaning holatiga mos keladi, ya'ni. jadvalda qancha satrlar mashinada qancha holatlar mavjud bo'lsa. Jadvalning ustunlari DA kirishlariga o'tishi mumkin bo'lgan kirish qiymatlariga mos keladi, ya'ni. ko'p ustun - kirish alifbosida qancha element bor. Jadval katakchasidagi i-ustun va j-satrning kesishmasida, aj holatidan (i-ustunga mos keladigan) xi kirish signali taʼsirida CA qaysi holatga oʻtadi. j-chi qatorga mos keladi) ko'rsatilgan. O'tish jadvali 6.2-rasmda ko'rsatilgan.
|
x 1 |
x 2 |
… |
x m |
|
|
a 1 |
a 2 |
a 1 |
… |
a 2 |
|
a 2 |
a n-1 |
a 3 |
… |
a 1 |
|
… |
… | |||
|
a n |
- |
a n |
… |
a 2 |
Shakl 6.2 - CA o'tishlari jadvali
O'tish jadvali Mur va Miles mashinasi uchun bir xil ko'rinadi. Mealy va Mur qisman avtomatlari uchun ko'rib chiqilgan jadvallarda aniqlanmagan holatlar va chiqish signallari o'rniga chiziqcha qo'yiladi. Bunday avtomatlarda, agar o'tish holati aniqlanmagan bo'lsa, har qanday o'tishdagi chiqish signali har doim aniqlanmagan.
Chiqish stoli uchun Mil mashinasi o'tish jadvali bilan bir xil shaklga ega, faqat jadval katakchasidagi i-ustun va j-satrning kesishmasida, chiqish qiymati ko'rsatiladi, u kirish signali xi ta'sirida CA ni hosil qiladi (bu mos keladi i-ustun) aj holatida (bu j- i qatoriga mos keladi). Mealy mashinasining chiqishlar jadvali 6.3-rasmda ko'rsatilgan.
|
x 1 |
x 2 |
… |
x m |
|
|
a 1 |
y 1 |
y 3 |
… |
y 1 |
|
a 2 |
y n-1 |
y 2 |
… |
y n-1 |
|
… |
… | |||
|
a n |
- |
y 1 |
… |
y 2 |
Shakl 6.3 - Miles mashinasining chiqishlari jadvali
Chiqish stoli uchun Murning avtomati bitta ustundan iborat. Jadvalning chiziqlari mashinaning holatiga mos keladi, ya'ni. jadvalda qancha satrlar mashinada qancha holatlar mavjud bo'lsa. Jadvalning namunasi 6.4-rasmda ko'rsatilgan.
|
x 1 |
|
|
a 1 |
y 1 |
|
a 2 |
y n-1 |
|
… | |
|
a n |
y 2 |
6.4-rasm - Mur avtomatining chiqishlari jadvali
Ba'zi hollarda, maqsadli auditoriyani aniqlaydigan ikkita jadval o'rniga foydalanish qulay birlashtirilgan o'tish va chiqish jadvali. 6.5-rasmda Mealy mashinasi uchun birlashtirilgan jadval ko'rsatilgan. 6.6-rasmda Mur avtomati uchun birlashtirilgan o'tish jadvali ko'rsatilgan.
|
x 1 |
x 2 |
… |
x m |
|
|
a 1 |
a 2 / y 1 |
a 1 / y 3 |
… |
a 2 / y 1 |
|
a 2 |
a n-1 / y n-1 |
a 3 / y 2 |
… |
a 1 / y n-1 |
|
… |
… | |||
|
a n |
- |
a n / y 1 |
… |
a 2 / y 2 |
6.5-rasm - Miles mashinasining o'tish va chiqishlarining birlashtirilgan jadvali
|
x 1 |
x 2 |
… |
x m |
Y |
|
|
a 1 |
a 2 |
a 1 |
… |
a 2 |
y 2 |
|
a 2 |
a n-1 |
a 3 |
… |
a 1 |
y 1 |
|
… |
… | ||||
|
a n |
- |
a n |
… |
a 2 |
y 2 |
Shakl 6.6 - Kombinatsiyalangan Mur avtomatining o'tish jadvali
7.2 Raqamli mashinalarni sozlashning grafik usuli
Grafik usulda avtomat yo'naltirilgan grafik shaklida ko'rsatiladi, uning uchlari holatlarga, yoylari esa ular orasidagi o'tishlarga mos keladi. A m cho'qqisidan yo'naltirilgan yoy avtomatdagi a m holatdan a s holatga o'tishni belgilaydi. Ushbu yoyning boshida X f X kirish signali yoziladi, bu o'tishni a s = (a m, x f) keltirib chiqaradi. Mealy avtomatining grafigi uchun o'tishda hosil bo'lgan yg Y chiqish signali yoy oxirida yoziladi, Mur avtomati uchun esa am cho'qqisiga yaqin, am holati bilan belgilanadi. yaratilgan. Agar avtomatda a m holatdan a s holatga o’tish bir necha kirish signallari ta’sirida amalga oshirilsa, u holda bu barcha kirish va mos chiqish signallari a m dan a s gacha yo’naltirilgan grafik yoyga tayinlanadi. C-avtomatning grafigi ikki turdagi chiqish signallarini o'z ichiga oladi va ular tegishli avtomatlarning grafiklaridagi kabi grafikda belgilanadi. Mur avtomatining grafigi 6.7-rasmda, Mealy avtomatining grafigi 6.8-rasmda ko'rsatilgan.
y 2
6.7-rasm - Mur avtomatining grafik tasviri
6.8-rasm - Miles mashinasining grafik tasviri
8 Raqamli avtomatlarning abstrakt sintezi
Raqamli avtomatlar nazariyasi raqamli avtomatlarning mavhum va strukturaviy sintezini tekshiradi. Abstrakt sintez avtomatning ichki tuzilishini tavsiflamaydi, lekin u bilan o'zaro ta'sirini tavsiflaydi. muhit... Abstrakt sintez quyidagilarni o'z ichiga oladi:
holatlarning kirish, chiqish va alifbosini, o'tish va chiqish funktsiyalarini aniqlash;
avtomatning grafiklarini va o'tish va chiqish jadvallarini belgilash;
shtatlar sonini minimallashtirish
8.1 Raqamli mashinaning tuzilishi
Raqamli mashinaning ichki tuzilishini 8.1-rasmda ko'rsatilganidek tasvirlash mumkin.
8.1-rasm - Raqamli mashinaning blok diagrammasi.
1-sonli kombinatsiya sxemasi kirish signallari ta'sirida mashinaning bir holatdan ikkinchisiga o'tishlarini amalga oshiradi. Sxema kodlangan o'tish jadvali va tanlangan saqlash elementining o'tish subgrafiyasi asosida ishlab chiqilgan.
Xotira bloki - bu kodlangan holat raqamining bitlarini saqlaydigan flip-floplar to'plami. Triggerlar soni avtomat bo'lishi mumkin bo'lgan holatlar soniga bog'liq. Va u quyidagicha hisoblanadi:
N = log 2 M
Bu erda M - holatlar soni, N - triggerlar soni
2-sonli kombinatsiyalash sxemasi mashinaning chiqishlari funktsiyasini amalga oshiradi va uning chiqishida mashinaning chiqish qiymatlari quyidagilarga muvofiq o'rnatiladi. hozirgi holat avtomat va kirish qiymatlari.
8.2 Raqamli mashinaning holatlar sonini minimallashtirish
Ko'pincha, mavhum sintezni amalga oshirishda, ekvivalentligi aniq bo'lmagan ortiqcha holatlar kiritiladi. Haddan tashqari ko'p holatlar keraksiz triggerlardan foydalanishga olib kelishi mumkin, bu esa KC1 va KC2 ni murakkablashtiradi. Shuning uchun uning tarkibiy sintezidan oldin holatlar sonini minimallashtirishni amalga oshirish juda muhimdir.
Minimallashtirish algoritmi barcha holatlar to'plamini ekvivalent holatlarning juft-juft ajratilgan sinflariga bo'lish va butun ekvivalentlik sinfini bitta holat bilan almashtirishga asoslangan. Olingan minimallashtirilgan avtomat dastlabki holatlar to'plami qancha ekvivalentlik sinfiga bo'linganiga shunchalik ko'p holatlarni o'z ichiga oladi.
Ta'rif
Ikki davlat a s va a m teng bo'lsa
(a s , E) =
(a m , E), qayerda
- o'tish funktsiyasi, E - ixtiyoriy uzunlikdagi kirish so'zi.
Boshqacha qilib aytganda, agar ikkita holatdan qat'i nazar, bir xil kiritilgan so'zlarga javoban bir xil holatlar ketma-ketligi hosil bo'lsa, holatlar ekvivalent hisoblanadi. a s yoki a m Dastlabki vaqtda avtomat bor edi. Agar ikkita holat ekvivalent bo'lsa, unda bir holat boshqasi bilan almashtirilishi mumkin.
Ekvivalent holatlardan tashqari k-ekvivalent holatlar tushunchasi mavjud: 1-ekvivalent, 2-ekvivalent va boshqalar.
Ta'rif
Ikki davlat a s va a m bork
-
ekvivalent bo'lsa
(a s , Ek) =
(a m , Ek), qayerda
- o'tish funktsiyasi, Ek- uzunlikdagi kirish so'zik
.
Minimallashtirish algoritmi:
Avtomatning holatlarining P 1, P 2, ... PK, PK + 1 bo'limlari ba'zi K + 1 qadamda PK + 1 P K ga teng bo'lgunga qadar ketma-ket topiladi. Bunda hosil bo'lgan k-ekvivalent bo'lim. to'liq ekvivalent sinflarni ifodalaydi.
Har bir ekvivalentlik sinfida bitta holat tanlanadi, ular minimallashtirilgan avtomatning yangi holatlar to'plamini tashkil qiladi.
O'tish va chiqish funktsiyalarini qayta aniqlash uchun minimallashtirilgan avtomatning yangi holatlar to'plamiga kiritilmagan holatlarga mos keladigan satrlar o'chiriladi va o'tish jadvalining qolgan qatorlarida barcha holatlar o'zlariga almashtiriladi. yangi to'plamga kirgan ekvivalent holatlar.
Agar to'plam bitta holatdan iborat bo'lsa, unda uning ekvivalent holatlari yo'q. Agar barcha holatlar bir holatdan alohida to'plamlarga kirsa, u holda avtomat minimallashtirish mumkin emas.
Bo'lish 0-ekvivalent sinfdan boshlanadi. Bunday holda, chiqish signallari bir xil bo'lgan holatlar bir xil to'plamlarga tushadi.
Bitta kirish, bitta chiqish va har bir daqiqada ko'p imkoniyatlardan bitta holatda bo'ladi. Ushbu qurilmaga kirish bitta alifboning belgilarini oladi, chiqishda u boshqa alifboning belgilarini (umumiy holatda) chiqaradi.
Rasmiy ravishda, mavhum avtomat beshlik sifatida aniqlanadi
Mavhum avtomatning parametrlari sonining cheklanishi bunday kontseptsiyani chekli avtomat sifatida aniqladi.
Avtomatning ishlashi ikkita ketma-ketlikni hosil qilishdan iborat: avtomatning ketma-ket holatlari ketma-ketligi. va chiqish belgilar ketma-ketligi , bu belgilar ketma-ketligi uchun diskret vaqt momentlarida ochiladi t = 1, 2, 3, ... Diskret vaqt momentlari shomil deb ataladi.
Avtomatning diskret vaqtlarda ishlashini t takroriy munosabatlar tizimi bilan tavsiflash mumkin:
Mavhum avtomatlarning xususiyatlarini aniqlashtirish uchun tasnif kiritiladi.
Mavhum avtomatlar mustaqil model sifatida va Tyuring mashinalari, FFS mashinalari, chekli avtomatlar va boshqa axborot konvertorlarining asosiy komponenti sifatida diskret modellarning asosiy sinfini tashkil qiladi.
"Mavhum avtomat" maqolasiga sharh yozing
Abstrakt avtomatni tavsiflovchi parcha
Imperator tabassum bilan o'z atrofidagilardan biriga o'girilib, apsheronlik yaxshi odamlarga ishora qildi va unga nimadir dedi.Kutuzov o'z ad'yutantlari hamrohligida karabinerlarni bosqichma-bosqich kuzatib bordi.
U ustunning dumida yarim chaqirimcha yo'l bosib o'tib, ikki yo'lning vilka yaqinidagi yolg'iz tashlandiq uyda (ehtimol, sobiq mehmonxona) to'xtadi. Ikkala yo'l ham pastga tushdi va qo'shinlar ikkalasida ham yurishdi.
Tuman tarqala boshladi va ikki chaqirim uzoqda, noma'lum muddatda, qarama-qarshi balandliklarda dushman qo'shinlarini ko'rish mumkin edi. Pastki chap tomonda otishma kuchaydi. Kutuzov avstriyalik general bilan gaplashishni to'xtatdi. Bir oz orqada turgan shahzoda Endryu ularga qaradi va ad'yutantdan teleskop so'ramoqchi bo'lib, unga o'girildi.
"Mana, qara," dedi bu ad'yutant uzoqdagi qo'shinga emas, balki uning oldidagi tog'dan pastga qarab. - Bular frantsuzlar!
Ikki general va adyutant trubani bir-biridan tortib olib, ushlay boshladilar. Hammaning yuzlari birdan o'zgarib ketdi va hammada dahshat paydo bo'ldi. Frantsuzlar bizdan ikki chaqirim uzoqda bo'lishi kerak edi, lekin ular birdan, kutilmaganda oldimizda paydo bo'ldi.
— Bu dushmanmi?... Yo‘q!... Ha, qara, u... ehtimol... Bu nima? - ovozlar eshitildi.
Knyaz Andrey oddiy ko'zlari bilan Kutuzov turgan joydan besh yuz qadam narida absheronliklarni kutib olish uchun ko'tarilgan qalin fransuz ustunini ko'rdi.
“Mana, hal qiluvchi daqiqa keldi! Bu menga keldi, - deb o'yladi knyaz Endryu va otni urib, Kutuzovga yaqinlashdi. — Absheronlarni to‘xtatishimiz kerak, — deb baqirdi u, — Janobi Oliylari! Ammo shu vaqtning o'zida hamma narsani tutun qopladi, yaqindan otishma eshitildi va knyaz Andreydan ikki qadam narida: "Xo'sh, birodarlar, shanba!" Va go'yo bu ovoz buyruq edi. Bu ovozdan hammasi yugura boshladi.
Aralash, tobora ko'payib borayotgan olomon besh daqiqa oldin qo'shinlar imperatorlar yonidan o'tgan joyga qochib ketishdi. Bu olomonni to'xtatish nafaqat qiyin, balki o'zimiz ham olomon bilan birga orqaga qaytmaslikning iloji yo'q edi.
Bolkonskiy faqat unga ergashishga harakat qildi va uning oldida nima qilinayotganini tushunolmay, dovdirab, atrofga qaradi. Nesvitskiy g'azablangan, qizarib ketgan va o'ziga o'xshamagan holda, Kutuzovga agar hozir ketmasa, asirga tushishi mumkinligini aytdi. Kutuzov o'sha joyda turdi va javob bermay, ro'molini oldi. Uning yonoqlaridan qon oqardi. Shahzoda Endryu uning oldiga bordi.
- Yaradormisiz? — so‘radi u jag‘i titrab arang ushlab.
- Yaralar bu yerda emas, qayerda! - dedi Kutuzov ro'molini yaralangan yuziga bosib, qochayotgan tomonga ishora qilib. - Ularni to'xtating! — deb qichqirdi va shu bilan birga, ehtimol, ularni to‘xtatib bo‘lmasligiga ishonch hosil qilib, otni urib, o‘ngga otlandi.
Sxemalarni mustaqil o'rganish. Abstrakt avtomat. 2-qism
- Yangi boshlanuvchilar uchun elektronika
Maqola yozilgan, to'plangan va terilgan. Katta raxmat.
Oldingi maqolada men ushbu maqolani iloji boricha aniqroq qilish uchun barcha asosiy ta'riflar va tamoyillarni tasvirlashga harakat qildim. Hammasi mos kelmadi, shuning uchun men sizga ushbu fayllar bilan tanishishingizni maslahat beraman:
Asos, Basis2, Minimallashtirish. Keyinchalik ushbu maqolada men kursivda bir nechta tushuntirish yozuvlarini qoldirdim.
Ushbu maqolada men tushuntirishga harakat qilaman kirish mumkin bo'lgan til mavhum avtomat nima, uni ifodalash usullari. Avtomatlar nazariyasi matematika va murakkablik bilan to'la bo'lganligi sababli, men tayyorlanmagan o'quvchi nima xavf ostida ekanligini tushunishi uchun inson tilida yozishga harakat qilaman.
Elektron raqamli sxemalarni rasmiy ravishda 2 sinfga bo'lish mumkin:
- Kombinatsiya sxemalari (CC) - xotira yo'q. Chiqish signali qarab hosil bo'ladi kombinatsiyalar Belgilangan vaqtda ma'lumotlarni kiritish (signalni aylantirish kechikishini hisobga olgan holda) Kombinatsiyalangan sxemalar, ularning turlari va qurilish tamoyillari alohida maqola uchun mavzu bo'lishi mumkin va misol sifatida: Boshqariladigan avtobuslar, multipleksorlar va demultipleksatorlar, dekoderlar va kodlovchilar, kod konvertorlari, kombinatsiya hisoblagichlari va topuvchilar va boshqalar.
- Xotira sxemalari - ularning ishlash algoritmi kirishlar holatiga bog'liq va xotira(vaqtning oldingi daqiqalarida nima bo'lgan). Bu sxemalar chekli avtomatlar nazariyasi yordamida tasvirlangan. Biz ular haqida batafsilroq gaplashamiz.
Abstrakt avtomat
Mashina ishlab chiquvchi tomonidan belgilangan ba'zi funktsiyalarni bajarishi kerak. Bu oddiy qo'shimcha bo'lishi mumkin, u har qanday protsessor mikroko'rsatmasini amalga oshirishi, RAMdan so'zlarni tanlashi yoki ifodani tahlil qilishi mumkin.Umuman olganda, tafsilotlarga berilmasdan, mavhum avtomatni quyidagicha ifodalash mumkin:
Yoki illyustratsiyadan matematik tavsifga o'tadigan bo'lsak:
A =
Afsona:
- To'plam (A) - bu mashinaning jismoniy kirishlaridagi qiymatlar to'plami. Kirishda, bizning holatlarimizda, yuqori va past kuchlanish darajalarining bir qator ketma-ketligi bo'ladi, ular mantiqiy nol va birlarni kodlaydi.
- To'plam (B) - bu mashinaning jismoniy chiqishidagi qiymatlar to'plami.
- To'plam (C) - va mashinaning ichki holatini ifodalovchi to'plam xotiradir. Kelajakda C0 avtomatning dastlabki holatini bildiradi.
- d = X × Z → Z avtomatning o'tish funksiyalari bo'lib, ular avtomatning aj holatidan o'tadigan ai holatini yagona aniqlaydi.
- l = X × Z → Y - chiqish funktsiyalari, ular kirishlar va ichki holatga qarab mashinaning chiqishida nima borligini aniqlaydi.
Bunday avtomat vaqt bo'yicha diskret ishlaydi, ya'ni kirish, chiqish qiymatlari va avtomatning ichki holati diskret vaqtlarda o'zgaradi.
Shunday qilib, biz mavhum avtomat nima ekanligini umumiy ma'noda tasvirlab berdik. Bunday avtomatlarga misol sifatida flip-flop, kompyuter registrini yoki to'ldiruvchini keltirish mumkin.
2 turdagi mashinalar mavjud:
- Miles avtomatlari. U tenglamalar tizimi bilan tavsiflanadi:
c (t) = d (a (t), c (t-1));
b (t) = l (a (t), c (t-1)). - Mur avtomati. Tenglamalar bilan tavsiflanadi:
c (t) = d (a (t), c (t-1));
b (t) = l (a (t), c (t)).
Mashinalar chiqish funksiyasi turida farqlanadi. Mealy mashinasida chiqish signali kirish signali a (t) va mashinaning oldingi c (t-1) vaqtidagi holati bilan aniqlanadi. Mur avtomatining chiqish signali kirish signalining juftligi a (t) va c (t) momentidagi holat bilan aniqlanadi.
Shuni ham ta'kidlash mumkinki, bir turdan ikkinchisiga va aksincha o'tish mumkin va Mealy avtomatidan Mur avtomatiga o'tishda avtomatning ichki holatlari soni bir xil bo'lib qoladi va teskari o'tish paytida, ichki davlatlar soni ortishi mumkin. Biz bu haqda batafsil to'xtalib o'tirmaymiz, o'zimizga kerakli turdagi avtomatni sintez qildik (grafik chizdik).
Shunday qilib, bu material bilan tugadi. Keling, mashinalarni tavsiflashga harakat qilaylik.
Bular. Mealy tipidagi avtomat oldingi holatiga qarab, kirish o'zgarganda chiqish signalini hosil qiladi. Bunday holda, chiqish signalining davomiyligi kirish signalining davomiyligiga bog'liq emas, balki faqat uning mavjudligiga bog'liq. Mur tipidagi mashinalarda chiqish signali hozirgi vaqtda mashinaning holatiga bog'liq, ya'ni. mashina o'z holatini o'zgartirmaguncha ma'lum bir chiqish signalini ishlab chiqaradi.
Avtomatlarni aniqlash usullari
Birinchi bo'limda bilib olganimizdek, avtomat kirish va chiqish alifbolari to'plami, o'tish va chiqishlarni aniqlaydigan ichki holatlar va funktsiyalar to'plamidir. Biroq, odatda d va l funktsiyalari ko'rsatilmaydi va avtomatning xatti-harakati boshqacha tarzda tasvirlanishi kerak.Avtomatni aniqlashning ikkita asosiy usuli mavjud:
- Grafiklardan foydalanish.
- O'tish jadvallari va chiqishlar yordamida.
Grafiklar
Avtomat grafigi yo‘naltirilgan bog‘langan grafik bo‘lib, uning uchlari avtomatning ichki holatlarini, yoylari esa bir holatdan ikkinchi holatga o‘tishni ifodalaydi.
Millar grafigi uchun o'xshash va chiqish harflari yoylarda ko'rsatilgan. Chiqish harflari yoylar ustiga yoziladi, bu chiqish holati avtomatning oldingi vaqtdagi holatiga bog'liqligini anglatadi.
Mur avtomatining grafigi uchun faqat kirish harflari yoylarga yoziladi, chiqish harflari esa cho'qqilar yonida ko'rsatiladi.
Muhim nuqta: agar har bir cho'qqidan qancha kirish harflari bo'lsa, shuncha yoy chiqsa, u holda avtomat deyiladi. to'liq... Boshqacha qilib aytganda, har bir kirish harfi uchun har bir tepadan o'tishlar aniqlansa. Bizning misollarimizda mashina Milya tugadi, va mashina Mur - qisman.
Va yana bir narsa: agar bitta cho'qqidan kirish harflariga qaraganda ko'proq yoylar chiqsa (ya'ni bir xil kirish harflari bilan 2 yoki undan ortiq yoylar), unda bunday avtomat deyiladi. deterministik bo'lmagan... Bu rasmiylashtirilgan tavsifni qurishda sodir bo'lishi mumkin va keyin unga o'tish kerak bo'ladi deterministik avtomatik mashina, lekin bu har doim ham amalga oshirilmaydi. Men ushbu jarayonning tavsifini ham qoldirib, darhol deterministik avtomatni chizaman.
Hammasi grafiklar haqida.
O'tish va chiqish jadvallari.
Grafiklar odamlar uchun, jadvallar esa mashinalar uchun aniqroq. Har qanday avtomat o'tish va chiqish jadvali (TPV) sifatida taqdim etilishi mumkin. TPVda chiziqlar avtomatning ichki holatlari, ustunlar esa kirish harflaridir.Keling, Mil va Mur grafiklarimiz uchun TPV quraylik. Agar kirish yoki chiqish harfi aniqlanmagan bo'lsa, uning o'rniga chiziqcha qo'yiladi. Agar davlat ko'rsatilmagan bo'lsa, xuddi shu oddiy qoida qo'llaniladi.
TPV Earl Miles
TPV Millarida o'tishlar va chiqishlar har bir hujayrada qayd etiladi. Misol uchun, agar avtomat C0 holatda bo'lsa va kirishga a1 harfi kelsa, u holda u C1 holatiga o'tadi va chiqishda b3 harfi paydo bo'ladi.
Count Murning TPV
Graf Mur uchun belgilangan sakrash stoli tuzilgan. Chiqish harflari uchun qo'shimcha ustun ajratiladi.Kirish harfi ostidagi katakka avtomat qaysi holatga o'tishi, eng o'ng katakchaga qaysi chiqish harfini qaytarishi yoziladi.
Avtomatni sintez qilish misoli
Mavhum avtomatlar bilan deyarli hamma narsani tasvirlash mumkin. Raqamli sxemaning ishlashini yoki sintaktik yoki leksik analizatorni tasvirlashingiz mumkin. Keling, tetikni tasvirlashga harakat qilaylik - bu avtomat emasmi?Grafikni o'rnatish uchun sizga trigger algoritmining og'zaki tavsifi kerak. Biz o'qiymiz:
Biz kirish va chiqish alifbolarini kodlaymiz:
A = (a0, a1), bu erda a0 - R kirishida mantiqiy 1, a1 - S kirishda mantiqiy.
B = (b0, b1), bu erda b0 - Q chiqishida mantiqiy 0, b1 - Q chiqishida mantiqiy.
Biz Miles avtomatining grafigini quramiz: 
Mana, kulgili Cheburashka chiqdi :-). Endi siz o'tish va chiqish jadvalini yaratishingiz mumkin: 
Agar biz ushbu jadvalni afsonani haqiqiyga aylantirish orqali bo'yasak, unda biz trigger o'tish jadvali bo'lgan jadvalni olamiz. Keyin uni soddalashtirish mumkin: 
Olingan funktsiyani Weich xaritasiga qo'llaymiz va minimallashtiramiz:
Keling, nima bo'lganini yozamiz: 
Biz funktsiya bo'yicha sxema tuzamiz (uy vazifangizni bajardingizmi?).
