69
правок
Изменения
Нет описания правки
* На выходе мы получаем число <tex> Pr(s)</tex>, являющееся вероятностью данного конечного автомата быть в допускающем состоянии.
==Типы ККА==* Первый тип {{---}} '''односторонние''' ККА. Они двигают только в одном направлении. Главная особенность {{---}} допущение большинство регулярных языков. Также односторонний делятся на Одномерные и Многомерные ККА.* Второй тип {{---}} '''двухсторонние''' ККА. По аналогии с односторонним, они могу двигаться в обоих направлениях и их свойство {{---}} допущение нерегулярных языков. == Описание==
Для первоначального описание ККА воспользуемся следующим примером. Пусть есть графовым представлением [[Детерминированные конечные автоматы|ДКА]] и пусть в нем <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>Q</tex> — базисные ортогональные вектора пр-ва <tex>\mathcal{H}_Q</tex>
* <tex>\Sigma</tex> — алфавит, из букв которого могут состоять входные слова
* <tex>\delta : Q\times \Sigma \times Q \to \mathbb{C} </tex> —всюду — всюду определённая функция перехода автомата
* <tex>q_0</tex> — начальное состояние автомата
* <tex>Q_a \subset Q</tex> — базисные ортогональные вектора пр-ва <tex>\mathcal{H}_a</tex>
:<math>\operatorname{Pr}_a (s) = \Vert P_a |\psi\rangle \Vert^2</math>, где <tex>s</tex> {{---}} входная строчка
==Двухсторонние квантовые конечные автоматы==
{{Определение
|definition=
'''Двухсторонний квантовый конечный автомат''' (англ. ''2-way QFA'') {{---}} это кортеж : <math>(Q,\Sigma, \delta, q_0, Q_a, Q_r)</math>, где
* <tex>Q</tex> — базисные ортогональные вектора пр-ва <tex>\mathcal{H}_Q</tex>
* <tex>\Sigma</tex> — алфавит, из букв которого могут состоять входные слова
* <tex>\delta : Q\times \Sigma \times Q \to \mathbb{C} \times \{-1,0,1\}</tex> — всюду определённая функция перехода автомата
* <tex>q_0</tex> — начальное состояние автомата
* <tex>Q_a \subset Q</tex> — базисные ортогональные вектора пр-ва <tex>\mathcal{H}_a</tex>
* <tex>Q_r \subset Q</tex> — базисные ортогональные вектора пр-ва <tex>\mathcal{H}_r</tex>
}}
Отличия от одностороннего :
* Головка может двигаться в обоих направлениях.
* Может гарантированно разрешать регулярный язык.
* Может за линейное время разрешать нерегулярный язык.
==См. также==
