Permutation automaton
Encyclopedia
In automata theory
, a permutation automaton, or pure-group automaton, is a deterministic finite automaton such that each input symbol permutes
the set of states.
Formally, a deterministic finite automaton may be defined by the tuple where is the set of states of the automaton, is the set of input symbols, is the transition function
that takes a state and an input symbol to a new state , is the initial state of the automaton, and is the set of accepting or final states of the automaton. is a permutation automaton if and only if, for every two distinct states and in and every input symbol in , .
A formal language
is p-regular (also: a pure-group language) if it is accepted by a permutation automaton. For example, the set of strings of even length forms a p-regular language: it may be accepted by a permutation automaton with two states in which every transition replaces one state by the other.
was proved to be computable.
Automata theory
In theoretical computer science, automata theory is the study of abstract machines and the computational problems that can be solved using these machines. These abstract machines are called automata...
, a permutation automaton, or pure-group automaton, is a deterministic finite automaton such that each input symbol permutes
Permutation
In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...
the set of states.
Formally, a deterministic finite automaton may be defined by the tuple where is the set of states of the automaton, is the set of input symbols, is the transition function
Transition function
In mathematics, a transition function has several different meanings:* In topology, a transition function is a homeomorphism from one coordinate chart to another...
that takes a state and an input symbol to a new state , is the initial state of the automaton, and is the set of accepting or final states of the automaton. is a permutation automaton if and only if, for every two distinct states and in and every input symbol in , .
A formal language
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
is p-regular (also: a pure-group language) if it is accepted by a permutation automaton. For example, the set of strings of even length forms a p-regular language: it may be accepted by a permutation automaton with two states in which every transition replaces one state by the other.
Applications
The pure-group languages were the first interesting family of regular languages for which the star height problemStar height problem
The star height problem in formal language theory is the question whether all regular languages can be expressed using regular expressions of limited star height, i.e. with a limited nesting depth of Kleene stars...
was proved to be computable.