1632
правки
Изменения
м
<nowiki>Вставьте сюда текст, который не нужно форматировать</nowiki>Неформально говоря квантовый конечный автомат {{---}} это квантовый аналог ''конечного автомата'', который использует [[Квантовые гейты | квантовые гейты]]. Такие автоматы позволяют допускать некотые языки, имея при этом экспоненциально меньший размер, чем обычные автоматы.
rollbackEdits.php mass rollback
== Определение ==
|definition=
'''Квантовый конечный автомат (ККА)''' (англ. ''Quantum finite automata'', ''QFA'') {{---}} это кортеж : <tex>(Q,\Sigma, V, q_0, Q_a, Q_r)</tex>, где
* <tex>Q</tex> — множество состояний автомата,* <tex>\Sigma</tex> — алфавит, из букв которого могут состоять входные слова,* <tex>V</tex> — функция перехода автомата,* <tex>q_0</tex> — начальное состояние автомата,* <tex>Q_a \subset Q</tex> — множество допускающих состояний,* <tex>Q_r \subset Q</tex> — множество опровергающих состояний,* <tex>Q_{non} = Q \setminus (Q_a \bigcup Q_r), Q_{non} \subset Q </tex> — множество промежуточных состояний.
}}
==Типы ККА==
* Первый тип {{---}} '''односторонние''' ККА. Они двигают только в одном направлении. Главная особенность односторонних ККА {{---}} допускать большинство регулярных языков. Также односторонние ККА делятся на Одномерные ККА и Многомерные ККА.* Второй тип {{---}} '''двухсторонние''' ККА. По аналогии с односторонним, они могу двигаться в обоих направлениях и их свойство {{---}} допускать нерегулярные языкы.
== Описание ==
|definition=
'''Многомерный квантовый конечный автомат''' (англ. ''Measure-many QFA'') {{---}} это кортеж : <tex>(Q,\Sigma, \delta, q_0, Q_a, Q_r)</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>,* <tex>Q_r \subset Q</tex> — базисные ортогональные вектора пр-ва <tex>\mathcal{H}_r</tex>.
}}
'''Многомерный''' ККА был введен Attila Kondacs и John Watrous в 1997. Его главное свойство {{---}} допускать регулярные языкы.
Принципы многомерного ККА очень схожи с одномернымодномерными, за исключением измерения вероятности после каждой итерации каждого прочтения символа входящей строки , вместо единственного измерения после полного ввода вероятности целой строчки как у одномерного одномерных ККА. Для формального определения понадобится [[Гильбертовы пространства | гильбертово пространство]]. Пусть у нас есть гильбертово пространство <tex>\mathcal{H}_Q</tex> :
<tex>\mathcal{H}_Q=\mathcal{H}_a \oplus \mathcal{H}_r \oplus \mathcal{H}_{non}</tex> , где <tex> \mathcal{H}_a </tex> {{---}} допускающее пр-во , <tex> \mathcal{H}_r </tex> {{---}} отвергающее пр-во , <tex> \mathcal{H}_{non} </tex> {{---}} промежуточное пр-во. Для каждого пр-ва существует набор базисных ортогональных векторов <tex>Q , Q_a \subset Q, Q_r \subset Q , Q_{non}\subset Q</tex> соответственно :
|definition=
'''Двухсторонний квантовый конечный автомат''' (англ. ''2-way QFA'') {{---}} это кортеж : <tex>(Q,\Sigma, \delta, q_0, Q_a, Q_r)</tex>, где
* <tex>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>Q_r \subset Q</tex> — множество опровергающих состояний.
}}
