Ма́триця перехо́дів автома́та — один зі способів визначення скінченного абстрактного автомату.
Для автомата A, який має n станів, матриця переходів автомату ||A|| являє собою квадратну матрицю порядку n. Нехай {a1, a2, …, an} — множина станів автомату A, а {x1, x2, …, xm} та {y1, y2, …, yk} — відповідно вхідний та вихідний алфавіти. У випадку ініціального автомату a1 завжди позначає початковий стан.
Елементом (i, j) матриці ||A|| є множина пар виду (xis/yis), таких, що під дією вхідного сигналу xis автомат A переходить зі стану ai в стан aj і видає, при цьому, вихідний сигнал yis. Для позначення множини, яка складається із пар (xi1/yi1), (xi2/yi2), …, (xiq, yiq), зазвичай виписують ці пари, з'єднані знаком диз'юнкції: (xi1/yi1) ∨ (xi2/yi2) ∨ … ∨ (xiq, yiq).
Від матриці переходів автомату легко перейти до будь-якого іншого способу визначення абстрактного автомату, наприклад, до таблиць переходів та виходів, графу автомата, і так далі.
Див. також
Джерела
- Hopcroft, John E.; ; Ullman, Jeffrey D. (2001). Вступ до теорії автоматів, мов і обчислень (вид. 2nd). Addison–Wesley. с. 521.(англ.)
- Енциклопедія кібернетики, , т. 1, с. 26-27.
Це незавершена стаття з математики. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Ma tricya pereho div avtoma ta odin zi sposobiv viznachennya skinchennogo abstraktnogo avtomatu Dlya avtomata A yakij maye n staniv matricya perehodiv avtomatu A yavlyaye soboyu kvadratnu matricyu poryadku n Nehaj a1 a2 an mnozhina staniv avtomatu A a x1 x2 xm ta y1 y2 yk vidpovidno vhidnij ta vihidnij alfaviti U vipadku inicialnogo avtomatu a1 zavzhdi poznachaye pochatkovij stan Elementom i j matrici A ye mnozhina par vidu xis yis takih sho pid diyeyu vhidnogo signalu xis avtomat A perehodit zi stanu ai v stan aj i vidaye pri comu vihidnij signal yis Dlya poznachennya mnozhini yaka skladayetsya iz par xi1 yi1 xi2 yi2 xiq yiq zazvichaj vipisuyut ci pari z yednani znakom diz yunkciyi xi1 yi1 xi2 yi2 xiq yiq Vid matrici perehodiv avtomatu legko perejti do bud yakogo inshogo sposobu viznachennya abstraktnogo avtomatu napriklad do tablic perehodiv ta vihodiv grafu avtomata i tak dali Div takozhMatricya sumizhnosti Sposobi zadannya avtomativDzherelaHopcroft John E Ullman Jeffrey D 2001 Vstup do teoriyi avtomativ mov i obchislen vid 2nd Addison Wesley s 521 angl Enciklopediya kibernetiki t 1 s 26 27 Ce nezavershena stattya z matematiki Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi