Ajratkichlar va ajratish masalasi. Ajratkichlarning ko‘rinishlari. Chekli avtomatlar

MUSTAQIL ISHI 2

2022

1 Ajratkichlar va ajratish masalasi. Ajratkichlarning ko‘rinishlari. Chekli avtomatlar.
5.7.CHekIi avtomatlar
CHekli avtomat - bu qandaydir tilni qatorlarini anglash uchun qurilmadir.
Uning tarkibida chekli holatlar to’plami bor bo’lib, ulaming ba'zilari oxirgilari deb
ataladi. Har bir literaning o’qilishi davomida nazorat qatori holatdan holatga
berilgan o’tishlar to’plamiga mos ravishda uzatiladi. Agar qatoming oxirgi
literasini o’qiganidan so’ng avtomat oxirgi holatlardan btrida bo’lsa, qator haqida,
u avtomat bilan qabul qilingan tilga tegishli deb aytiladi. Boshqa hollarda qator
avtomat bilan qabul qilingan tilga tegishli emasdir.
CHekli avtomat formal ravishda quyidagi beshta xarakteristika bilan
aniqlanadi:
- (K) holatlaming chekli to’plami
- (E ) chekli kirish alfaviti
__- (5 ) o’tishlar to’plami _____________________________________ _
- (S0 € K ) boshlang’ich holat
- ( f e K) oxirgi holatlar to’plami
M = (K, X, 5, S0, f ).
96
Misoi: Avtomatning holatlari A va V, kiruvchi alfavit {0,l},boshlang’ich
xolati -A , oxirgi holatlar to’plami -{A}, o’tishlar

(A,0 ) = A, (A ,l) = V,

(V,0)=V (V,1)=A

Bu o’tishlar A holatda 0 ni o’qishda boshqaruv A holatga uzatilishini
anglatadi va x.k. 0 1 0 0 1 0 1 1 qatomi o’qishda boshqaruv ketma-ket ravishda
quyidagi tartibda uzatiladi: A,A,V,V,V,A,A,V,A
A so’nggi holat bo’Igani uchun qator chekli avtomat tomonidan qabul
qilinadi, Iekin 0 0 1 1 1 qatomi o’qishda avtomat quyidagi holatlar orqali o’tadi
A,A,A,V,A,V.
V oxirgi holat bo’lmaganligi sababli, bu qator qabul qilinmaydi, ya'ni bu
qator ushbu avtomat qabul qiladigan tilga tegishli emas. SHu sababli, nullar
avtomatning holatiga ta'sir ko’rsatmaydi, har bir 1 esa uning holatini A dan V ga
V dan A ga va boshlang’ich holat esa oxirgi holatdek bo’ladi, ya'ni avtomat bilan
qabul qilingan til juft birlar soniga ega qatorlardan tuzilgan.
O’tishlami quyidagi jad val (3-jadval) orqali va chizma ko’rinishini (2 0 -~ :^
rasm) tasawur qilish mumkin.