shown in Figure 11 where the transition function is asfollows:

Figure 10. The transition matrix of1DFA(2) accept a language.

Figure 11. 1REV-DFA(2) accept a language.

The transition matrix of the above automaton is shown in Figure 12.

Dot product of any two row is zero for multihead reversible finite state automaton.

8) 1-way multihead quantum finite state automaton

1-way multihead quantum finite state automaton is a 1-way k-head quantum finite state automaton where k-heads of the automaton can move to the right or stay on the current tape square but not beyond the end markers.The language is accepted by the 1QFA(k)

[see Figure 13] where

Figure 12. The transition matrix of 1REV-DFA(2) accept a language.

The transition matrix of the above automaton is shown in Figure 14.

The sum of the square of the norms in each row adds up to 1 and dot product of any two row is zero formultihead quantum finite state automaton.

3.1.2. Recognition of Language Class

In this section we show that 1QFA(k) has more language recognizing power than 1QFA. 1QFA(2) can recognize regular language and context-sensitive language respectively.

Theorem 4. 1QFA(2) can accept all unary regular languages.

Proof. In [12] it has been shown that any unary regular language is accepted by some 1-way reversible 2-headdeterministic finite automaton. We find from the previous section that in a 1-way multihead quantum

Figure 13. 1QFA(2) accept a language with acceptance probability p > 0.

Figure 14. The transition matrix of 1QFA(2) accept a language with acceptance probability p > 0.

finitestate automaton where the transition matrices are only 0 and 1 entry, it is essentially a 1-way reversible multihead finite state automaton. So 1-way 2-head quantum finite state automaton accept all unary language.

Example 1. A 1-way 2-head quantum finite state automaton is a automaton can accept in the folowing manner:

Let, , ,

Define:

The automaton acts as follows: Initially both heads of the automaton M are at #. After reading the input symbols, the automaton M remain at state. The first head remain stationary where the second head move one square to the right of the input tape whenever the automaton reaches at state. The movement of heads are similar as the previous case. Due to the movement of heads the second head may be at “a” or “b”.

For both cases the automaton M move to state from state and both heads move one square to theright of the input tape. When the first head at “a” and second head at “$”, the automaton M goes to final state from and the string will be accepted by the automaton M with probability 1.

Consider a string w not in L. As w is not in L the heads of the automaton M will arrived in such a way that for that particular position of heads and state, no transition rules are defined. So, for a string w, which M does not accept, there is no sequence of transitions that makes M to its final state after consumption of w. So, M rejects with probability 1. Each pairs of is unitary.

Example 2. A 1-way 2-head quantum finite state automaton is a automaton can accept in the following manner:

Let, , ,

Define:

The automaton acts as follows: Initially both heads of the automaton M are at #. After reading the input symbols, the automaton M remains at and the first head remain stationary and the second head moveone square to the right of the input tape.Whenever the automaton M reach at state the movement of heads are similar as the above case.The automaton M performs similar task as previous one for all inputletter “a” until the next input letter read by second head is “b”. For reading input letter “b” by the second head of the automaton M, it moves to state and remains at state until the next input letter read by thesecond head is “c”. This steps counts the number of letter “b” with number of letter “a”. Both heads move one square to the right of the input string for state. After reading the letter “c” by second head where the first is reading letter “a” of the input string, the automaton M goes to state from state. Both heads moveone square to the right of the input string whenever state will be reached. The automaton M now checks the number of letter “b” and “c” of the input string with two heads of the automaton until the second head readthe right endmarker $, for which the automaton goes to state. When the automaton M is in state and both heads read the right endmarker $, then the automaton accept the input string with probability 1.

Consider a string w not in L. As w is not in L the heads of the automaton M will arrived in such a way that for that particular position of heads and state, no transition rules are defined. So, for a string w, which M does not accept,there is no sequence of transitions that makes M to its final state after consumption of w. So, M rejects with probability 1. Condition of unitarity is satisfied for all pairs of.

Theorem 5. 1QFA(2) is more powerful than 1QFA with respect to recognition of language.

Proof. In Theorem 2 it was proved that the language cannot be recognized by 1QFA with bounded error. In Example 1 we proved that it can be done with 1QFA(2).

Theorem 6. Given a language it is possible in general case to build a 1QFA(k) that re- cognizes this language.

Proof. In [24] it has been shown that this language consists of subset of words from language whichis recognize by 1QFA(2) as shown in Example 1.

Example 3. A 1-way 2-head quantum finite state automaton is a automaton can accept in the following manner:

Let, , ,

Define:

The automaton acts as follows: at each reading of the symbol the automaton goes into a super-

position of two states and with amplitude a respectively.This is done with the objective that at

each reading of the symbol the automaton guesses x to be the first character which does not match. Thus if the guess is rightthen the path corresponding to goes to an accepting states and the guess is wrong the path correspondingto goes to an rejecting state. Even if the guess is wrong the path corresponding to allows us to makeanother guess. So if the input word belongs to L and k^{th} letter does not match with theend.

Then at the k^{th} depth will reach an accepting states with probability. But if the input word is an

palindrome and does notbelong to L then no matter what depth we traversed will never go to an accepting state. As the aboveautomaton is 1-way and the length of the input word is finite, the above automaton will always halt in finitetime and the input string belonging to the language is accepted by the automaton if the probability of state is greater than 0. We arrive at this conclusion because if the word is palindrome the probability of will be 0. Each is unitary by inspection. So M is well-formed. Figure 15 and Figure 16 shown below describe the working steps of the automaton in pictorial form.

Figure 15. Input “abba” is palindrome and hence it is not accepted.

Figure 16. Input “abba” is not palindrome and hence it is accepted.

Theorem 7. where is the set of all languages accepted by 1-way 2-head quantum finite state automaton and is the set of all languages accepted by 1-way 2-headdeterministic finite state automaton.

Proof. The language cannot be recognized by 1DFA(2) ( [18] [19] ). In Example 3 we proved that it can be done with 1QFA(2).

Theorem 8. For every 1-way reversible 2-head finite state automaton M which accepts a language L, thereexists a 1-way 2-head quantum finite state automaton M’ which accepts the same language L.

Proof. We know that the transition matrix of 1-way reversible multihead finite state automaton has the following properties:

1) Dot product of any two row is zero for 1-way reversible multihead finite state automaton.

2) All matrices only have 0 or 1 entries.

Therefore the above two properties of the transition matrix ensures that the transition matrix is also unitary. As a result given a 1-way reversible 2-head finite state automaton M we get a 1-way 2-head quantum finite state automaton M’ which has the same transition matrix,same set of states, same set of accepting states and start state as M. as the transition matrix, start state and accepting states of M and M’ are same,they accept the same language.

Theorem 9. The set of all languages accepted by 1-way reversible 2-head finite state automata (1RMFA(2)) is a proper subset of set of all language accepted by 1-way 2-head quantum finite state automata. (1QFA(2))

Proof. Theorem 8 tells us that for every 1RMFA(2) which accept a language L there exist 1QFA(2) which accept the same language. So, the set of all languages accepted by 1RMFA(2) is a subset of set of all languages accepted by 1QFA(2). From ( [18] [19] ) we know that the language is not accepted by any 1DFA(2). Also from ( [13] ) we know that the set of all languages accepted by 1RMFA(2) is a proper subset of 1DFA(2). Therefore, there is no 1RMFA(2) which accepts the language. In Example 3 ithas been shown 1QFA(2) accept the language L. Thus, the subset relation is proper.

Corollary 1. 1QFA(2) is computationally more powerful than 1RMFA(2).

4. Conclusion

In this paper, we studied characteristics of 1QFA(k) with their language accepting capability. There are still many non-regular context free context sensitive languages accepted by 1QFA(k) other than shown in this paper. We show that where is the set of all languages accepted by 1-way 2-head quantum finite state automaton and is the set of all languages accepted by 1-way 2-head deterministic finite state automaton. We also show that 1QFA(2) is more powerful than 1RMFA(2) with respect to recognition of language. But though 1QFA(2) can accepts some non-regular languages but it is still not be proved that whether 1QFA(2) can accepts all regular languages.We can explore it by using the superposition property of 1QFA(k).

Acknowledgements

Research of Debayan Ganguly is funded by the Council of Scientific Industrial Research (CSIR). This support is greatly appreciated.

Conflicts of Interest

The authors declare no conflicts of interest.

[1] |
Moore, C. and Crutchfield, J. (1997) Quantum Automata and Quantum Grammars. Theoretical Computer Science, 237, 275-306. http://dx.doi.org/10.1016/S0304-3975(98)00191-1 |

[2] |
Kondacs, A. and Watrous, J. (1997) On the Power of Quantum Finite State Automata. Proceedings of the 38th Annual Symposium on Foundations of Computer Science, Miami, 66-75. http://dx.doi.org/10.1109/SFCS.1997.646094 |

[3] |
Ambainis, A. and Freivalds, R. (1998) One-Way Quantum Finite Automata: Strengths, Weakness and Generalizations. IEEE 39th Annual Symposium on Foundations of Computer Science, 332-342.
http://dx.doi.org/10.1109/SFCS.1998.743469 |

[4] |
Ambainis, A., Bonner, R.F., Freivalds, R. and Kikusts, A. (1999) Probabilities to Accept Languages by Quantum Finite Automata. COCOON, 174-183. http://dx.doi.org/10.1007/3-540-48686-0_17 |

[5] | Ambainis, A., Bcandry, M., Golovkins, M., Kikusts, A., Mercer, M. and Therien, D. (2004) Algebric Results on Quantum Automata. STACS, 93-104. |

[6] | Bertoni, A., Mereghetti, C. and Palano, B. (2003) Quantum Computing: 1 way Quantum Automata. Developments Language Theory, 1-20. |

[7] | Ambainis, A. and Watrous, J. (2002) Two Way Finite Automata with Quantum and Classical States. Theoretical Computer Science, 287, 299-311. |

[8] | Ambainis, A., Beaudry, M., Golovkins, M., Kikusts, A., Mercer, M. and Therien, D. (2004) Algebraic Results on Quantum Automata. In: Diekert, V. and Habib, M., Eds., STACS, LNCS, Vol. 2996, Springer, Heidelberg, 93-104. |

[9] | Dzelme, I. (2003) Kvantu Automar Jauktajiem Stavokliem. Technical Report, University of Latvia. |

[10] |
Nayak, A. (1999) OPtimal Lower Bounds for Quantum Automata and Random Access Codes. Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 369-377. http://dx.doi.org/10.1109/sffcs.1999.814608 |

[11] | Rabin, M.O. and Scott, D. (1964) Finite Automata and Their Decision Problems. Sequential Machines, Selected Papers, Addition-Wesley, 63-91. |

[12] |
Rosenberg, A.L. (1966) On Multihead Finite Automata. IBM Journal of Research and Development, 10, 388-394.
http://dx.doi.org/10.1147/rd.105.0388 |

[13] |
Kutrib, M. and Malchar, A. (2013) One-Way Reversible Multi-Head Finite Automata. Reversible Computation, Lecture Notes in Computer Science, 7581, 14-28. http://dx.doi.org/10.1007/978-3-642-36315-3_2 |

[14] | Morita, K. (2011) Two-Way Reversible Multi-Head Finite Automata. Fundamenta Informaticae, IOS Press, 241-254. |

[15] |
Belovs, A., Rosmanis, A. and Smotrovs, J. (2007) Multi-Letter Reversible and Quantum Finite Automata. Proceedings of the 13th International Conference on Developments in Language Theory (DLT’2007), Lecture Notes in Computer Science, Vol. 4588, Springer, Berlin, 60-71. http://dx.doi.org/10.1007/978-3-540-73208-2_9 |

[16] | Qiu, D., Li, L., Zou, X., Mateus, P. and Gruska, J. (2011) Multi-Letter Quantum Finite Automata: Decidability of the Equivalence and Minimization of States. Acta Informatica, 271-290. |

[17] | Qiu, D. and Yu, S. (2006) Hierarchy and Equivalence of Multi-Letter Quantum Finite Automata. Theoretical Computer Science, 356, 190-199. |

[18] | Ibarra, H.O. and Ravikumar, B. (2009) On Partially Blind Multihead Automata. Theoretical Computer Science, 410, 3006-3017. |

[19] | Wagner, K. and Wechsung, G. (1986) Computational Complexity. D Reidel Publishing Company. |

[20] | Hopcroft, E.J.,Motwani, R. and Ullman, D.J. (2012) Introduction to Automata Theory. Languages, and Computation, Pearson, 3rd Edition. |

[21] | Sylvain, L. (2002) On the Construction of Reversible Automata for Reversible Language. Automata, Languages and Programming, Volume 2380 of the Series Lecture Notes in Computer Science, 170-182. |

[22] |
Rabin, O.M. (1963) Probabilistic Automata. Information and Control, 6, 230-245.
http://dx.doi.org/10.1016/S0019-9958(63)90290-0 |

[23] | Gruska, J. (2000) Quantum Computing. McGraw Hill, 153-157. |

[24] | Skuskovniks, A. On Languages Not Recognizable by One-Way Measure Many Quantum Finite Automaton. Supported by ESF Project 2009/0216/1DP/1.1.1.2.0/09/APIA/VIAA/044. |

comments powered by Disqus

Copyright © 2020 by authors and Scientific Research Publishing Inc.

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.