DSpace
 

EMU I-REP >
08 Faculty of Arts and Sciences >
Department of Mathematics >
Theses (Master's and Ph.D) – Mathematics >

Please use this identifier to cite or link to this item: http://hdl.handle.net/11129/3301

Title: 2-Head Pushdown Automata
Authors: Nagy, Benedek
Awe, Samson Ayodeji
Eastern Mediterranean University, Faculty of Arts and Science, Department of Mathematics
Keywords: Mathematics
Applied Mathematics and Computer Science
Machine theory - Formal languages - Computer programming
2-head pushdown automata
non-context-free languages
deterministic automata
non-deterministic automata
Issue Date: Feb-2015
Publisher: Eastern Mediterranean University (EMU) - Doğu Akdeniz Üniversitesi (DAÜ)
Citation: Awe, Samson Ayodeji. (2015). 2-Head Pushdown Automata. Thesis (M.S.), Eastern Mediterranean University, Institute of Graduate Studies and Research, Dept. of Mathematics, Famagusta: North Cyprus.
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.
Description: Master of Science in Applied Mathematics and Computer Science. Thesis (M.S.)--Eastern Mediterranean University, Faculty of Arts and Sciences, Dept. of Mathematics, 2015. Supervisor: Assoc. Prof. Dr. Benedek Nagy.
URI: http://hdl.handle.net/11129/3301
Appears in Collections:Theses (Master's and Ph.D) – Mathematics

Files in This Item:

File Description SizeFormat
AweSamson.pdfThesis, Master934.9 kBAdobe PDFView/Open


This item is protected by original copyright

Recommend this item
View Statistics

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

 

Valid XHTML 1.0! DSpace Software Copyright © 2002-2010  Duraspace - Feedback