Theory
We define a queue machine by the six-tuple
- where
- is a finite set of states;
- is the finite set of the input alphabet;
- is the finite queue alphabet;
- is the initial queue symbol;
- is the start state;
- is the transition function.
We define the current status of the machine by a configuration, an ordered pair of its state and queue contents (note defines the Kleene closure or set of all supersets of ). Therefore the starting configuration on an input string is defined as, and we can define our transition as the function that, given an initial state and queue, takes the function to a new state and queue. Note the "first-in-first-out" property of the queue in the relation
where defines the next configuration relation, or simply the transition function from one configuration to the next.
The machine accepts a string if after a (possibly infinite) number of transitions the starting configuration evolves to exhaust the string (reaching a null string ), or
Read more about this topic: Queue Automaton
Famous quotes containing the word theory:
“Many people have an oversimplified picture of bonding that could be called the “epoxy” theory of relationships...if you don’t get properly “glued” to your babies at exactly the right time, which only occurs very soon after birth, then you will have missed your chance.”
—Pamela Patrick Novotny (20th century)
“Osteopath—One who argues that all human ills are caused by the pressure of hard bone upon soft tissue. The proof of his theory is to be found in the heads of those who believe it.”
—H.L. (Henry Lewis)
“By the “mud-sill” theory it is assumed that labor and education are incompatible; and any practical combination of them impossible. According to that theory, a blind horse upon a tread-mill, is a perfect illustration of what a laborer should be—all the better for being blind, that he could not tread out of place, or kick understandingly.... Free labor insists on universal education.”
—Abraham Lincoln (1809–1865)