Two-Way Finite Automata with Translucent Input Letters

Finite automata with translucent input letters can be obtained by equipping classical finite automata with a translucency function which, depending on the current state, establishes the set of invisible input symbols: such symbols are skipped in the current move and dealt with subsequently, while the first visible symbol from the current input head position is processed and consumed. These models can be returning, meaning that the input head is rewinded at each move after processing a visible symbol, or not. In their original definition by Mraz and Otto [13], translucent finite automata feature a one-way input head, i.e., the head always “looks to the right” to spot the next visible symbol. Here, we extend this definition in the deterministic case by allowing a two-way input head motion, meaning that the next visible symbol can be found by looking either to the left or to the right of the head. We also consider translucent sweeping finite automata, as the restricted version of two-way devices reverting input head direction at the endmarkers only. We prove that the sweeping restriction does not affect the recognition power in the returning mode, while the opposite holds for non-returning devices. We show that our devices are strictly more powerful than their one-way version, and that they are incomparable with translucent pushdown automata [9,14,17]. We investigate some closure properties for the families of languages recognized by translucent two-way and sweeping finite automata. In particular, while dealing with this latter topic, an open problem stated in [13] is addressed and solved.