2-Head Pushdown Automata

Abstract

ÖZ: Sonlu otomata düzenli dilleri tanır ve metin işleme, derleyiciler ve donanım tasarımı icin kullanilabilir. Iki basli sonlu otomata doğrusal bağlamsiz dilleri kabul eder, ve ters otomata programlama dilleri ve yapay zeka konularinda kullanilabilen baglamsiz dilleri tanir. Sonlu otomat iki basli sonlu otomata ve asagi suruklemeli otomata’da oldugu gibi deterministik ve deterministik olmayan versiyonlara sahiptir. Bu otomata’larin deterministik versiyonlarinda hareket etme secimi yapilamaz iken, deterministik olmayan versiyonlarda hareket seçimi yapmak mumkundur. Bu tezde ters otomata’dan daha güçlü olan bunun yani sira bazi baglamli dilleri de tanimakta olan 2-basli asagi suruklemeli otomata tarif edilmiştir. Bu çalışmalar sırasında, temel olarak yapilan is bu otomata’lari karakterize etmektir. Anahtar Kelimeler: 2-basli asagi suruklemeli otomata, bağlamli serbest diller, deterministik otomata, deterministik olmayan otomata.

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.