2-Head Pushdown Automata

Finite state automata recognize regular languages which can be used in text processing, compilers, and hardware design. 2-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. We distinguish between deterministic and nondeterministic finite automata, 2-head automata and also 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 may have a choice of move. The present thesis describes 2-head pushdown automata which is more powerful than the pushdown automata and it is able to recognize some non-context-free languages as well. Throughout the thesis we try to focus on characterization of aforementioned machines. Keywords: 2-head pushdown automata, non-context-free languages, deterministic automata, non-deterministic automata.