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 . 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. ə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
- Mahoney, Michael S. . The Rutherford Journal. 27 May 2020 tarixində . İstifadə tarixi: 7 June 2020.
- Booth, Taylor. Sequential Machines and Automata Theory. New York: John Wiley & Sons. 1967. səh. 1-13. ISBN 0-471-08848-X.
-
Ashby, William Ross. (PDF). Currents in Modern Biology. 1 (2). January 15, 1967: 95–104. doi:. PMID . 2023-06-04 tarixində (PDF) arxivləşdirilib. İstifadə tarixi: 2021-03-29.
The theories, now well developed, of the "finite-state machine" (Gill, 1962), of the "noiseless transducer" (Shannon and Weaver, 1949), of the "state-determined system" (Ashby, 1952), and of the "sequential circuit", are essentially homologous.
Əlavə ədəbiyyat
- ; ; . (2nd). Pearson Education. 2000. ISBN 978-0-201-44124-6.
- . . PWS Publishing. 1997. ISBN 978-0-534-94728-6. 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.
- . . Pearson. 2008. ISBN 978-0-13-228806-4.
- . . Encyclopedia of Mathematics and Its Applications. 25. Cambridge University Press. 1985. ISBN 978-0-521-30245-6. .
- Anderson, James A. Automata theory with modern applications. With contributions by Tom Head. Cambridge: Cambridge University Press. 2006. ISBN 978-0-521-61324-8. .
- Regular algebra and finite machines. Chapman and Hall Mathematics Series. London: . 1971. .
- (1991) Automata and Languages, ISBN 0-19-853424-8
- Sakarovitch, Jacques. Elements of automata theory. Translated from the French by Reuben Thomas. Cambridge University Press. 2009. ISBN 978-0-521-84425-3. .
- ; . Producing a top-down parse order with bottom-up parsing. Elsevier North-Holland. 1995.
- ; F. Keith Hanna. . New York: Crane Russak. 1975. ISBN 978-0-8448-0657-0.
- . . Princeton, N.J.: Prentice Hall. 1967.
- John C. Martin. . New York: McGraw Hill. 2011. ISBN 978-0-07-319146-1.