Quantum automata and quantum grammars

Merina Aruja, Lisa Mathew, Jayakrishna Vijayakumar

Zhengjun Xi, Yongming Li, Xin Wang

Michail A. Zak

Qiu Dao

The relationships among various quantum automata are clarified, and in particular, variously equivalent characterizations of quantum automata are established. The G-quantum automata, g-quantum automata, (generalized) quantum automata, G-quantum grammars and g-quantum grammars are presented, and their connections to some of the other existing quantum automata are expounded. Under a certain condition, the equivalence between the G(g)-quantum automata and G(g)-quantum grammars is discussed. Therefore the problem of quantum grammars generating quantum regular languages is solved. The relation between quantum and regular languages is dealt with, and particularly, two open problems proposed by Gudder are answered. Finally, the method of decreasing the dimensions of spaces of states on quantum automata is given.

Ilze Dzelme-Bērziņa

Peng Jia

To increase depictive ability of quantum grammars and overcome difficulties in context sensitive grammars, we put forward the concepts of attributed G (g ) quantum grammars and attributed quantum automata in this paper. The relationship between them is investigated. It is proved that for a given attributed G (g ) quantum grammar G, an attributed quantum automaton Q can be produced such that f Q=f G,X , and vice versa. So attributed G (g ) quantum language can be recognized automatically.