Formal diLLƏr və avtomatlar nəZƏRİYYƏSİ

V.AVTOMATLAR NƏZƏRİYYƏSİ
5.1 Avtomat anlayışı.Avtomatların tipləri
Avtomat-bir çox çoxluqları təyin edən və bəzən də onları başqa çoxluqlara çevirən alqoritmdir.Avtomatların formal olmayan təsviri aşağıdakı kimidir:avtomatın giriş lenti vəziyyətlərin nömrəsini yadda saxlayan sonlu yaddaşlı idarəedici qurğusu var,

həm də köməkçi (işçi) və çıxış lenti ola bilər.

Avtomatlar iki tip olur:

1. 
   Müəyyən edən – çıxışsız avtomatlar,hansılar ki,giriş zəncirinin verilmiş L çoxluğunun aid olub-olmadığını təyin edir;
   
2. 
   Çevirici - x ∈ L şərti daxilində x giriş zəncirini y zəncirinə çevirən çıxışlı avtomat.
   

Giriş lentini xanaların xətti ardıcıllıqla düzülməsi kimi baxmaq olar.Hər bir xanada sonlu giriş əlifbasının bir simvolu saxlanılır.Avtomatın lenti sonsuzdur, amma orada hər bir anda sonlu sayda xanalar məşğul olur.Xanaların tutulmuş sahəsinin sağında və solunda xüsusi sonlu markerlər ola bilər.Marker lentin yalnız bir ucunda ola bilər ya da heç ola bilməz.

Giriş başlığı istənilən vaxt giriş lentinin yalnız bir xanasını oxuya bilər.Avtomatın işinin bir taktı vaxtı giriş başlığı 1 xana sağa sürüşə bilər ya da öz yerində qala bilər.Bu zaman o təkcə oxuma əməliyyatını yerinə yetirir,yəni avtomatın iş vaxtı giriş lentinin xanalarındakı simvollar dəyişməyəcək.

İşçi lent- informasiyanı yadda saxlayan köməkçi tutumdur (anbardır). Verilənləri ondan avtomat vasitəsilə oxumaq və ya oraya yazmaq olar.

İdarəedici qurğu-avtomatın hərəkətini idarə edən proqramdır.

Avtomat işçi taktların ardıcıllıqla yerinə yetirməklə işləyir.Taktın əvvəlində giriş simvolu oxunur və işçi lentdəki informasiya araşdırılır.Sonra , oxunan informasiyadan və cari vəziyyətdən asılı olaraq avtomatın hərəkəti təyin edilir:

1)Giriş başlığı sağa sürüşür və ya yerində qalır;

2)İşçi lentə hər hansı bir informasiya yazılır;

3)İdarəedici qurğunun vəziyyəti dəyişir;

4)çıxış lentinə (əgər o varsa) simvol yazılır.

Avtomatın hərəkətini avtomatın konfiqurasiya terminləri ilə təsvir etmək daha əlverişlidir:

1. 
   idarəedici qurğunun vəziyyəti;
   
2. 
   giriş başlığının vəziyyətinə uyğun giriş lentinin məzmunu;
   
3. 
   işçi başlığın vəziyyətilə işçi lentin məzmunu;
   
4. 
   çıxış lentinin məzmunu,əgər o varsa.
   

Avtomatların aşağıdakı tip növləri var:

1)Tyurinq maşını;

2)xətti-məhdudlayıcı avtomat;

3)maqazin yaddaşlı avtomat;

4)sonlu avtomat.
İşçi lentin mürəkkəbliyi avtomatın mürəkkəbliyini təyin edir.Məsələn,

1)Tyurinq maşını hər iki tərəfə uzadılmış sonsuz lentə malikdir;

2)Xətti-məhdudlayıcı avtomatda işçi lentin uzunluğu xətti funksiyanın giriş zəncirinin uzunluğu ilə təyin edilir;

3)Maqazin yaddaşlı avtomatda işçi lent LİFO maqazinin prinsipi ilə işləyir;

4)Sonlu avtomatda işçi lent yoxdur.