Введение
Конечный автомат в теории автоматов
В теории автоматов, перестановочный автомат, или чистый групповой автомат, — это детерминированный конечный автомат, для которого каждый входной символ переставляет множество состояний. Формально, детерминированный конечный автомат A может быть определен кортежем (Q, Σ, δ, q0, F), где Q — множество состояний автомата, Σ — множество входных символов, δ — функция перехода, отображающая состояние q и входной символ x в новое состояние δ(q, x), q0 — начальное состояние автомата, а F — множество принимающих состояний (также: конечных состояний) автомата. Автомат A является перестановочным автоматом тогда и только тогда, когда для любых двух различных состояний qi и qj из Q и любого входного символа x из Σ, δ(qi, x) ≠ δ(qj, x). Формальный язык называется p-регулярным (также: чистым групповым языком), если он принимается перестановочным автоматом. Например, множество строк четной длины является p-регулярным языком: он может быть принят перестановочным автоматом с двумя состояниями, в котором каждый переход заменяет одно состояние другим.
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 A may be defined by the tuple (Q, Σ, δ, q0, F),
where Q is the set of states of the automaton, Σ is the set of input symbols, δ is the transition function that takes a state q and an input symbol x to a new state δ(q,x), q0 is the initial state of the automaton, and F is the set of accepting states (also: final states) of the automaton. A is a permutation automaton if and only if, for every two distinct states qi and qj in Q and every input symbol x in Σ, δ(qi,x) ≠ δ(qj,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.
Приложения
Чистые групповые языки были первым интересным семейством регулярных языков, для которого проблема высоты звезды была доказана вычислимой. Другая математическая проблема, связанная с регулярными языками, — это проблема разделяющих слов, которая заключается в определении размера наименьшего детерминированного конечного автомата, способного различать два заданных слова длиной не более n, принимая одно слово и отклоняя другое. Известная верхняя оценка в общем случае — это . Позднее эта проблема была исследована для случая ограничения пермутационными автоматами. В этом случае известная верхняя оценка изменяется на .