二维二方向有限自动机的识别能力研究

摘要

研究了3种有限自动机,即二维二方向的确定型、非确定型以及Las Vegas有限自动机.证明存在语言能被二维二方向的Las Vegas有限自动机识别,但不能被相应的确定型有限自动机识别;存在语言能被二维二方向的非确定型有限自动机识别,但不能被相应的Las Vegas有限自动机识别.研究结果表明,二维二方向的Las Vegas有限自动机所识别的语言真包含确定型有限自动机所识别的语言;二维二方向的非确定型有限自动机所识别的语言真包含Las Vegas有限自动机所识别的语言.