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

Матеріал з Вікіпедії — вільної енциклопедії.

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

Для автомату 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).

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

[ред.] Джерела інформації

• Енциклопедія кібернетики, Чеботарев А. Н., т. 1, с. 26-27.

[ред.] Дивіться також

• Автоматів способи визначення

Це незавершена стаття з математики. Ви можете допомогти проекту, виправивши або дописавши її.