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:
“Hygiene is the corruption of medicine by morality. It is impossible to find a hygienest who does not debase his theory of the healthful with a theory of the virtuous.... The true aim of medicine is not to make men virtuous; it is to safeguard and rescue them from the consequences of their vices.”
—H.L. (Henry Lewis)
“A theory of the middle class: that it is not to be determined by its financial situation but rather by its relation to government. That is, one could shade down from an actual ruling or governing class to a class hopelessly out of relation to government, thinking of gov’t as beyond its control, of itself as wholly controlled by gov’t. Somewhere in between and in gradations is the group that has the sense that gov’t exists for it, and shapes its consciousness accordingly.”
—Lionel Trilling (1905–1975)
“No one thinks anything silly is suitable when they are an adolescent. Such an enormous share of their own behavior is silly that they lose all proper perspective on silliness, like a baker who is nauseated by the sight of his own eclairs. This provides another good argument for the emerging theory that the best use of cryogenics is to freeze all human beings when they are between the ages of twelve and nineteen.”
—Anna Quindlen (20th century)