3622
правки
Изменения
м
→Многомерный квантовый конечный автомат
'''Многомерный''' ККА был введен Attila Kondacs и John Watrous в 1997. Его главное свойство {{---}} допускать нерегулярный язык <tex>L = \{a^mb^m\}</tex> за линейное время.
Принципы многомерного ККА очень схожи с одномерным, за исключением применения матрицы <tex>P</tex> после каждой итерации символа строки. Для формального определения понадобиться понадобится [[Гильбертовы пространства | гильбертово пространство]]. Пусть у нас есть гильбертово пространство <math>\mathcal{H}_Q</math> :
<math>\mathcal{H}_Q=\mathcal{H}_a \oplus \mathcal{H}_r \oplus \mathcal{H}_{non}</math> , где <math> \mathcal{H}_a </math> {{---}} допускающее пр-во , <math> \mathcal{H}_r </math> {{---}} отвергающее пр-во , <math> \mathcal{H}_{non} </math> {{---}} промежуточное пр-во. Для каждого пр-ва существует набор базисных ординальных векторов <tex>Q , Q_a \subset Q, Q_r \subset Q , Q_{non}\subset Q</tex> соответственно :
