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

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

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

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

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

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

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

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


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