Վերջավոր ավտոմատ

Վերջավոր ավտոմատ, կիբեռնետիկայի հասկացություն, որը վերաբերում է դիսկրետ ինֆորմացիան փոխակերպող և հիշողության վերջավոր սևեռված ծավալ ունեցող որևէ համակարգի մաթեմատիկական մոդելի։ Վերջավոր ավտոմատը կարող է լինել տեխնիկական սարքավորման (ԹՀՄ, ռելեային սարքավորում) կամ կենսաբանական համակարգի (կենդանու իդեալականացված նյարդային համակարգ) մոդել։ Գործնական մեծ նշանակություն ունեցող վերջավոր ավտոմատի տեսության կարևոր ուղղություններն են անհուսալի բաղադրիչներից հուսալի տարրերի սինթեզը և պատահական միջավայրերում վերջավոր ավտոմատի վարքի հետազոտումը։

Մաթեմատիկական սահմանումը

Վերջավոր ավտոմատի մաթեմատիկական սահմանումը տրվում է $A=\langle Q,\Sigma ,\delta ,q_{0},F\rangle$ հնգյակի տեսքով, որի բաղադրիչներն ունեն հետևյալ նշանակությունը.^[1].

$Q$ — վիճակների վերջավոր բազմությունն է,
$\Sigma$ — մուտքային (ժապավենային) նիշերի վերջավոր բազմությունն է,
$\delta$ — անցումների ֆունկցիան է, որի արգումենտներն են ընթացիկ վիճակն ու մուտքային նիշը, իսկ արդյունքը նոր վիճակն (կամ վիճակները) է։
$q_{0}$ — սկզբնական վիճակն է ( $q_{0}\in Q$ ), որում գտնվում է ավտրոմատն իր աշխատանքը սկսելուց անմիջապես առաջ։
$F$ — վերջնական կամ ճանաչող (թույլատրող) վիճակների բազմությունն է։

Կախված $\delta$ ֆունկցիայի տեսքից, վերջավոր ավտոմատն անվանում են դետերմինացված կամ ոչ-դետերմինցաված։

Դետերմինացված վերջավոր ավտոմատ

Վերջավոր ավտոմատը կոչվում է դետերմինացված, եթե ցանկացած մուտքային հաջորդականության համար գոյություն ունի միայն մեկ վիճակ, որին ավտոմատը կարող է անցում կատարել ընթացիկ վիճակից։ Այս դեպքում $\delta$ ֆունկցիայի արժեքը մի վիճակ է։

Ոչ-դետերմինացված վերջավոր ավտոմատ

Ի տարբերություն դետերմինացված վերջավոր ավտոմատի, ոչ-դետերմիացված վերջավոր ավտոմատը ժամանակի կոնկրետ պահին կարող է գտնվել մի քանի վիճակներում։ Այս դեպքում էլ $\delta$ ֆունկցիայի արժեքը ոչ թե վիճակ է, այլ՝ վիճակների բազմություն։

Հղումներ

↑ Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey D. (1986). Compilers: Principles, Techniques, and Tools (1st ed.). Addison-Wesley. ISBN 978-0-201-10088-4.

Այս հոդվածի կամ նրա բաժնի որոշակի հատվածի սկզբնական կամ ներկայիս տարբերակը վերցված է Քրիեյթիվ Քոմմոնս Նշում–Համանման տարածում 3.0 (Creative Commons BY-SA 3.0) ազատ թույլատրագրով թողարկված Հայկական սովետական հանրագիտարանից (հ․ 11, էջ 415)։

[1] Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey D. (1986). Compilers: Principles, Techniques, and Tools (1st ed.). Addison-Wesley. ISBN 978-0-201-10088-4.

[1]