Editing Permutation automaton (section)

{{Short description|Finite-state machine in automata theory}}
In [[automata theory]], a '''permutation automaton''', or '''pure-group automaton''', is a [[deterministic finite automaton]] such that each input symbol [[permutation|permutes]] the set of states.<ref name=McNaughton1967>{{Citation
 | title = The loop complexity of pure-group events
 |date=August 1967
 | author = McNaughton, Robert
 | journal = Information and Control
 | pages = 167–176
 | volume = 11
 | issue = 1-2
 | doi=10.1016/S0019-9958(67)90481-0
| doi-access = free
 }}</ref><ref>{{cite journal |last=Thierrin|first=Gabriel|date=March 1968|title=Permutation automata|journal=Theory of Computing Systems|volume=2|issue=1|pages=83–90|doi=10.1007/BF01691347}}</ref>

Formally, a deterministic finite automaton {{mvar|A}} may be defined by the tuple (''Q'', Σ, δ, ''q''<sub>''0''</sub>, ''F''),
where ''Q'' is the set of states of the automaton, Σ is the set of input symbols, δ is the [[Transition map|transition function]] that takes a state ''q'' and an input symbol ''x'' to a new state δ(''q'',''x''), ''q''<sub>''0''</sub> is the initial state of the automaton, and ''F'' is the set of accepting states (also: final states) of the automaton. {{mvar|A}} is a permutation automaton if and only if, for every two distinct states {{math|''q<sub>i</sub>''}} and {{math|''q<sub>j</sub>''}} in ''Q'' and every input symbol {{mvar|x}} in Σ,  δ(''q<sub>i</sub>'',''x'') ≠ δ(''q<sub>j</sub>'',''x'').

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.