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.^[1] 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.^[2] 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.^[3] 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

↑ Mahoney, Michael S. "The Structures of Computation and the Mathematical Structure of Nature". The Rutherford Journal. 27 May 2020 tarixində arxivləşdirilib. İ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. "The Place of the Brain in the Natural World" (PDF). Currents in Modern Biology. 1 (2). January 15, 1967: 95–104. doi:10.1016/0303-2647(67)90021-4. PMID 6060865. 2023-06-04 tarixində orijinalından (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

John E. Hopcroft; Rajeev Motwani; Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation (2nd). Pearson Education. 2000. ISBN 978-0-201-44124-6.
Michael Sipser. Introduction to the Theory of Computation. 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.
Elaine Rich. Automata, Computability and Complexity: Theory and Applications. Pearson. 2008. ISBN 978-0-13-228806-4.
Salomaa, Arto. Computation and automata. Encyclopedia of Mathematics and Its Applications. 25. Cambridge University Press. 1985. ISBN 978-0-521-30245-6. Zbl 0565.68046.
Anderson, James A. Automata theory with modern applications. With contributions by Tom Head. Cambridge: Cambridge University Press. 2006. ISBN 978-0-521-61324-8. Zbl 1127.68049.
Conway, J.H. Regular algebra and finite machines. Chapman and Hall Mathematics Series. London: Chapman & Hall. 1971. Zbl 0231.94041.
John M. Howie (1991) Automata and Languages, Clarendon Press ISBN 0-19-853424-8 Şablon:Mr
Sakarovitch, Jacques. Elements of automata theory. Translated from the French by Reuben Thomas. Cambridge University Press. 2009. ISBN 978-0-521-84425-3. Zbl 1188.68177.
James P. Schmeiser; David T. Barnard. Producing a top-down parse order with bottom-up parsing. Elsevier North-Holland. 1995.
Igor Aleksander; F. Keith Hanna. Automata Theory: An Engineering Approach. New York: Crane Russak. 1975. ISBN 978-0-8448-0657-0.
Marvin Minsky. Computation: Finite and infinite machines. Princeton, N.J.: Prentice Hall. 1967.
John C. Martin. Introduction to Languages and The Theory of Computation. New York: McGraw Hill. 2011. ISBN 978-0-07-319146-1.

Xarici keçidlər

[1] Mahoney, Michael S. "The Structures of Computation and the Mathematical Structure of Nature". The Rutherford Journal. 27 May 2020 tarixində arxivləşdirilib. İstifadə tarixi: 7 June 2020.

[2] Booth, Taylor. Sequential Machines and Automata Theory. New York: John Wiley & Sons. 1967. səh. 1-13. ISBN 0-471-08848-X.

[3] Ashby, William Ross. "The Place of the Brain in the Natural World" (PDF). Currents in Modern Biology. 1 (2). January 15, 1967: 95–104. doi:10.1016/0303-2647(67)90021-4. PMID 6060865. 2023-06-04 tarixində orijinalından (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.

[1]

[2]

[3]