Axborotlarga ishlov berish va boshqarish” kafedrasi tizimlarnazari ya s I fanidan Sirtqi ta’lim yo‘nalishi uchun Ma’ruza matni 5330200-«Informatika va axborot texnologiyalari»

35-rasm. Mur avtomatining o‘tishlar jadvali.
Mur avtomatidan ekvivalent Mili avtomatiga o‘tish teskari vazifasi quyidagicha bajariladi. Mili avtomatining hamda unga ekvivalent bo‘lgan Mur avtomatining o‘tishlar jadvali o‘zaro mos tushadi. Mili avtomatining chiqishlar jadvali quyidagicha tuziladi: jadvalning har bir katagiga shu katakda joylashgan holatga mos keluvchi holatni belgilovchi chiqish signali yoziladi. Bunda Mili avtomati grafining Mur avtomati grafidan farqi shundaki, har bir uzeldagi chiqish signali shu uzelga tegishli bo‘lgan barcha shoxlarga uzatiladi.
Qarab chiqilgan algoritmlar bo‘yicha olingan ekvivalent avtomatlar ortiqcha ichki holatga ega bo‘lib qolishi mumkin. Avtomatning holatlari soni minimallashtirilgan bo‘lishi mumkin.
SHunday avtomatlar ham bo‘lishi mumkinki, ularning kirishiga signallarning ba’zi ketma-ketliklari hech qachon berilmaydi. Bunday ketma-ketliklar ta’qiqlangan kirish so‘zlari deb, ta’qiqlangan kirish so‘zli avtomatlar esa qisman ishlovchi avtomatlar deb ataladi. Qisman ishlovchi avtomat grafi cho‘qqilarining chiquvchi shoxlari soni kirish alifbosidagi harflar sonidan kichik bo‘ladi. Qisman ishlovchi avtomatga mos keluvchi sxema minimal miqdordagi elementlardan tashkil topgan bo‘lishi uchun sintez jarayonida qisman ishlovchi avtomatni to‘la tavsiflab olinadi.
CHekli avtomat holatlari sonini minimallashtirish
Biror chekli avtomat «ortiqcha» ichki holatga ega bo‘lsin. Uning holatlari sonining minimallashtirish - unga ekvivalent, holatlar soni minimal bo‘lgan chekli avtomatni aniqlashni bildiradi.
CHekli avtomatning mumkin holatlar soni orasida quyidagi xossalarga ega bo‘lgan bir nechta holatlar mavjud bo‘lsin: ixtiyoriy kirish so‘ziga chekli avtomatning dastlabki momentida ko‘rsatilgan holatlarning qaysi birida bo‘lishiga bog‘liqsiz holda, biror chiqish so‘zi mos kelsin. Bu holda ko‘rsatilgan holatlarni barchasi mohiyatiga ko‘ra bir xil va har xil holatda turlicha belgilangan deb hisoblash mumkin. Bunday holatlarni bitta simvol bilan belgilab birlashtirish mumkin
Minimallashtirish bir nechta bosqichda olib boriladi. Holatlar sonini minimallashtiruvchi birinchi bosqichda chiqishlar va o‘tishlar jadvallari ko‘rib chiqiladi va ikkala jadvalning yuqori qatorida (dastlabki holatlar qatori) chiqishlar va o‘tishlar jadvallarida bir xil bo‘lgan ustunlarga mos keluvchi holatlar aniqlashtiriladi. Bu holatlar birlashtiriladi, ya’ni ikkala jadvalda aniqlashtirilgan holatlarning birortasiga mos keluvchi ustundan tashqari barcha bir xil ustunlar o‘chirib tashlanadi va holatlar jadvalining qolgan qismida barcha birlashtiriladigan holatlar bir xil simvol orqali belgilanadi. Bunday o‘zgartirishlar natijasida yana shunday holatlar paydo bo‘lishi mumkinki, ularga ikkala jadvalda ham bir xil ustunlar mos keladi.
Agar chiqishlar va o‘tishlar jadvallarida har xil dastlabki holatlarga mos keluvchi ustunlar chiziqchalar bo‘lganligi tufayli ustma-ust tushmasa, bunday ustunlarga mos keluvchi dastlabki holatlarni ham birlashtirish mumkin.
Birlashtirishning ikkinchi bosqichida barcha holatlar guruhlarga shunday birlashtiriladiki, xar bir guruhga kiruvchi holatlarga chiqish jadvalidagi bir xil ustunlar mos kelsin. Bunday har bir guruhga biror belgi mos qo‘yiladi. YOzuv quyidagicha amalga oshiriladi:

гуруҳлар символи
ҳолатлар символи

Har xil guruhlarga kiruvchi holatlarni birlashtirish mumkin emasligi aniq. Bir guruhga tegishli holatlarni birlashtirish imkoniyatlarini qo‘shimcha tekshirish zarur. Buning uchun har bir holat tagiga holatlar jadvalidan unga mos keluvchi ustun yozib boriladi, ammo bu ustundagi har bir holat o‘z simvoli bilan emas holat tegishli bo‘lgan guruh simvoli bilan belgilanadi. Bunday qayta belgilash natijasida holatlar jadvalining bir biri bilan mos tushmaydigan ustunlari bir biri bilan mos tushadigan guruhlar simvollari ustunlariga almashishi mumkin.

Misol. Mili avtomati 36-rasmda keltirilgan o‘tish va chiqish jadvallari bilan berilgan bo‘lsin. Bu avtomatning holatlar sonini minimallashtirishni amalga oshiraylik.
1-bosqich. CHiqish va o‘tish jadvalida ustunlari ustma-ust tushadigan holatlarni topamiz. Bunday holatlar a₃ va a₆. Almashtirish bajaramiz: a₃=a₆, ya’ni a₆ holatni o‘chiramiz (37-rasm).
2-bosqich. Holatlarni guruhlarga shunday ajratamizki, har bir guruhda chiqish jadvalining ustunlari mos keluvchi holatlar bo‘lsin a₁, a₄, a₅ - gr.1 (z₁); a₀, a₃ - gr. 2 (z₂).
Faqat bitta guruhga tegishli holatlar birlashtirilishi mumkin. Bunday holatlarni birlashtirish imkonini aniqlashtirish uchun bir guruhga tegishli holatlarni yozib chiqamiz, tagiga ustun shaklida o‘tish jadvalidagi holatlar belgisini guruh belgisi bilan almashtirib yozib chiqamiz. Bir xil ustunli holatlarni birlashtirish mumkin.

O‘tish jadvali CHiqish jadvali