%0 Journal Article
%T 二维二方向有限自动机的识别能力研究
%A 董晶
%A 刘庆晖
%J 北京理工大学学报
%D 2012
%X 研究了3种有限自动机,即二维二方向的确定型、非确定型以及LasVegas有限自动机.证明存在语言能被二维二方向的LasVegas有限自动机识别,但不能被相应的确定型有限自动机识别;存在语言能被二维二方向的非确定型有限自动机识别,但不能被相应的LasVegas有限自动机识别.研究结果表明,二维二方向的LasVegas有限自动机所识别的语言真包含确定型有限自动机所识别的语言;二维二方向的非确定型有限自动机所识别的语言真包含LasVegas有限自动机所识别的语言.
%K 二维二方向
%K 确定型
%K 非确定型
%K Las
%K Vegas型
%U http://journal.bit.edu.cn/zr/ch/reader/view_abstract.aspx?file_no=20121107&flag=1