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

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

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

Վերջավոր ավտոմատի մաթեմատիկական սահմանումը տրվում է $A=⟨Q,\mathrm{\Sigma },\delta ,q_0,F⟩$ հնգյակի տեսքով, որի բաղադրիչներն ունեն հետևյալ նշանակությունը..

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

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

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

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

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

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

Հղումներ

Վերջավոր ավտոմատի օրինակ