Hairpin Finite Automata
Henning Bordihn, Markus Holzer, Martin Kutrib · Universitätsbibliothek Gießen · 2011
We introduce and investigate nondeterministic finite automata with the additional ability to apply the hairpin inversion operation to the remaining part of the input. Three different modes of hairpin operations, namely left-most hairpin, general hairpin, and right-most hairpin are considered. We show that these operations do not increase the computation power, when the number of operations is bounded by a constant. An unbounded number of these operations leads to language families that are properly contained in the family of context~sensitive languages and are supersets of the family of regular languages. Moreover, we show that in most cases we obtain incomparability results for the language families under consideration. Finally, we prove that the language families accepted by the variants of hairpin finite automata are not closed under standard operations of formal language theory as, for example, intersection, complementation, concatenation, homomorphism, and inverse homomorphism.