Automata theory
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.
Automata Theory Media
The automaton described by this state diagram starts in state S1, and changes states following the arrows marked 0 or 1 according to the input symbols as they arrive. The double circle marks S1 as an accepting state. Since all paths from S1 to itself contain an even number of arrows marked 0, this automaton accepts strings containing even numbers of 0s.
