Automata theory

Books on this shelf deal with automata theory: the study of abstract machines and problems which they are able to solve. An automaton is a mathematical model for a finite state machine (FSM). A FSM is a machine that, given an input of symbols, "jumps", or transitions, through a series of states according to a transition function. In the common variety of FSMs, this transition function tells the automaton which state to go to next given a current state and a current symbol. Note, however, that, in general, an automaton need not have a finite number of states, or even a countable number of states. An automaton need not strictly accept or reject an input; it may accept it with some probability between zero and one. Automata play a major role in compiler design and parsing.