论文标题
不返回的有限自动机和半透明的字母
Non-Returning Finite Automata With Translucent Letters
论文作者
论文摘要
在这里，我们提出了一个不确定性有限自动机的变体，并带有半透明的字母（NFAWTL），在阅读和删除字母后，它不会返回磁带的左端，而是从刚刚删除的字母位置继续进行。当达到录音机标记器时，我们的自动机可以决定是否接受，拒绝还是继续，这意味着从一开始就再次读取其余的磁带内容。这种类型的自动机，称为非返回的有限自动机，具有半透明字母或NRNFAWTL，比NFAWTL更具表现力。我们研究这种类型的自动机及其确定性变体的表达能力。同样，我们对由此产生的语言类别和决策问题的封闭属性感兴趣。
Here we propose a variant of the nondeterministic finite automaton with translucent letters (NFAwtl) which, after reading and deleting a letter, does not return to the left end of its tape, but rather continues from the position of the letter just deleted. When the end-of-tape marker is reached, our automaton can decide whether to accept, to reject, or to continue, which means that it again reads the remaining tape contents from the beginning. This type of automaton, called a non-returning finite automaton with translucent letters or an nrNFAwtl, is strictly more expressive than the NFAwtl. We study the expressive capacity of this type of automaton and that of its deterministic variant. Also we are interested in closure properties of the resulting classes of languages and in decision problems.
