|
|
|
|
|
Post MachineIn theoretical computer science and recursion theory, a Post machine, named after Emil Leon Post, is a deterministic finite automaton with a queue. There is no separate input tape. At the start of the computation, the input string x is loaded on the queue. The input string is followed by a special symbol Zo. At the start of the computation, the contents of the queue are xZo. The first symbol of x is at the front of the queue and Zo is at the end of the queue. A transition of a Post machine depends on the symbol at the front of the queue and on the state. Each transition will delete the symbol at the front of the queue. A transition has two components: the next state and the string to be added at the end of the queue. This string can be the empty string. References - V.A.Uspensky, "A Post Machine" (in Russian), Moscow, "Nauka", 1979.
External links
|
 |
|
| Copyright 2005-2009 OnPedia.com. All Rights Reserved |
|
|