Ավտոմատների տեսություն

Ավտոմատների տեսությունը աբստրակտ մեքենաների և ավտոմատների, ինչպես նաև դրանց միջոցով լուծվող հաշվողական խնդիրների ուսումնասիրությունն է։ Այն տեսություն է համակարգչային գիտության մեջ Ավտոմատ բառն առաջացել է հունարեն αὐτόματος բառից, որը նշանակում է «ինքնագործող, ինքնակամ, ինքնաշարժ»։ Ավտոմատը աբստրակտ ինքնագնաց հաշվողական սարք է, որն ավտոմատ կերպով հետևում է նախապես տրված գործողությունների հաջորդականությանը։ Վերջավոր թվով վիճակներով ավտոմատը կոչվում է վերջավոր ավտոմատ (FA) կամ վերջավոր վիճակի մեքենա (FSM): Աջ կողմի նկարը պատկերում է վերջավոր վիճակի մեքենա, որը ավտոմատների հայտնի տեսակ է։ Այս ավտոմատը բաղկացած է վիճակներից (նկարում ներկայացված են շրջանակներով) և անցումներից (ներկայացված են սլաքներով)։ Քանի որ ավտոմատը տեսնում է մուտքագրման խորհրդանիշը, այն անցում է կատարում (կամ ցատկում) մեկ այլ վիճակի, ըստ իր անցումային ֆունկցիայի, որն իր արգումենտ է ընդունում նախորդ վիճակն ու ընթացիկ մուտքագրման նշանը։

Այս վիճակի դիագրամով-ով նկարագրված ավտոմատը սկսվում է S₁ վիճակից և փոխում է վիճակը՝ հետևելով 0 կամ 1 նշված սլաքներին՝ համաձայն մուտքային նշանների, երբ նրանք հասնում են: Կրկնակի շրջանագիծը նշում է S₁ որպես ընդունող վիճակ: Քանի որ S₁-ից դեպի իրեն բոլոր ուղիները պարունակում են 0-ով նշված սլաքների զույգ թիվ, այս ավտոմատն ընդունում է 0-ների զույգ թվեր պարունակող տողեր:.

Աոմատների տեսությունը սերտորեն կապված է ֆորմալ լեզուների տեսության հետ։ Այս համատեքստում ավտոմատներն օգտագործվում են որպես ֆորմալ լեզուների վերջավոր ներկայացումներ, որոնք կարող են անվերջ լինել։ Ավտոմատները մեծ դեր են խաղում հաշվարկների տեսության, կոմպիլյատորների կառուցման, արհեստական ինտելեկտի, սինտաքսիկ վերլուծության և ֆորմալ ստուգման մեջ։

Պատմություն խմբագրել

Աբստրակտ ավտոմատների տեսությունը զարգացել է 20-րդ դարի կեսերին՝ կապված վերջավոր ավտոմատների հետ^[1]։ Ավտոմատների տեսությունը սկզբում դիտարկվում էր դիսկրետ-պարամետրային համակարգերի վարքն ուաումնասիրող մաթեմատիկական համակարգերի տեսության ճյուղ։ Ավտոմատների տեսության վաղ աշխատանքները տարբերվում էին համակարգերի վերաբերյալ նախորդ աշխատանքներից նրանով, որ ինֆորմացիոն համակարգերը նկարագրելու համար օգտվում էին աբստրակտ հանրահաշվից, այլ ոչ թե դիֆերենցիալ հաշիվը նյութական համակարգերը նկարագրելու համար^[2]։ Վերջնավոր ավտոմատների տեսությունը մշակվել է տարբեր հետազոտական համայնքների կողմից, տարբեր անվանումներով^[3]։ Թյուրինգի մեքենայի ավելի վաղ գաղափարը նույնպես ներառված էր այս ճյուղի մեջ՝ անվերջ վիճակներով ավտոմատների նոր ձևերի հետ միասին, ինչպիսիք են մագազինով ավտոմատները:.

1956 թվականին լույս տեսավ Ավտոմատների ուսումնասիրություն գիրքը, որը հավաքագրել էր այնպիսի գիտնականների աշխատանքները, ինչպիսիք են՝ Կլոդ Շենոնը, Վ. Ռոս Էշբին, Ջոն ֆոն Նեյմանը, Մարվին Մինսկին, Էդվարդ Ֆ. Մուրը և Սթիվեն Քոլ Քլինը^[4]։ Այս հատորի հրատարակմամբ «ավտոմատների տեսությունը դարձավ համեմատաբար ինքնավար ճյուղ»^[5] Գիրքը ներառում էր ռեգուլյար պատահարների կամ ռեգուլյար լեզուների հավաքածուի վերաբերյալ Քլինիի նկարագրությունը և Շենոնի կողմից Թյուրինգի մեքենայի ծրագրերում բարդության համեմատաբար կայուն չափման մասին^[6]։ Միևնույն տարում Նոամ Չոմսկին նկարագրեց Չոմսկու հիերարխիան՝ ավտոմատների և ֆորմալ քերականությունների միջև համապատասխանությունը^[7], իսկ Ռոս Էշբին հրատարակեց «Կիբեռնետիկայի ներածություն»՝ մատչելի դասագիրք, որը ավտոմատները և տեղեկատվությունը բացատրում է օգտագործելով բազմությունների տեսությունը։

Ավտոմատ խմբագրել

Ոչ ֆորմալ նկարագրություն խմբագրել

Ավտոմատն աշխատում է, երբ նրան դիսկրետ ժամանակային քայլերով տրվում է մուտքերի որոշակի հաջորդականություն։ Ավտոմատը մշակում է նշանների և տառերի բազմությունից, որը կոչվում է մուտքային այբուբեն, ընտրված մեկ մուտք, Ավտոմատի մուտքին տրված նշանների հաջորդականությունները կոչվում են բառեր։ Ավտոմատն ունի վիճակների բազմություն. Ավտոմատի աշխատանքի ընթացքում յուրաքանչյուր պահի ավտոմատը գտնվում է իր վիճակներից մեկում։ Երբ ավտոմատը նոր մուտք է ստանում, այն անցնում է այլ վիճակի, համաձայն անցումային ֆունկցիայի, որի պարամետրերն են նախորդ վիճակն ու ընթացիկ մուտքագրված նշանը։ Միևնույն ժամանակ, մեկ այլ ֆունկցիա, որը կոչվում է ելքային, ըստ նախորդ վիճակի և ընթացիկ մուտքի։ Դուրս է բերում է ելքային այբուբենից սիմվոլներ։ Ավտոմատը կարդում է մուտքագրված բառի նշանները և անցում է կատարում վիճակների միջև, մինչև բառը ամբողջությամբ կարդացվի, եթե այն ունի վերջավոր երկարություն, և այդ պահին ավտոմատը կանգ է առնում։ Այն վիճակը, երբ ավտոմատը կանգ է առնում, կոչվում է վերջնական վիճակ։

Որպեսզի հետազոտել ֆորմալ լեզուների տեսություն օգտագործող ավտոմոտի ավտոմատի հնարավոր վիճակի/մուտքի/ելքի հաջորդականությունները մեքենային կարող է վերագրվել մեկնարկային վիճակ և ընդունվող վիճակների հավաքածու։ Այնուհետ, կախված նրանից, թե մեկնարկային վիճակից սկսվող աշխատանքը ավարտվում է ավտոմատի ընդունելի վիճակում, կարող է ասել, որ ավտոմատը ընդունում կամ մերժում է մուտքի հաջորդականությունը։ Ավտոմատի կողմից ընդունելի բոլոր բառերի բազմությունը կոչվում է ավտոմատի կողմից ընդունելի կամ ճանաչելի լեզու։ . Լեզուն ճանաչող մեքենայի ծանոթ օրինակ է էլեկտրոնային կողպեքը, որն ընդունում կամ մերժում է կոդը մուտքագրելու փորձերը։

Ֆորմալ սահմանում խմբագրել

Ավտոմատ

Ավտոմատը ֆորմալ կարող է ներկայացվել հնգյակով

M=\langle \Sigma ,\Gamma ,Q,\delta ,\lambda \rangle

, որտեղ։

$\Sigma$ -ն սիմվոլների վրջավոր բազմություն է՝ ավտոմտի մուտքի այբուբեն,
$\Gamma$ -ն սիմվոլների մեկ այլ բազմություն է՝ ավտոմատի ելքի այբուբեն,
$Q$ -ն վիճակների բազմություն է,
$\delta$ -ն հաջորդ վիճակի ֆունկցիան է կամ անցումային ֆունկցիան $\delta :Q\times \Sigma \to Q$ վիճակ-մուտք զույգերի համապատասխանեցումը հաջորդ վիճակներին,
$\lambda$ -ն is the հաջորդ ելքային ֆունկցիան է $\lambda :Q\times \Sigma \to \Gamma$ վիճակ-ելք զույգերի համապատասխանեցումը ելքերին։

Եթե

Q

-ն վերջավոր է, ապա

M

վերջավոր ավտոմատ է^[5]։

Մուտքային բառ: Ավտոմատը կարդում է սիմվոլների վերջավոր շարք $a_{1}a_{2}...a_{n}$ , որտեղ $a_{i}\in \Sigma$ , որը կոչվում է մուտքային բառ. Բոլոր բառերի բազմությունը նշանակվում է $\Sigma ^{*}$ -ով։

Աշխատանքը: $q_{0},q_{1},...,q_{n}$ $q_{i}=\delta (q_{i-1},a_{i})$ , $0<i\leq n$ վիճակների հաջորդականությունը, որտեղ $q_{i}\in Q$ ավտոմատի աշխատանքն է $a_{1}a_{2}...a_{n}\in \Sigma ^{*}$ մուտքի վրա $q_{0}$ վիճակից սկսած։ Այլ կերպ ասած, ավտոմատը սկզբում գտնվում է $q_{0}$ սկզբնական վիճակում և ստանում է $a_{1}$ մուտքը։ Մուտքի հաջորդականության $a_{1}$ -ի և յուրաքանչյուր հաջորդ $a_{i}$ -ի դեպքում ավտոմատն ընտրում է $q_{i}$ վիճակը, համաձայն $\delta (q_{i-1},a_{i})$ անցման ֆունկցիայի, մինչև վերջին $a_{n}$ սիմվոլը կարդալը, մեքենան հասցնելով աշխատանքի $q_{n}$ վերջնական վիճակին։ Նման կերպ, յուրաքանչյուր քայլում ավտոմատը արձակում է ելքային նշան՝ ըստ ելքային ֆունկցիայի $\lambda (q_{i-1},a_{i})$ .

Երբ անցումային $\delta$ ֆունկցիան մուտքին ստանում է բոլոր բառերը, այն ինդուկտիվ ընդլայնվում է ${\overline {\delta }}:Q\times \Sigma ^{*}\to Q$ ։ $\varepsilon$ դատարկ տողի համար, ${\overline {\delta }}(q,\varepsilon )=q$ բոլոր վիճակների համար, իսկ $wa$ տողերի համար, որտեղ $a$ -ն վերջին սիմվոլն է և $w$ -ն տողի մնացած մասը (հավանական է դատարկ), ${\overline {\delta }}(q,wa)=\delta ({\overline {\delta }}(q,w),a)$ ^[8]։ Ելքային $\lambda$ ֆունկցիան կարող է ընդլայվել նույն կերպ՝ line\lambda(q,w)</math>, որը $w$ բառի վրա աշխատելիս տալիս է մեքենայի ամբողջական արդյունքը $q$ վիճակից սկսած։
Ընդունող

Ավտոմատը ֆորմալ լեզուների տեսությամբ ուսումնասիրելու համար ավտոմատը կարող է դիտարկվել որպես «ընդունող», որ փոխարինում է ելքային այբուբենը և

\Gamma

և

\lambda

ֆունկցիան հետևյալով

$q_{0}\in Q$ , տրված սկզբնական վիճակն է, իսկ
$F$ , a set of states of $Q$ վիճակների բազմություն է(այսինքն $F\subseteq Q$ ) որ կոչվում է ընդունելի վիճակներ.

Սա թույլ է տալիս սահմանել հետևյալը․

Ընդունելի բառ: $w=a_{1}a_{2}...a_{n}\in \Sigma ^{*}$ բառը ավտոմատի համար ընդունելի բառ է, եթե

${\overline {\delta }}(q_{0},w)\in F$ , that is, if after consuming the whole string $w$ եթե ամբողջ տողի վրա աշխատելուց հետո մեքենան գտնվում է ընդունելի վիճակում։

Ճանաչելի լեզու: Ավտոմատի կողմից ճանաչելի լեզուն $L\subseteq \Sigma ^{*}$ ավտոմատի կողմից ճանաչելի բոլոր բառերի բազմությունն է $L=\{w\in \Sigma ^{*}\ |\ {\overline {\delta }}(q_{0},w)\in F\}$ .^[9]

Ճանաչելի լեզուներ: Ճանաչելի լեզուները այն լեզուների բազմությունն է, որոնք ճանաչելի են որև ավտոմատի կողմից։ Վերջավոր ավտոմատի համար ճանաչելի լեզուները ռեգուլյար են։ Տարբեր տեսակի ավտոմատների համար ճանաչելի լեզուները տարբեր են։

Ծանոթագրություններ խմբագրել

↑ Mahoney, Michael S. «The Structures of Computation and the Mathematical Structure of Nature». The Rutherford Journal. Վերցված է 2020 թ․ հունիսի 7-ին.
↑ Booth, Taylor (1967). Sequential Machines and Automata Theory. New York: John Wiley & Sons. էջ 1-13. ISBN 0-471-08848-X.
↑ Ashby, William Ross (1967 թ․ հունվարի 15). «The Place of the Brain in the Natural World» (PDF). Currents in Modern Biology. 1 (2): 95–104. doi:10.1016/0303-2647(67)90021-4. PMID 6060865. Արխիվացված է օրիգինալից (PDF) 2023 թ․ հունիսի 4-ին. Վերցված է 2023 թ․ ապրիլի 21-ին.: "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."
↑ Ashby, W. R.; և այլք: (1956). C.E. Shannon; J. McCarthy (eds.). Automata Studies. Princeton, N.J.: Princeton University Press.
↑ ^5,0 ^5,1 Arbib, Michael (1969). Theories of Abstract Automata. Englewood Cliffs, N.J.: Prentice-Hall.
↑ Li, Ming; Paul, Vitanyi (1997). An Introduction to Kolmogorov Complexity and its Applications. New York: Springer-Verlag. էջ 84.
↑ Chomsky, Noam (1956). «Three models for the description of language» (PDF). IRE Transactions on Information Theory. 2 (3): 113–124. doi:10.1109/TIT.1956.1056813.
↑ Hartmanis, J.; Stearns, R.E. (1966). Algebraic Structure Theory of Sequential Machines. Englewood Cliffs, N.J.: Prentice-Hall.
↑ Moore, Cristopher (2019 թ․ հուլիսի 31). «Automata, languages, and grammars». arXiv:1907.12713 [cs.CC].

[1] Mahoney, Michael S. «The Structures of Computation and the Mathematical Structure of Nature». The Rutherford Journal. Վերցված է 2020 թ․ հունիսի 7-ին.

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

[3] Ashby, William Ross (1967 թ․ հունվարի 15). «The Place of the Brain in the Natural World» (PDF). Currents in Modern Biology. 1 (2): 95–104. doi:10.1016/0303-2647(67)90021-4. PMID 6060865. Արխիվացված է օրիգինալից (PDF) 2023 թ․ հունիսի 4-ին. Վերցված է 2023 թ․ ապրիլի 21-ին.: "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."

[4] Ashby, W. R.; և այլք: (1956). C.E. Shannon; J. McCarthy (eds.). Automata Studies. Princeton, N.J.: Princeton University Press.

[Arbib_1969-5] 5,0 ^5,1 Arbib, Michael (1969). Theories of Abstract Automata. Englewood Cliffs, N.J.: Prentice-Hall.

[6] Li, Ming; Paul, Vitanyi (1997). An Introduction to Kolmogorov Complexity and its Applications. New York: Springer-Verlag. էջ 84.

[7] Chomsky, Noam (1956). «Three models for the description of language» (PDF). IRE Transactions on Information Theory. 2 (3): 113–124. doi:10.1109/TIT.1956.1056813.

[structure_theory-8] Hartmanis, J.; Stearns, R.E. (1966). Algebraic Structure Theory of Sequential Machines. Englewood Cliffs, N.J.: Prentice-Hall.

[9] Moore, Cristopher (2019 թ․ հուլիսի 31). «Automata, languages, and grammars». arXiv:1907.12713 [cs.CC].

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]