In theoretical computer science, automata theory is the study of abstract machines and the problems that they are able to solve. Automata theory is closely related to formal language theory as the automata are often classified by the type of formal languages that they are able to recognize (see below: push down automata, linear bounded automata and Turing machines). (Wikipedia)
An automaton is a mathematical model for a finite state machine (FSM). A FSM is a machine that, given an input of symbols, moves through a series of states according to a transition function. A FSM is a model of behaviour composed of a finite number of states, transitions between those states, and actions. It is similar to a "flow graph" where we can inspect the way in which the logic runs when certain conditions are met. A finite state machine is an abstract model of a machine with a primitive internal memory. The input stream to a FSM is a tape from which symbols are read and to which they can be written. 'Memory' is what is written on the tape. A FSM can also be expressed as a table. (Wikipedia)
Here is an example of a FSM reading the word 'nice': link.
The input is read symbol by symbol, until it is consumed completely (similar to a tape with a word written on it, which is read by a reading head of the automaton; the head moves forward over the tape, reading one symbol at a time). When the input is exhausted, the automaton is said to have stopped. (Wikipedia)
Depending on the state in which the automaton stops, the automaton either accepts or rejects the input. If it lands in an accept state, then the automaton accepts the word. If, on the other hand, it lands on a reject state, the word is rejected. The set of all the words accepted by an automaton is called the language accepted by the automaton.
Automata play a major role in compiler design and parsing. The distinction between FSM and FSA is that a FSM displays output while a FSA does not; a FSA will evaulate the input and produce output of Yes (acceptance of the input as valid) or No (non-acceptance: the input is invalid).
These basic concepts are common to most descriptions of automata:
Symbol: basic unit of the machine such as a letter
Alphabet: A finite set of symbols
Word: finite string formed by concatenation of symbols
Language: A set of words, formed by symbols in a given alphabet
There are three types of finite automata:
Deterministic finite automaton (DFA): Each state of an automaton of this kind has a transition for every symbol in the alphabet. For each pair of state and input symbol there is one and only one transition to a next state. A DFA will take in a string of input symbols. For each input symbol it will then transition to a state given by following a transition function. When the last input symbol has been received it will either accept or reject the string depending on whether the DFA is in an accepting state or a non-accepting state. Example. What does this FSM do? What is its alphabet? What is a valid word in its language? What is its language? Implement this example in Turing Kara.
Non-deterministic finite automaton (NFA): States of an automaton of this kind may or may not have a transition for each symbol in the alphabet, or can have multiple transitions for a symbol.
Non-deterministic finite automaton with ε transitions: advanced!
Pushdown automata: identical to DFAs (or NFAs), except that they additionally carry memory in the form of a stack. The top of the stack can be used to decide on the next transition and they can manipulate the stack when performing a transition. See here for an account of expression evaluation using a stack.
Linear bounded automata: A LBA is a limited Turing machine; instead of an infinite tape, the tape has an amount of space proportional to the size of the input string. They accept the context-sensitive languages. This limitation on tape length makes an LBA a more accurate model of computers that actually exist than a Turing machine in some respects.
Turing machines: These are the most powerful computational machines. They possess an infinite memory in the form of a tape, and a head which can read and change the tape, and move in either direction along the tape. Turing machines are equivalent to algorithms, and are the theoretical basis for modern computers. Turing machines decide/accept recursive languages and recognize the recursively enumerable languages. Turing machines are abstract, a thought experiment, and have never been built.
