Permutation automaton
In automata theory, a permutation automaton is a deterministic finite automaton such that each input symbol permutes the set of states.[1]
Formally, a deterministic finite automaton A may be defined by the tuple (S, I, δ, s0, F) where S is the set of states of the automaton, I is the set of input symbols, δ is the transition function that takes a state s and an input symbol x to a new state δ(s,x), s0 is the initial state of the automaton, and F is the set of accepting or final states of the automaton. A is a permutation automaton if and only if, for every two distinct states si and sj in S and every input symbol x in I, δ(si,x) ≠ δ(sj,x).
A formal language is p-regular 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.
References
- ^ Thierrin, Gabriel (1968). "Permutation automata". Theory of Computing Systems. 2 (1): 83–90. doi:10.1007/BF01691347.
{{cite journal}}: Unknown parameter|month=ignored (help)
 | This formal methods-related article is a stub. You can help Wikipedia by expanding it. |