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

Վիքիպեդիայից՝ ազատ հանրագիտարանից

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

Մաթեմատիկական սահմանումը[խմբագրել | խմբագրել կոդը]

Վերջավոր ավտոմատի մաթեմատիկական սահմանումը տրվում է հնգյակի տեսքով, որի բաղադրիչներն ունեն հետևյալ նշանակությունը.[1].

  1. վիճակների վերջավոր բազմությունն է,
  2. մուտքային (ժապավենային) նիշերի վերջավոր բազմությունն է,
  3. անցումների ֆունկցիան է, որի արգումենտներն են ընթացիկ վիճակն ու մուտքային նիշը, իսկ արդյունքը նոր վիճակն (կամ վիճակները) է։
  4. սկզբնական վիճակն է (), որում գտնվում է ավտրոմատն իր աշխատանքը սկսելուց անմիջապես առաջ։
  5. վերջնական կամ ճանաչող (թույլատրող) վիճակների բազմությունն է։

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

Դետերմինացված վերջավոր ավտոմատ[խմբագրել | խմբագրել կոդը]

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

Ոչ-դետերմինացված վերջավոր ավտոմատ[խմբագրել | խմբագրել կոդը]

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

Հղումներ[խմբագրել | խմբագրել կոդը]

  1. Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey D. (1986). Compilers: Principles, Techniques, and Tools (1st տպ.). Addison-Wesley. ISBN 978-0-201-10088-4. 
Վերջավոր ավտոմատի օրինակ
Այս հոդվածի կամ նրա բաժնի որոշակի հատվածի սկզբնական կամ ներկայիս տարբերակը վերցված է Քրիեյթիվ Քոմմոնս Նշում–Համանման տարածում 3.0 (Creative Commons BY-SA 3.0) ազատ թույլատրագրով թողարկված Հայկական սովետական հանրագիտարանից  (հ․ 11, էջ 415 CC-BY-SA-icon-80x15.png