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

[thumb|300px| Այս [վիճակի դիագրամով-ով նկարագրված ավտոմատը սկսվում է S1 վիճակից և փոխում է վիճակը՝ հետևելով 0 կամ 1 նշված սլաքներին՝ համաձայն մուտքային նշանների, երբ նրանք հասնում են: Կրկնակի շրջանագիծը նշում է S1 որպես ընդունող վիճակ: Քանի որ S1-ից դեպի իրեն բոլոր ուղիները պարունակում են 0-ով նշված սլաքների զույգ թիվ, այս ավտոմատն ընդունում է 0-ների զույգ թվեր պարունակող տողեր:.]]
Ավտոմատների տեսությունը աբստրակտ մեքենաների և ավտոմատների, ինչպես նաև դրանց միջոցով լուծվող հաշվողական խնդիրների ուսումնասիրությունն է։ Այն տեսություն է համակարգչային գիտության մեջ Ավտոմատ բառն առաջացել է հունարեն αὐτόματος բառից, որը նշանակում է «ինքնագործող, ինքնակամ, ինքնաշարժ»։ Ավտոմատը աբստրակտ ինքնագնաց հաշվողական սարք է, որն ավտոմատ կերպով հետևում է նախապես տրված գործողությունների հաջորդականությանը։ Վերջավոր թվով վիճակներով ավտոմատը կոչվում է վերջավոր ավտոմատ (FA) կամ վերջավոր վիճակի մեքենա (FSM): Աջ կողմի նկարը պատկերում է վերջավոր վիճակի մեքենա, որը ավտոմատների հայտնի տեսակ է։ Այս ավտոմատը բաղկացած է վիճակներից (նկարում ներկայացված են շրջանակներով) և անցումներից (ներկայացված են սլաքներով)։ Քանի որ ավտոմատը տեսնում է մուտքագրման խորհրդանիշը, այն անցում է կատարում (կամ ցատկում) մեկ այլ վիճակի, ըստ իր անցումային ֆունկցիայի, որն իր արգումենտ է ընդունում նախորդ վիճակն ու ընթացիկ մուտքագրման նշանը։

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

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

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

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

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

 : Ավտոմատը ֆորմալ կարող է ներկայացվել հնգյակով 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 վերջավոր ավտոմատ է։

;Մուտքային բառ
 : Ավտոմատը կարդում է սիմվոլների վերջավոր շարք a_1a_2...a_n, որտեղ a_i \in \Sigma, որը կոչվում է *մուտքային բառ*. Բոլոր բառերի բազմությունը նշանակվում է \Sigma^*-ով։

;Աշխատանքը
:q_0,q_1,...,q_n q_i = \delta(q_{i-1}, a_i), 0  վիճակների հաջորդականությունը, որտեղ q_i \in Q  ավտոմատի *աշխատանքն է* a_1a_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)։ Ելքային \lambda ֆունկցիան կարող է ընդլայվել նույն կերպ՝ line\lambda(q,w), որը w բառի վրա աշխատելիս տալիս է մեքենայի ամբողջական արդյունքը q վիճակից սկսած։
;Ընդունող

 : Ավտոմատը ֆորմալ լեզուների տեսությամբ ուսումնասիրելու համար ավտոմատը կարող է դիտարկվել որպես «ընդունող», որ փոխարինում է ելքային այբուբենը և \Gamma և \lambda ֆունկցիան հետևյալով
:* q_0 \in Q, տրված *սկզբնական վիճակն է*, իսկ
:* F, a set of states of Q վիճակների բազմություն է(այսինքն F \subseteq Q) որ կոչվում է *ընդունելի վիճակներ*. 
:Սա թույլ է տալիս սահմանել հետևյալը․

;Ընդունելի բառ
:w = a_1a_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\}.

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

## Ծանոթագրություններ

Կատեգորիա:Ինֆորմատիկա
Կատեգորիա:Հաշվողական լեզվաբանություն
Կատեգորիա:Մաթեմատիկական տրամաբանություն
Կատեգորիա:Տեսական ինֆորմատիկա
Կատեգորիա:Ֆորմալ լեզուներ