Mavzu: Chekli avtomatlar. Mur va Mili avtomatlari

5- §. Mili va Mur avtomatlari


Chekli avtomat modeli. Avtomat ishining kanonik tenglamasi. Initsial va noinitsial avtomatlar. Mili va Mur avtomatlari va ular orasidagi munosabatlar.


5.1. Avtomatning ishini kanonik tenglama bilan ifodalash. Chekli xotirali diskret qurilmalar chekli avtomat modeli bo‘ladi. Bu avtomatning ta kirishi, ta chiqishi va chekli ichki holati mavjud.
Chekli avtomat diskret vaqt momentlarida ishlaydi. Agar momentdagi kirish, chiqish va holatining qiymatlarini mos ravishda , va bilan belgilasak, u holda avtomatning ishi quyidagi kanonik tenglamalar bilan ifodalanadi:

(1) tenglamalardagi va funksiyalar mos ravishda chiqishning funksiyasi va o‘tishlar funksiyasi deb ataladi. Avtomatning ish jarayonini aniqlash uchun uning boshlang‘ich holatini ko‘rsatish kerak.
Agar va 1 momentdagi kirish qiymatlari ma’lum bo‘lsa, u holda (1) kanonik tenglamadan foydalanib 1 momentdagi chiqish va holatning qiymatini, va asosida 2 momentdagi chiqish va holatlarini aniqlash mumkin va hokazo.
Ikki turdagi avtomatlar mavjud: initsial va initsialmas (noinitsial). Initsial avtomatlarda boshlang‘ich holat tayinlangan (mahkamlangan) bo‘ladi. Noinitsial avtomatlarda boshlang‘ich holat sifatida istalgan holatni olish mumkin.
5.2. Mili va Mur avtomatlari. Ixtiyoriy sondagi kirish va chiqishga ega bo‘lgan avtomat ishini aniqlash masalasi 1ta kirish va 1ta chiqishga ega bo‘lgan avtomatning ishini aniqlash masalasiga keltiriladi. Shuning uchun asosiy model sifatida 1ta kirishga va 1ta chiqishga ega bo‘lgan avtomatlarni ko‘ramiz. Bunday avtomatlar quyidagi kanonik tenglama bilan ifodalanadi:
, .
Bunday turdagi avtomat Mili¹ avtomati deb ataladi.
Mili avtomati chekli xotirali diskret qurilmaning yagona modeli emas. Ikkinchi model – Mur² avtomati mavjud. Mur avtomatida chiqish qiymati o‘sha momentning o‘zidayoq ichki holatning qiymati bilan aniqlanadi. Mur avtomatining kanonik tenglamasi quyidagi ko‘rinishda bo‘ladi:
, .
Agar birinchi tenglamadan ikkinchisiga qiymatini qo‘ysak va deb belgilasak, u holda ikkinchi tenglama quyidagi ko‘rinishga keladi
.
Demak, Mur avtomatini Mili avtomatining xususiy holi deb qarash mumkin. Bu yerda o‘tish funksiyasi maxsus ko‘rinishda bo‘ladi. Xuddi shu kabi, Mili avtomatini ham (qandaydir ma’noda) Mur avtomatiga keltirish mumkin.
Demak, har qanday initsial va noinitsial Mili avtomatlari uchun ularga ekvivalent bo‘lgan initsial va noinitsial Mur avtomatlari mavjud.³