On Repetitive Finite Automata with Translucent Words
František Mráz, Friedrich Otto · Electronic Proceedings in Theoretical Computer Science · 2025
We introduce and study the repetitive variants of the deterministic and the nondeterministic finite automaton with translucent words (DFAwtw and NFAwtw). On seeing the right sentinel, a repetitive NFAwtw need not halt immediately, accepting or rejecting, but it may change into another state and continue with its computation. We establish that a repetitive DFAwtw already accepts a language that is not even semi-linear, which shows that the property of being repetitive increases the expressive capacity of the DFAwtw and the NFAwtw considerably.