2-Head Pushdown Automata
| Autor: | Awe Ayodeji Samson |
|---|---|
| Rok vydání: | 2015 |
| Předmět: |
TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES
Theoretical computer science Nested word Computer science Timed automaton ω-automaton computer.software_genre Deterministic pushdown automaton DFA minimization Regular language Deterministic automaton Quantum finite automata General Materials Science Two-way deterministic finite automaton Nondeterministic finite automaton Finite-state machine Programming language Deterministic context-free language Computability Deterministic context-free grammar Context-free language Pushdown automaton Non-Context-Free Languages Deterministic 2-Head Pushdown Automata Nonlinear Sciences::Cellular Automata and Lattice Gases Embedded pushdown automaton Mobile automaton TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Deterministic finite automaton 2-Head Pushdown Automata Theory of computation Computer Science::Programming Languages Automata theory Compiler computer Computer Science::Formal Languages and Automata Theory |
| Zdroj: | Procedia - Social and Behavioral Sciences. 195:2037-2046 |
| ISSN: | 1877-0428 |
| DOI: | 10.1016/j.sbspro.2015.06.225 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|