%0 Journal Article
%T Automata and Grammars Theory Based on Quantum Logic<br>基于量子逻辑的自动机和文法理论
%A QIU Dao-Wen
%A <br>邱道文
%J 软件学报
%D 2003
%I 
%X In this paper, a fundamental framework of automata and grammars theory based on quantum logic is preliminarily established. First, the introduce quantum grammar, which is called l valued grammars, is introduced. It is particularly showed that the language (called quantum language) generated by any l valued regular grammar is equivalent to that recognized by some automaton with e moves based on quantum logic (called l valued automata), and conversely, any quantum language recognized by l valued automaton is also equivalent to that generated by some l valued grammar. Afterwards, the l valued pumping lemma is built, and then a decision characterization of quantum languages is presented. Finally, the relationship between regular grammars and quantum grammars (l valued regular grammars) is briefly discussed. Summarily, the introduced work lays a foundation for further studies on more complicated quantum automata and quantum grammars such as quantum pushdown automata and Turing machine as well as quantum context-free grammars and context-sensitive grammars.
%K quantum logic
%K automata
%K regular grammar
%K formal language
%K pumping lemma<br>量子逻辑
%K 自动机
%K 正规文法
%K 形式语言
%K 泵引理
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=7735F413D429542E610B3D6AC0D5EC59&aid=4FDAE23DAAD6A1A1&yid=D43C4A19B2EE3C0A&vid=F3583C8E78166B9E&iid=CA4FD0336C81A37A&sid=EA389574707BDED3&eid=DB817633AA4F79B9&journal_id=1000-9825&journal_name=软件学报&referenced_num=10&reference_num=15