3622
правки
Изменения
м
→Описание
Для начала воспользуемся графовым представлением [[Детерминированные конечные автоматы|ДКА]]. Пусть в нем <tex>N</tex> вершин, и все вершины пронумерованы. Тогда для представления такого графа можно воспользоваться набором [[Матрица смежности графа|матриц смежности]] таких, что каждая матрица размера <tex>[N \times N]</tex> и что каждому символу <tex>c \in \Sigma</tex> сопоставляется единственная матрица из этого набора. Каждая матрица состоит из <tex>0</tex> и <tex>1</tex>, причём <tex>1</tex> означает переход из состояния <tex>i</tex> в <tex>j</tex> по символу <tex>c</tex>, а <tex>0</tex> {{---}} его отсутствие. В этом случае, текущее состояние автомата записывается как вектор, размерности <tex>N</tex>, в котором будет лишь одна единица, обозначающая текущее положение состояния. При помощи такого описания можно легко делать переходы из нынешнего состояние в новое состояние по символу <tex> c \in \Sigma</tex> обыкновенным ''умножением матриц''.
Пусть у нас есть ДКА с <tex>N</tex> вершинами и его <math>\Sigma=\{c_1, c_2, c_3, \dots\}</math>. Тогда по описанному определению можно составить матрицы смежности <math>\{U_\alpha \mid \alpha \in \Sigma \}</math> размерности <tex>[N \times N]</tex>. Также введем <tex>N</tex>-размерный вектор <tex>q \in Q</tex>, описывающее описывающий состояние ДКА, a <tex>q_0</tex> {{---}} начальное состояние автомата. Тогда для перехода из состояния <tex>q_0</tex> в <tex>q</tex> по строчке <tex> s = \langle \alpha_0, \alpha_1,\dots \rangle</tex> нужно воспользоваться правилом умножения матриц из линейной алгебры : <math>q = \cdots U_{\alpha_1} U_{\alpha_0} q_0.</math>
Описанное выше по сути и является ККА, но в <tex>q</tex> записываются [[wikipedia:Probability amplitude|''амплитуды вероятностей'']], a матрицы <math>\{U_\alpha\}</math> {{---}} [[Унитарный и ортогональный операторы| ''унитарные матрицы'']].
