Queue Automaton - Theory

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:

    The human species, according to the best theory I can form of it, is composed of two distinct races, the men who borrow and the men who lend.
    Charles Lamb (1775–1834)

    Could Shakespeare give a theory of Shakespeare?
    Ralph Waldo Emerson (1803–1882)

    The theory seems to be that so long as a man is a failure he is one of God’s chillun, but that as soon as he has any luck he owes it to the Devil.
    —H.L. (Henry Lewis)