摘要: 通过引入量化下推自动机与量化上下文无关文法的定义,研究了以两种不同方式接受语言的量化下推自动机等价性问题,证明了在可交换的双幺赋值幺半群上,量化下推自动机接受的语言与量化上下文无关文法生成的语言相同。
[1] HOPCROFT J E,MOTWANI R,ULLMAN J D.Introduction to Automata Theory,Languages and Computation (3rd)[M].New Jersey:Pearson Addision Wesley,2007:171-314. [2] LEE E T,ZADEH L A.Note on fuzzy languages[J].Information Science,1969,1(4):321-434. [3] 李永明.模糊系统分析[M].北京:科学出版社,2005:218-228. [4] YING M S.A theory of computation based on quantum logic(I) [J].Theoretical Computer Science,2005,344(2/3):134-207. [5] LI Y M,PEDRYCZ W.Fuzzy finite automata and fuzzy regular expressions with membership values in lattice-ordered monoids [J].Fuzzy Sets and Systems,2005,156(1):68-92. [6] QIU D W.Automata theory based on quantum logic:Reversibili-ties and pushdown automata[J].Theoretical Computer Scien-ce,2007,386(1):38-56. [7] XING H Y,QIU D W,LIU F C.Automata theory based on com-plete residuated lattice-valued logic:Pushdown automata[J].Fuzzy Sets and Systems,2009,160(8):1125-1140. [8] LI Y M.Finite automata theory with membership value in lattices [J].Information Science,2011,181(5):1003-1017. [9] DROSTE M,STBER T,VOGLER H.Weighted finite automata over strong bimonoids[J].Information Science,2010,0(1):156-166. [10] CHATTERJEE K,DOYEN L,HENZINGER T A.Quantitative languages [M]∥Computer Science Logic.Springer,2008:385-400. [11] DROSTE M,MEINECKE I.Weighted automata and regular expressions over valuation monoid[J].International Journal of Foundations of Computer Science,2011,2(8):1829-1844. [12] DROSTE M,MEINECKE I.Weighted automata and Weighted MSO logics for average and long-time behaviors[J].Information and Computation,2012,220-221(2):44-59. [13] HAN Z W,LI Y M.Pushdown automata and context-free grammars based on quantum logic[J].Journal of software,2010,21(9):2107-2117.(in Chinese) 韩召伟,李永明.基于量子逻辑的下推自动机与上下文无关文法 [J].软件学报,2010,1(9):2107-2117. [14] SONG X Z,HAN Z W,LI Y N.Algebraic properties of context-free grammar based on quantum logic[J].Computer Engineering and Applications,2011,47(4):42-46.(in Chinese) 宋小震,韩召伟,李永明.量子上下文无关文法的代数性质[J].计算机工程与应用,2011,7(4):42-46. |
No related articles found! |
|