Automata theory
study of abstract machines and automata
Automata theory is a branch of Theoretical computer science. Automata theory is concerned with the study of abstract machines called automata, and with the problems that can be solved using such machines. An automaton is characterized by a number of states it can be in, a number of transitions between those states, and an alphabet of symbols it accepts. One state is special: it is the state the automaton is in at the start. There are a number of states that are called final states or exit states; if at the end of the input, the automaton is in one of those states, it is said to accept the word just processed, otherwise it is said to reject it.
Example problems of automata theory include:
- The question to know whether a given automaton is the smallest possible, that accepts a given number of words. There are algorithms that permit to reduce the number of states, by combining different states that are equivalent.
