Վերջավոր ավտոմատներ և դրանք սահմանելու եղանակներ: Ավտոմատա Հիմնական սահմանումները սահմանելու եղանակներ n Վերջնական: Ստանդարտ կամ ավտոմատ նկարագրության լեզուներ

Ինչպես ավելի վաղ ասվեց, Յ (x, q)սահմանում է մուտքային նշանների փոխակերպման կարգը և ավտոմատի վիճակը նախորդ ցիկլում հաջորդի վիճակի, a Q (x, q) -մուտքային նշանների և ավտոմատի վիճակի փոխակերպումը ընթացիկ ցիկլում ելքային խորհրդանիշի: Եթե ք 0-ը ավտոմատի սկզբնական վիճակն է, և ես- չափել համարը, ապա դրա աշխատանքը նկարագրվում է համակարգով.

Այս հարաբերակցությունները կոչվում են կանոնական հավասարումների համակարգերվերջավոր ավտոմատ. Դուք կարող եք օգտագործել դրանք q 0,հաջորդաբար գտնել ավտոմատի և ելքային նշանների բոլոր հետագա վիճակները:

Գոյություն ունեն երկու տեսակի մեքենաներ. սկզբնականև ոչ սկզբնական. ATսկզբնական ավտոմատներն ունեն ֆիքսված սկզբնական վիճակ (այսինքն՝ նրանք միշտ սկսում են նույն վիճակից q0).Ոչ սկզբնական ավտոմատներում՝ հավաքածուից որևէ մեկը Ք; այս ընտրությունը որոշում է ավտոմատի հետագա վարքագիծը:

Որոշակի վերջավոր ավտոմատի ներկայացումը իրականում կրճատվում է մինչև այն սահմանող ավտոմատի գործառույթների նկարագրությունը: Համակարգից (9.3) հետևում է, որ վերջավոր թվով հնարավոր ներքին վիճակների դեպքում ավտոմատ գործառույթների հնարավոր արժեքների թիվը նույնպես վերջավոր է ստացվում: Դրանք կարելի է նկարագրել տարբեր ձևերով, որոնցից ամենատարածվածն է աղյուսակայինև օգնությամբ դիագրամներ.

AT աղյուսակային ձևովԱվտոմատ ֆունկցիաները տրված են համապատասխանաբար անվանված երկու վերջավոր աղյուսակներով անցումային մատրիցաև ելքային մատրիցա.Այս աղյուսակներում տողերը նշվում են մուտքագրման այբուբենի տառերով, իսկ սյունակները՝ ներքին այբուբենի տառերով (ավտոմատի ներքին վիճակը կոդավորող խորհրդանիշներ)։ Անցումային մատրիցայում շարքի հատման կետում (xk)և սյունակ (qr)տեղադրված են Y ֆունկցիայի արժեքները ( q r, x k),ա Արդյունքների մատրիցում - Q ֆունկցիայի արժեքները (q r, x k):

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

Պլանավորում:

1. Ավտոմատ հասկացությունը, ավտոմատի շահագործման սկզբունքը

2. Վերջավոր ավտոմատների ճշտման մեթոդներ

3. Ավտոմատների տեսության ընդհանուր խնդիրներ

Տեսական տեղեկատվություն

Մարդը միշտ ձգտել է հեշտացնել իր աշխատանքը՝ առանց իր միջամտության իր համար որոշ մեխանիկական սարքեր աշխատելու միջոցով։ Սկզբում դրանք հեքիաթներ էին, հետո սկսեցին վերածվել սովորական բաների։ Ավտոմեքենաները, հեռուստացույցները, լվացքի մեքենաները, ամբողջ արտադրությունները գործում են առանց մարդու միջամտության։ Ավելին, մարդու միջամտությունը շատ դեպքերում չի պահանջվում, իսկ որոշ դեպքերում նման միջամտությունը կարող է հանգեցնել բացասական երեւույթների։ «Մեքենա» հասկացությունը՝ որպես որոշակի տիպի գործողություն կատարող սարք, վաղուց է այսպես մեկնաբանվել մարդկանց կողմից։

Ավտոմատ հասկացությունը, ավտոմատի շահագործման սկզբունքը

հայեցակարգ մեքենադիտարկվում է երկու տեսանկյունից.

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

2. Ավտոմատ - մաթեմատիկական հասկացությունցույց տալով իրական տեխնիկական սարքերի մաթեմատիկական մոդելը: Ավտոմատը վերացական սարք է, պարզ չէ, թե ինչու և ինչպես է այն աշխատում և, ընդհանրապես, ինչու կարող է աշխատել։ Այս առումով ավտոմատը «սև արկղ» է, որը տեսականորեն ունակ է որոշակի գործողություններ իրականացնել։ Մաթեմատիկայի տեսանկյունից բացարձակապես կարևոր չէ, թե ինչ, ինչպես և ինչու է առաջացնում որոշակի գործողություններ։

Ցանկացած ավտոմատ պետք է ունենա որոշակի քանակությամբ մուտքեր, որոշակի քանակությամբ ելքեր և որոշակի քանակությամբ ներքին վիճակներ:

Հանրահաշվային ավտոմատների տեսությունը տեսական կիբեռնետիկայի մի ճյուղ է, որն ուսումնասիրում է դիսկրետ ավտոմատները վերացական հանրահաշվական տեսանկյունից։

Ավտոմատների ընդհանուր տեսությունը պարունակում է տարբեր ենթաբաժիններ. Կախված ուսումնասիրության առարկայից՝ այն բաժանվում է ավտոմատների վերացական տեսության և ավտոմատների կառուցվածքային տեսության։

Վերացական ավտոմատների տեսությունուսումնասիրում է ավտոմատի կատարած անցումները, որոնց վրա ազդում են մուտքային ազդանշանները, ինչպես նաև այդ անցումների արդյունքում ելքային ազդանշանները։

Ուսումնասիրության առարկա կառուցվածքայինԱվտոմատների տեսությունը ավտոմատի կառուցվածքն է, ինչպես նաև մուտքային և ելքային ազդանշանների կառուցվածքը, օրինակ՝ մուտքային և ելքային ազդանշանների կոդավորման մեթոդները և այլն։

Պետական ​​մեքենաների սահմանում

Մեքենա- սարքի վերացական մոդել, որն աշխատում է դիսկրետ ժամանակում, որը մշակում է մուտքային ազդանշանների վերջավոր հաջորդականություն և դրանք վերածում ելքային ազդանշանների (ռեակցիաների) վերջավոր հաջորդականության։

Վերջավոր ավտոմատի շահագործման գործընթացում նրա ներքին վիճակների վերջավոր թիվը հաջորդաբար փոխվում է, և ավտոմատի վիճակը որոշակի կետում եզակիորեն որոշվում է մուտքային և ելքային ազդանշաններով: Նման ավտոմատները բոլոր ժամանակակից համակարգչային տեխնոլոգիաների և ավտոմատ կառավարման և կառավարման բոլոր տեսակի դիսկրետ համակարգերի հիմքն են:

Ավտոմատ հասկացությունն այնքան վերացական է, որ դժվար է ասել, թե երբ է մարդը դա անում ընդհանրապես առանց ավտոմատների: Ավտոմատի սահմանման համար հարմար են ցանկացած սարք, ներառյալ նրանք, որոնցով պարզունակ մարդիկ որս էին անում կամ քարեր էին նետում՝ պաշտպանելով իրենց տունը թշնամուց:

Ալգորիթմ- հասկանալի և ճշգրիտ պաշտոնական հրահանգ կատարողին, որը միանշանակորեն որոշում է գործողությունների բովանդակությունը և հաջորդականությունը, որոնք թարգմանում են տվյալ սկզբնական տվյալների հավաքածուն ցանկալի արդյունքի

Ենթադրվում է, որ մարդու կողմից ստեղծված առաջին ծրագրային սարքը եղել է ժամացույցը: Ժամացույցի մեխանիզմները շարժակների և խցիկի մեխանիզմների, շարժակների և լծակների օգնությամբ զսպանակի օգնությամբ կատարում են մի շարք կոնկրետ գործողություններ: Ժամացույցի նման մեխանիզմի օրինակ է Մոսկվայի Կենտրոնական տիկնիկային թատրոնի հայտնի ժամացույցը, որտեղ շարժման մեջ է դրվում թվատախտակի վրա տեղադրված տասներկու հեքիաթային կերպարներ:

Նշենք մի քանի հետաքրքիր պատմական փաստեր՝ կապված ավտոմատների՝ որպես մեխանիկական սարքերի հետ։

1. Գերմանացի փիլիսոփա և ալքիմիկոս Ալբերտ Մեծը 1216-1246 թվականներին ստեղծել է «երկաթյա» սպասավոր՝ ավտոմատ, որը տան մեջ կատարում էր դարպասապահի պարտականությունները:

2. Աստղագետ Յոհան Մյուլլերը (Regiamontanus) (1436-1476) ստեղծել է մեխանիկական արծիվ, որը ողջունել է Սուրբ Հռոմի կայսր Մաքսիմիլիան II-ի Նյուրնբերգի մուտքը գլխի թեքմամբ և թեւերի շարժումով:

3. Մեխանիկ Ժակ դե Վականսոն (1709-1782) - աշխարհում առաջին ավտոմատ ջուլհակի հեղինակը։ Նա կերտել է մեխանիկական բադի կերպարը, իր կենդանի գործընկերոջ ճշգրիտ պատճենը՝ լողացել է, մաքրել փետուրները, ափից հատիկներ է կուլ տվել։ Նրա մեխանիկական ֆլեյտահարը, որը կատարել է տասնմեկ երաժշտական ​​ստեղծագործություն, ապշեցրել է այդ հեռավոր տարիներին ապրած մարդկանց։

4. 19-րդ դարի ռուս գյուտարար. Ա.Մ.Գամուլեցկին ստեղծեց մի ամբողջ մեխանիկական կաբինետ, որում կային նրա կողմից նախագծված բազմաթիվ ավտոմատներ: Այստեղ, ի թիվս այլ բաների, կային կախարդի խոսող գլուխը և տավիղ նվագող Cupid-ը, ինչը ապշեցնում էր ժամանակակիցների երևակայությունը։

5. Առաջին պարզունակ ավելացման մեքենան նախագծվել է 1641 թվականին Բլեզ Պասկալի կողմից։ Բացման խթանը հոր տանջանքն էր՝ հարկը, տեսուչ, ով օր ու գիշեր աշխատում էր մեծ հաշվարկներով։ Հնարելով գումարող մեքենա՝ տասնութամյա որդին փրկեց հորը բարդ հաշվարկներից և աշխարհին տվեց թվեր գումարող և հանող առաջին հաշվիչը։

6. Առաջին շախմատային մեքենան կառուցվել է 1890 թվականին իսպանացի ինժեներ Տորես Կեվեդոյի կողմից։ Այդպիսի ավտոմատը կարող էր խաղալ միայն ռոքի վերջնախաղ (թագավորը և թագը թագավորի դեմ):

7. Ավտոմատ կառավարմամբ առաջին համակարգիչը ստեղծվել է Չարլզ Բեբիջի կողմից 1822 թվականին, նա նախագծել է ավելացնող մեքենա, որն ուներ հիշողության և թվաբանական սարքեր։ Այս սարքերը դարձան ժամանակակից համակարգիչների նմանատիպ սարքերի նախատիպերը:

Մեքենաների տեսակները.

Մեքենան կարելի է մեկնաբանել որպեսսարք, որն իրականացնում է էներգիայի, նյութերի կամ տեղեկատվության ստացման, փոխակերպման և փոխանցման գործընթացները դրանցում սահմանված ծրագրին համապատասխան, բայց առանց անձի անմիջական մասնակցության։

Յուրաքանչյուր մեքենա ունի իր սեփականը բազայի հավաքածուներ,որոնք ներառում են՝ մուտքային այբուբեն, ելքային այբուբեն, ավտոմատ վիճակների հավաքածու։

Վերջավոր ավտոմատի բնորոշ առանձնահատկությունն առկայությունն է հիշողություն,որը որոշում է ավտոմատի վիճակը՝ կախված ժամանակից։ Ավտոմատի տարբեր վիճակների արտաքին դրսևորումը նրա արձագանքն է նույն տեսակի ազդեցություններին (ազդանշաններին):

Վերջավոր թվային ավտոմատների շահագործման մեջ կարևոր հայեցակարգ է ժամանակ.

Ավտոմատները կարելի է դասակարգել ըստ տարբեր չափանիշների:

1. Ըստ գործունեության տեսակի - ավտոմատները բաժանվում են՝ տեղեկատվության, կառավարման և հաշվողական:

Դեպիտեղեկատվական մեքենաներներառում են տարբեր տեղեկատու աղյուսակներ, մարզադաշտերում տեղեկատվական տախտակներ, ազդանշանային սարքեր:

Դեպի հսկիչ մեքենաներընդունված է սարքեր վերագրել որոշակի գործընթաց կառավարելու համար, ներառյալ՝ վերելակ, փոխակրիչ, հաստոց, պատնեշ:

Դեպի հաշվողական մեքենաներներառում են միկրոհաշվիչներ, համակարգչային պրոցեսորներ և այլ սարքեր, որոնք կատարում են հաշվարկներ:

Այնուամենայնիվ, խստորեն ասած, շատ ավտոմատներ այնպիսի բարդ համակարգեր են, որ դրանք և՛ հաշվողական, և՛ կառավարման, և՛ տեղեկատվական ավտոմատներ են:

2. Վերջավոր ավտոմատներ -Ինֆորմատիկայի տեսանկյունից դրանք ավտոմատներ են, որոնք դիսկրետ տեղեկատվության փոխարկիչներ են։ Դրանք ներառում են փոխարկիչներ, որոնք պարունակում են մուտքային և վերջավոր ելքային ազդանշանների, ինչպես նաև ներքին վիճակների վերջավոր շարք

3. Թվային մեքենաներ- ավտոմատներ, որոնք փոխակերպում են թվայինտեղեկատվություն։ Նման ավտոմատներում մուտքային ազդանշանները տրվում են որպես ակնթարթային նշանների վերջավոր հավաքածու՝ դրանց տևողությունը այնքան փոքր է, որ կարելի է անտեսել: Ֆիքսված ժամանակի համար մուտքային նշանները փոխակերպվում են, և ելքը մի վիճակից մյուս վիճակի թռիչքային անցում է:

4. Աբստրակտ ավտոմատներ -մուտքագրման այբուբենի բառերի մի շարք ցուցադրում Xմեջելքային այբուբենի բառերի հավաքածու Յ.

Աբստրակտ ավտոմատը հետևյալն է.

~ Մաթեմատիկականմոդել,

~ Ալգորիթմկոդերի հաջորդականությունների որոշ վերափոխման գործողություններ,

~ օրենքմուտքային այբուբենի փոխակերպումները ելքայինի:

5. Սինխրոն և ասինխրոն ավտոմատներ. Կախված նրանից, թե մուտքային ազդանշանը և վիճակի փոփոխության ազդանշանը ստացվում են միաժամանակ կամ հաջորդաբար, ավտոմատները բաժանվում են համաժամանակյա և ասինխրոն ավտոմատների։

Սինքրոն մեքենաներումմուտքային ազդանշանների տեւողությունը եւ անցումների ժամանակը համաձայնեցված են միմյանց հետ։ Դրանք օգտագործվում են համակարգչային համակարգերում, ավտոմատացված կառավարման համակարգերում և այլն։

Ասինխրոն մեքենաներումմուտքային ազդանշանների տեւողությունը եւ անցումների ժամանակը համաձայնեցված չեն միմյանց հետ։ Դրանք կախված են արտաքին աղբյուրներից՝ տարբեր իրադարձություններից, և նմուշառման միջակայքըփոփոխական է (օրինակ՝ համակցված կողպեքներում)։ Ասինխրոն ավտոմատներում մուտքային ազդանշանների արժեքների հաջորդ փոփոխությունը կարող է տեղի ունենալ միայն այն դեպքում, եթե այս ազդանշանների նախորդ փոփոխությամբ առաջացած անցողիկ գործընթացը ավարտվել է:

6. Ավտոմատները բաժանվում են վերջավոր և անվերջ ավտոմատների։Եթե ​​դասակարգումը հիմնված է հիշողության չափը,ապա տարբերությունը կայանում է նրանում, թե արդյոք ավտոմատը ունի եզրափակիչկամ անվերջներքին վիճակների քանակը.

Անվերջության տակավտոմատը սովորաբար հասկացվում է որպես անսահման թվով վիճակներ ունեցող ավտոմատի մասին գաղափարների որոշակի մաթեմատիկական իդեալականացում։ Նման ավտոմատի հիշողությունը պոտենցիալ կարող է անվերջ աճել: Օրինակ՝ հայտնի Post և Turing աբստրակտ ավտոմատները անսահման ավտոմատներ են, բայց համակարգիչը կամ նրա առանձին մասերը վերջավոր ավտոմատներ են։

7. Ավտոմատները բաժանվում են դետերմինիստական ​​և հավանականական ավտոմատների. Եթե ​​դասակարգումը հիմնված է պատահական ընտրության մեխանիզմապա տարբերակվում է որոշիչ և հավանականական (ստոխաստիկ) ավտոմատների միջև։

Դետերմինիստական ​​ավտոմատներումվարքագիծը և կառուցվածքը ժամանակի յուրաքանչյուր պահի եզակիորեն որոշվում են ընթացիկ մուտքային տեղեկատվության և ինքն ավտոմատի վիճակի միջոցով նախորդ պահին:

Հավանական ավտոմատներում այս կախվածությունը նույնպես կապված է որոշ պատահական ընտրության հետ:

ՀավանականԱվտոմատը դիսկրետ տեղեկատվության փոխարկիչ է, որի գործունեությունը յուրաքանչյուր պահի կախված է միայն հիշողության վիճակներից և նկարագրված է վիճակագրական օրենքներով:

8. Ունիվերսալ մեքենա.Ավտոմատների տեսության մեջ ապացուցված է, որ տեղեկատվության տարբեր փոխակերպումներ իրականացնելու համար բավական է կառուցել. ունիվերսալավտոմատ մեքենա՝ ծրագրի և համապատասխան կոդավորման օգնությամբ, որն ունակ է լուծելու ցանկացած խնդիր։

Մեկ մուտքով թվային ավտոմատի մաթեմատիկական մոդելը տրվում է հինգ օբյեկտով.

X-մուտքային նշանների վերջավոր հավաքածու, մուտքային այբուբեն.

X \u003d (x 1 (t), x 2 (t), ..., x n (t));

Y-ելքային նշանների վերջավոր հավաքածու, ելքային այբուբեն.

Y \u003d (y 1 (t), y 2 (t), ..., y n (t));

Q~վերջավոր մի շարք ավտոմատ վիճակների:

Q= (q 0 (t), q 1 (t), q 2 (t), ..., q n (t)), q0- սկզբնական վիճակ;

δ(ք, X) - ավտոմատի մի վիճակից մյուսին անցնելու գործառույթը. Ք X x)®Q;

λ(q, X) ~ ավտոմատ ելքային գործառույթ. Ք x X) ® Յ.

Ուրեմն պետական ​​մեքենան C=(X, Q, Y, δ, λ.) որոշվում է ռեկուրսիվ հարաբերություններով

q(0) = q 0, q(t + I) = δ (g(t), x(t)), y(t) = λ (g(t), x(t)),

t-ը ժամանակի դիսկրետացված պահն է, թե՞ դա միապաղաղ ֆունկցիայի պատկեր է տ:. Տ® Ն, և T -սովորական շարունակական ժամանակը, N-ը բնական թվերի բազմությունն է:

Աշխատանքի բոլոր ժամերը Տբաժանվում է վերջավոր թվով ինտերվալների, որոնց սահմանին փոխվում է ավտոմատի վիճակը։ Միևնույն ժամանակ, t(Г 0)-ը ցույց է տալիս փոփոխությունների քանակը, որոնք տեղի են ունեցել մինչև Г 0 ժամանակը:

Դիսկրետացման օրինակ է սովորական կինոթատրոնը. ժամանակը բաժանվում է 1/24 վրկ միջակայքերի: Մարդկային աչքը դիսկրետ շրջանակների հետևյալն ընկալում է որպես շարունակական շարժում։

9. Սինխրոն ավտոմատները բաժանվում են Mealy ավտոմատների և Moore ավտոմատների. Կախված նրանից ելքի գործառույթը կազմակերպելու եղանակՍինքրոն մեքենաները բաժանվում են Mealy մեքենաների (առաջին տեսակի ավտոմատներ) և Մուր ավտոմատներ (երկրորդ տեսակի ավտոմատներ):

Միլի ավտոմատներում- ելքային ազդանշան y(t) x(t)և պետական ք(t- 1) ավտոմատը նախորդ պահին (t-մեկը): Նման ավտոմատների մաթեմատիկական մոդելը հավասարումների համակարգն է.

q(t) = δ (q(t-1), x(t)) և y(t) = λ (q(t-1), x(t)),

Մուրի մեքենաներումելքային ազդանշան y(t)եզակիորեն որոշվում է մուտքային ազդանշանով x(t)և պետական ք(t)տվյալ պահին տ. Նման ավտոմատների մաթեմատիկական մոդելը համակարգն է.

q(t) = δ (q(t-1), x(t)) և y(t) = λ (q(t)),

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

10. Համակցված ավտոմատներ– կան ավտոմատներ, որոնցում ելքային նշանը կախված չէ իր վիճակից և որոշվում է միայն ընթացիկ մուտքային նշաններով, այսինքն. այս ավտոմատում բոլոր վիճակները համարժեք են։ Նման ավտոմատում անցումային ֆունկցիան այլասերված է, այն սկզբունքորեն անկարևոր է և անփոփոխ շահագործման ընթացքում։ Հետեւաբար, նվազագույն կոմբինացիոն ավտոմատն ունի միայն մեկ վիճակ.

11 Բուլյանավտոմատներ - կան ավտոմատներ, որոնց մուտքային այբուբենը բաղկացած է 2 տերկուական երկարության հավաքածուներ տ,և ելքը 2 n երկարության երկուական հավաքածուներից է Պ.Համար տրամաբանական համակցումավտոմատ, ելքի ֆունկցիան ունի համակարգի ձև Պ տրամաբանական գործառույթները տփոփոխականներ.

Ավտոմատների տեսությունը դիսկրետ մաթեմատիկայի մի ճյուղ է, որն ուսումնասիրում է դիսկրետ տեղեկատվության փոխարկիչների մոդելները։ Նման փոխարկիչները և՛ իրական սարքերն են (համակարգիչներ, կենդանի օրգանիզմներ), և՛ երևակայական սարքեր (աքսիոմատիկ տեսություններ, մաթեմատիկական մեքենաներ): Ըստ էության, վերջավոր վիճակի մեքենան կարելի է բնութագրել որպես սարք Մ , որն ունի մուտքային և ելքային ալիքներ, մինչդեռ յուրաքանչյուր դիսկրետ ժամանակի պահերին, որոնք կոչվում են ժամացույցի պահեր, այն գտնվում է վերջնական վիճակներից մեկում։

Մուտքային ալիքի վրա ցանկացած պահի տ =1, 2, ... սարքին Մ մուտքային ազդանշանները գալիս են (որոշ վերջավոր ազդանշանների շարքից): Ժամանակի հաջորդ պահի փոփոխության օրենքը սահմանվում է կախված մուտքային ազդանշանից և տվյալ պահին սարքի վիճակից: Ելքային ազդանշանը կախված է ընթացիկ ժամանակի վիճակից և մուտքային ազդանշանից (նկ. 1):

Պետական ​​մեքենան իրական դիսկրետ տեղեկատվության մշակման սարքերի մաթեմատիկական մոդել է:

պետական ​​մեքենա կոչվում է համակարգ A= (X , Ք , Յ ,  ,  ), որտեղ X , Ք , Յ կամայական ոչ դատարկ վերջավոր բազմություններ են, և  և  - գործառույթներ, որոնցից.

շատ X ={ա 1 , ..., ա մ ) կոչվում է մուտքագրման այբուբենը , և դրա տարրերն են մուտքային ազդանշաններ , դրանց հաջորդականությունը նշված է գրավիչ արտահայտություններ ;

շատ Ք ={ք 1 , ..., ք n ) կոչվում է շատ նահանգներ ավտոմատ և դրա տարրերը - պետությունները ;

շատ Յ ={բ 1 , ..., բ էջ ) կոչվում է ելքային այբուբեն , նրա տարրերն են ելքային ազդանշաններ , դրանց հաջորդականություններն են ելքային բառեր ;

ֆունկցիան  : X  Ք Ք կանչեց անցումային ֆունկցիա ;

ֆունկցիան  :X  Ք Յ կանչեց ելքային գործառույթ .

Այս կերպ,  (x , ք )Ք ,  (x , ք )Յ համար  x X , ք Ք .

Պետական ​​մեքենայի հետ կապված է երևակայական սարք, որն աշխատում է հետևյալ կերպ. Կոմպլեկտից կարող է լինել վիճակում Ք , ստացեք ազդանշաններ հավաքածուից X և թողարկեք ազդանշաններ հավաքածուից Յ .

2. Վերջավոր ավտոմատի սահմանման մեթոդներ

Կան վերացական ավտոմատների սահմանման մի քանի համարժեք եղանակներ, որոնցից երեքն են. աղյուսակային , երկրաչափական և ֆունկցիոնալ .

2.1 Մեքենայի աղյուսակի նշանակում

Ավտոմատի սահմանումից հետևում է, որ այն միշտ կարող է սահմանվել աղյուսակով, որը պարունակում է երկու մուտքեր. տ գծեր և Պ սյուներ, որտեղ սյունակի խաչմերուկում ք և տողեր ա ֆունկցիայի արժեքները արժեն  (ա ես , ք ժ ),  (ա ես , ք ժ ).

2.2. Ավտոմատի սահմանում Մուրի գծապատկերով

Վերջավոր վիճակի մեքենան նշելու մեկ այլ եղանակ գրաֆիկական է, այսինքն՝ օգտագործելով գրաֆիկը: Ավտոմատը ներկայացված է որպես պիտակավորված ուղղորդված գրաֆիկ Գ(Ք , Դ ) բազմաթիվ գագաթներով Ք և շատ կամարներ Դ ={(ք ժ ,  (ա ես , ք ժ ))| ք ժ Ք , ա ես X ), մինչդեռ աղեղը ( ք ժ ,  (ա ես , ք ժ )) պիտակավորված է զույգով ( ա ես ,  (ա ես , ք ժ )): Այսպիսով, այս մեթոդով ավտոմատի վիճակները պատկերվում են շրջանագծերով, որոնցում մուտքագրվում են վիճակների նշանները. ք ժ (ժ = 1, …, n ) Յուրաքանչյուր շրջանից իրականացվում է տ սլաքներ (ուղղված եզրեր) մեկ առ մեկ, որոնք համապատասխանում են մուտքային այբուբենի նիշերին X ={ա 1 , ..., ա մ ) տառին համապատասխան սլաք ա ես X և դուրս գալով շրջանից ք ժ Ք , զույգը ( ա ես ,  (ա ես , ք ժ )), և այս սլաքը տանում է դեպի համապատասխան շրջան  (ա ես , ք ժ ).

Ստացված նկարը կոչվում է ավտոմատ գրաֆիկ կամ, Մուրի դիագրամ . Ոչ շատ բարդ ավտոմատների համար այս մեթոդն ավելի պատկերավոր է, քան աղյուսակային.

Խորհուրդ ենք տալիս կարդալ

Հանգստյան տուն

Ինչո՞վ է պայմանավորված խմելու մշտական ​​ցանկությունը։

Պաստառ

Բաշկորտոստանի Հանրապետության Խայբուլինսկի շրջանի կենտրոնացված գրադարանային համակարգ Բյանկա Իգոր Կուբերսկի

Հարդարում

Այծի պանրի տնային բաղադրատոմսը լուսանկարով քայլ առ քայլ

Մանկական

Ինչպես պատրաստել նեխուրի արմատը տանը

Խոհանոց

Կոռուպցիայի ամենացածր և ամենաբարձր մակարդակ ունեցող երկրները

Տանիք

Ինչպես ստուգել ձեր մեքենան կարգադրիչների կողմից ձերբակալված լինելու համար Ինչպես կոտրել մեքենան գրավի և տուգանքների համար