Remove ads

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

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

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

Remove ads

Див. також

Remove ads

Джерела

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

Wikiwand in your browser!

Seamless Wikipedia browsing. On steroids.

Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.

Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.

Remove ads