2-Head Pushdown Automata

Abstract

Finite state automata recognize regular languages which can be used in text processing, compilers, and hardware design. Two head finite automata accept linear context free languages. In addition, pushdown automata are able to recognize context free languages which can be used in programming languages and artificial intelligence. The finite automaton has deterministic and non-deterministic version likewise the two head finite automata and the pushdown automata. The deterministic version of these machines is such that there is no choice of move in any situation while the non-deterministic version has a choice of move. In this research the 2-head pushdown automata are described which is more powerful than the pushdown automata and it is able to recognize some non-context free languages as well. During this work, the main task is to characterize these machines. (C) 2015 The Authors. Published by Elsevier Ltd. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/).