Матриця переходів автомата

Ма́триця перехо́дів автома́та — один зі способів визначення скінченного абстрактного автомата.

Для автомата A, який має n станів, матриця переходів автомата ||A|| являє собою квадратну матрицю порядку n. Нехай {a₁, a₂, …, a_n} — множина станів автомата A, а {x₁, x₂, …, x_m} та {y₁, y₂, …, y_k} — відповідно вхідний та вихідний алфавіти. У випадку ініціального автомата a₁ завжди позначає початковий стан.

Елементом (i, j) матриці ||A|| є множина пар виду (x_is/y_is), таких, що під дією вхідного сигналу x_is автомат A переходить зі стану a_i в стан a_j і видає, при цьому, вихідний сигнал y_is. Для позначення множини, яка складається із пар (x_i1/y_i1), (x_i2/y_i2), …, (x_iq, y_iq), зазвичай виписують ці пари, з'єднані знаком диз'юнкції: (x_i1/y_i1) ∨ (x_i2/y_i2) ∨ … ∨ (x_iq, y_iq).

Від матриці переходів автомата легко перейти до будь-якого іншого способу визначення абстрактного автомата, наприклад, до таблиць переходів та виходів, графа автомата, тощо.

Див. також

• Матриця суміжності
• Способи задання автоматів

Джерела

• Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001). Вступ до теорії автоматів, мов і обчислень (вид. 2nd). Addison–Wesley. с. 521. {{cite book}}: Зовнішнє посилання в |edition= (довідка)(англ.)
• Енциклопедія кібернетики, Чеботарев А. Н., т. 1, с. 26-27.