5? ? 3? Watson-Crick pushdown automata

Abstract

Watson-Crick automata work on two-stranded tape, and, consequently, they have two reading heads. In the case of sensing 5' -> 3' Watson-Crick automata, the two heads start from different ends of the input and they move in opposite directions until they meet. In this paper, an extension of these automata is presented by adding a pushdown stack. This model can also be seen as a 2-head extension of the pushdown automata. Acceptance by empty stack and acceptance by final states are proven to have the same recognition power in this new model. The language family recognized by this model contains only semi-linear context-sensitive languages and it includes the class of context-free languages. Some well-known non-context-free languages are shown as examples. Normal form like results, a pumping lemma and various closure properties are also proven. (C) 2020 Elsevier Inc. All rights reserved.