情報処理学会 第77回全国大会講演要旨

We suggest one-way jumping finite automata. These automata are modified jumping finite automata which can jump over some symbols while reading the input. The read head moves in one direction within the input word. One-way jumping finite automata accept different languages from jumping finite automata. We establish several results concerning one-way jumping finite automata, such as closure properties and pumping lemma for the accepted languages. We show the difference between the language class accepted by one-way jumping finite automata and classical language families, such as those regular languages and context-free languages.