Simultaneously One-Turn Two-Pushdown Automata

Consider two consecutive moves, $m_{1}$ and $m_{2}$ , made by a two-pushdown automaton, M , whose pushdowns are denoted by $\pi_{1}$ and $\pi_{2}$ . If during $m_{1}$ M does not shorten $\pi_{i}$ , for some $i = 1, 2$ , while during $m_{2}$ it shortens $\pi_{i}$ , then M makes a turn in $\pi_{i}$ during $m_{2}$ . If M makes a turn in both $\pi_{1}$ and $\pi_{2}$ during $m_{2}$ , this turn is simultaneous . A two-pushdown automaton is one-turn if it makes no more than one turn in either of its pushdowns during any computation. A two-pushdown automaton is simultaneously one-turn if it makes either no turn or one simultaneous turn in its pushdowns during any computation. This paper demonstrates that every recursively enumerable language is accepted by a simultaneously one-turn two-pushdown automaton. Consequently, every recursively enumerable language is accepted by a one-turn two-pushdown automaton.

Keywords:

• Automata Theory
• One-turn Two-pushdown Automata
• Recursively Enumerable Languages