540
Z
0
1
1
0
0
0
Bu jadvalni tahlil qilishdan ko‘rinadiki, o‘zgaruvchilarning 1, 3, 5 taktlardagi
X
1
= 0 va
X
2
= 0 kirish kombinasiyasiga chiqish kattaligining
mos ravishda turli
qiymatlari
Z
= 0, 1, 0 mos keladi. Bu hol ko‘targichni boshqarish tizimini amalga
oshirish uchun kombinasion sxemani qo‘llab bo‘lmasligidan dalolat beradi.
Keltirilgan misoldan, kirish o‘zgaruvchilarining ayni bir kombinasiyasiga chiqish
kattaligining turli xil qiymatlari mos keladigan barcha hollarda boshqa matematik
apparatni qo‘llash, xususan chekli avtomatlar nazariyasini qo‘llash zarurligi kelib
chiqadi.
CHekli avtomatlar nazariyasining asosiy tushunchalarini kiritamiz.
Bizning
fikrimizcha, hamma diskret modellarni chekli avtomatlar deb atagan maqsadga
muvofiq. Ular o‘z navbatida xotirasiz (yoki kombinasion) chekli avtomatlarga va
xotirali (yoki izchil) chekli avtomatlarga bo‘linishi mumkin. Oldinroq biz asosiy
tushunchalarni kiritdik va xotirasiz (kombinasion) chekli avtomatlarni sintez
qilishning ba’zi masalalarini qarab chiqdik. Bu erda biz xotirali chekli avtomatlarni
qarab chiqamiz. SHuni aytib o‘tish zarurki, «chekli avtomat»
atamasi aniq, texnik
qo‘rilmani anglatmaydi, balki matematik ABTtraksiya hisoblanadi (diskret ta’sir
ko‘rsatish tizimlarida real hodisalarni aks ettiruvchi haqiqiylikning ma’lum
darajadagi matematik modeli).
CHekli avtomatlar nazariyasining ikki modeli farq qilinadi: ABTtrakt
(mavhum) va strukturali. Ayni bir ABTtrakt chekli avtomatga bir nechta strukturali
chekli avtomat mos kelishi mumkin.
Xotirali chekli avtomatni bundan keyin oddiygina chekli avtomat deb, xotirasiz
avtomatlarni esa kombinasion avtomatlar deb ataymiz. SHuningdek, hamma kirish va
chiqish o‘zgaruvchilari chekli to‘plamda qiymat qabul qiladi, deb hisoblaymiz.
Aslida chekli avtomtalarning umumiy nazariyasi to‘plam
elementlari qiymatini
cheklamasada, amaliy natijalar faqat ikki xonali mantiq uchun olinganini ta’kidlab
o‘tish kerak.
CHekli avtomat kirishiga so‘zlar deb ataluvchi ikkili kombinasiyalar
PDF created with pdfFactory Pro trial version
www.pdffactory.com
541
ko‘rinishidagi axborot uzatiladi. To‘plam alifbo deb ataladi, uning 0 va 1 elementlari
esa harflar deyiladi. Harflarning chekli tartibli ketma-ketligi so‘zni tashkil etadi.
Ravshanki, kiruvchi va chiquvchi so‘zlar mavjud. Bu holda diskret axborotning
ixtiyoriy shakl almashtirishi kiruvchi so‘zlar to‘plami
f
ning chiquvchi so‘zlar
to‘plamiga bir qiymatli akslanishi sifatida ifodalanib, bunda, kiruvchi va chiquvchi
so‘zlar to‘plamlari, odatda, hamma so‘zlar to‘plamining qism to‘plami bo‘ladi.
Istagan chekli avtomat bir qiymatli akslantirishni amalga oshiradi.
CHekli avtomatni ta’riflaymiz. CHekli avtomat diskret dinamik tizim bo‘lgani
uchun u turli vaqtda turli xil chekli holatlarda bo‘lishi mumkin. Ularni avtomatning
holati
deb ataymiz va
y(t)
orqali belgilaymiz. CHekli avtomat – bu diskret tizim
bo‘lib, uning mazkur paytdagi holatlari va chiqishlari quyidagi tenglamalar bilan
tavsiflanadi:
(19.19)
yoki
(19.20)
(19.20) Bu erda,
t
- diskret vaqt (t = 0, 1, 2 . . .).
(19.19) tenglamalar tizimi bilan tavsiflanuvchi avtomatlar Mil avtomatlari
deyilsa, (19.20) tenglamalar tizimlari bilan tavsiflanuvchilari Murning muntazam
avtomatlari deyiladi. Mil va Mur avtomatlari orasidagi asosiy farq chiqishlar
funksiyalarini aniqlashdan iborat bo‘lib,
ayni paytda ularning holatlari, funksiyalari
bir-biriga o‘xshashdir. Mur avtomatlarida chiqishlar avtomatning holati bilangina
aniqlanadi.
SHunday qilib, chekli avtomat kirish so‘zlari va holatlari to‘plamlarini holatlar
va chiqish so‘zlari to‘plamiga bir qiymatli akslantiradi. Ravshanki, holatlar to‘plami
ham ikkili so‘z ko‘rinishida ifodalanishi mumkin. CHekli alifbo va holatlar sonida
aniqlangan so‘zlar to‘plamida ifodalangan (berilgan) avtomat akslanishlar chekli
avtomati deyiladi.
[
]
[
]
[
]
[ ]
.
)
(
)
(
)
(
),
1
(
)
(
)
(
),
1
(
)
(
)
(
)
,
1
(
)
(
t
y
t
z
t
t
y
t
y
t
t
y
t
z
t
t
y
t
y
ψ
ρ
ϕ
ρ
ψ
ρ
ϕ
=
−
=
−
=
−
=
PDF created with pdfFactory Pro trial version
www.pdffactory.com
542
Avtomatni ifodalashning uchta usuli mavjud: analitik,
jadvalli va geometrik
usullar.
Analitik ifodalash usulini qarab chiqamiz. Agar quyidagi ob’ektlar ma’lum
bo‘lsa, ya’ni kiruvchi so‘zlar to‘plami
X,
chiquvchi so‘zlar to‘plami
Z
, holatlarning
chekli holati
u
, element
u
1
(boshlang‘ich holat deb aytiladi) va U to‘plamni o‘ziga
akslantirish (istagan
u
∈
u ga va kiruvchi so‘z
r
∈
X
ga
y
i
∈
U
holatlar va chiqish
so‘zi
u
∈
U moc qo‘yiladi) ma’lum bo‘lsa, chekli avtomat berilgan deyiladi. Bu usul
ancha qo‘pol, chunki (kiruvchi va chiquvchi alifbolarni berishdan tashqari)
akslantirishlarni chiqish so‘zlarini kiruvchi so‘zlar va holatlarining mumkin bo‘lgan
hamma birikmalariga moslashtirish jadvali ko‘rinishida ifodalash zarur.
Ifodalashning ancha ixcham shakli jadval shaklidir. Bu holda chekli avtomat
o‘tishlar va chiqishlar jadvallari ko‘rinishida ifodalanadi.
O‘tishlar jadvalida
ustunlar avtomat holatlariga, satrlar esa kirishlarga mos
keladi. Tegishli satr va ustunning kesishgan joyida avtomatning kirish ta’sirida
avvaligi holatidan o‘tish holati yoziladi.
O‘tishlar jadvalining tuzilishini o‘tishlar va chiqishlar jadvalari misolida
tushuntiramiz. Faraz qilaylik, avtomat
1
y
holatda bo‘lsin,
1
ρ
kirish ta’sirida u
2
y
holatga,
2
ρ
ta’sirida esa
1
y
holaatga o‘tadi.
2
y
holati uchun ham xuddi shunday.
CHiqishlar jadvalida ustunlar| avtomatning holatiga,
satrlar esa kirishlarga
mos keladi. Jadvalning o‘ziga esa chiqishlar yoziladi. Odatda, chiqishlar jadvali Mili
avtomati uchun yoziladi. Mir avtomati uchun u zarur emas, chunki chiqish
avtomatning holati bilan bir qiymatli aniqlanadi.
Do'stlaringiz bilan baham: