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

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

Recognition Power Analysis of Two-Way Two-Dimensional Finite Automata

The recognition power of three types of two-way two-dimensional finite automata were investigated, including deterministic, nondeterministic and Las Vegas finite automata. By inferences in theory, it was proved that there is a language that can be recognized by two-way two-dimensional Las Vegas finite automaton but can't be recognized by deterministic one, and that there is a language that can be recognized by two-way two-dimensional nondeterministic finite automaton but can't be recognized by Las Vegas one. The following two results are obtained: languages recognized by two-way two-dimensional Las Vegas finite automata strictly contain languages that recognized by deterministic ones; languages recognized by two-way two-dimensional nondeterministic finite automata strictly contain languages that recognized by Las Vegas ones.