Applications
The pure-group languages were the first interesting family of regular languages for which the star height problem was proved to be computable.
Another mathematical problem on regular languages is the separating words problem, which asks for the size of a smallest deterministic finite automaton that distinguishes between two given words of length at most n – by accepting one word and rejecting the other. The known upper bound in the general case is . The problem was later studied for the restriction to permutation automata. In this case, the known upper bound changes to .
Read more about this topic: Permutation Automaton