Automata theory is a branch of Theoretical computer science. Automata theroy 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 stats 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 process, 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.