Automata theory
lastmod 2022-03-20created 2015-10-162 edits
Automata theory is the field of computer science that studies abstract machines with computational capability and the problems that can be solved using those machines. Here, the abstract machines are called automata (plural) or automaton (singular), that is, automatic machines. The name comes from the Greek word 'αὐτόματα', meaning 'self-acting'.
In general, an automaton has at least a finite number of states, receives input, transitions between states in a fixed way according to the input, and produces output. This is the same as what an algorithm requires, namely the ability to solve computational problems. Computational problems are generally converted into decision problems to fit the capabilities of automata, and at this point abstract machines, formal languages, and formal grammars become inseparable. Therefore, automata have the same hierarchical classification as languages and grammars.
Automaton theory is the study of automata, but put another way, it concerns 'part or all of a sequence of processes in which one focuses on some function of an object, translates the interrelationship between the input and internal output signals into a mathematical model, examines this model mathematically and derives conclusions, and then interprets the derived conclusions by fitting them back exactly onto the original object'. It is not much concerned with things such as the properties of the object's components. Automata are an important element of computer architecture design, compiler design, parsing, formal verification of formal models, and more.