Avtomatlar nəzəriyyəsi

Avtomatlar nəzəriyyəsi — abstrakt maşınların və avtomatların, habelə onlardan istifadə etməklə həll edilə bilən hesablama problemlərinin öyrənilməsi. Bu, riyazi məntiqlə sıx əlaqəsi olan nəzəri kompüter elmində bir nəzəriyyədir. Avtomat sözü yunan sözü olan αὐτόματος sözündən yaranıb, "öz-özünə fəaliyyət göstərən, öz iradəsi ilə, öz-özünə hərəkət edən" deməkdir. Avtomat avtomatik olaraq əvvəlcədən müəyyən edilmiş əməliyyatlar ardıcıllığını izləyən abstrakt özüyeriyən hesablama cihazıdır. Sonlu sayda vəziyyətə malik avtomata Sonlu Avtomat (FA) və ya Sonlu Vəziyyət Maşını (FSM) deyilir. Sağdakı qrafik tanınmış avtomat növü olan sonlu vəziyyət maşınını təsvir edir. Bu avtomat vəziyyətdən (şəkildə dairələrlə təmsil olunur) və keçidlərdən (oxlarla təmsil olunur) ibarətdir. Avtomat giriş simvolunu gördükcə, əvvəlki vəziyyət və cari giriş simvolunu öz arqumentləri kimi qəbul edən keçid funksiyasına uyğun olaraq başqa vəziyyətə keçid (və ya sıçrayış) edir.

Avtomatlar nəzəriyyəsi formal dil nəzəriyyəsi ilə sıx bağlıdır. Bu kontekstdə avtomatlar sonsuz ola bilən formal dillərin sonlu təmsilləri kimi istifadə olunur. Avtomatlar tez-tez tanıya biləcəkləri formal dillər sinfinə görə təsnif edilir, məsələn, əsas avtomat sinifləri arasında yuva əlaqəsini təsvir edən Çomski iyerarxiyasında. Avtomatlar hesablama nəzəriyyəsində, kompilyatorun qurulmasında, süni intellektdə, təhlildə və formal yoxlamada böyük rol oynayır.

 Tarixi 
Abstrakt avtomatlar nəzəriyyəsi XX əsrin ortalarında sonlu avtomatlarla bağlı işlənib hazırlanmışdır. Avtomatlar nəzəriyyəsi əvvəlcə diskret parametrli sistemlərin davranışını öyrənən riyazi sistemlər nəzəriyyəsinin bir qolu hesab olunurdu. Avtomatlar nəzəriyyəsindəki ilk iş material sistemlərini təsvir etmək üçün diferensial hesablamadan daha çox məlumat sistemlərini təsvir etmək üçün abstrakt cəbrdən istifadə etməklə sistemlər üzərində əvvəlki işlərdən fərqlənirdi. Sonlu vəziyyət çeviricisi nəzəriyyəsi müxtəlif araşdırma icmaları tərəfindən müxtəlif adlar altında işlənib hazırlanmışdır. Türinq maşınının əvvəlki konsepsiyası da aşağı itələyən avtomatlar kimi sonsuz vəziyyətli avtomatların yeni formaları ilə birlikdə bu fənnə daxil edilmişdir.

 İstinadlar 

 Əlavə ədəbiyyat 

  Part One: Automata and Languages, chapters 1–2, pp. 29–122. Section 4.1: Decidable Languages, pp. 152–159. Section 5.1: Undecidable Problems from Language Theory, pp. 172–183.




 John M. Howie (1991) Automata and Languages, Clarendon Press  






 Xarici keçidlər 
 dk.brics.automaton
 libfa

Kateqoriya:Avtomatlar (hesablama)