Перестановочный автомат

В теории автоматов автомат перестановок или автомат чистой группы — это детерминированный конечный автомат , в котором каждый входной символ переставляет набор состояний.

Формально детерминированный конечный автомат A может быть определен набором ( Q , Σ, δ, q ₀ , F ),где Q – множество состояний автомата, Σ – множество входных символов, δ – функция перехода , переводящая состояние q и входной символ x в новое состояние δ( q , x ), q ₀ – исходное состояние автомата, а F — множество принимающих состояний (также: конечных состояний) автомата. A является автоматом перестановок тогда и только тогда, когда для каждых двух различных состояний q _i и q _j в Q и каждого входного символа x в Σ δ( q _i , x ) ≠ δ( q _j , x ).

Формальный язык является p-регулярным (также: чисто групповым языком ), если он принимается перестановочным автоматом. Например, набор строк четной длины образует p-регулярный язык: его может принять перестановочный автомат с двумя состояниями, в которых каждый переход заменяет одно состояние другим.

Приложения

Чистогрупповые языки были первым интересным семейством регулярных языков, для которых проблемы высоты звезды была доказана вычислимость .

Другая математическая проблема в регулярных языках — это проблема разделения слов , которая требует определения размера наименьшего детерминированного конечного автомата, который различает два заданных слова длиной не более n — принимая одно слово и отвергая другое. Известная верхняя оценка в общем случае равна $O(n^{2/5}(\log n)^{3/5})$. Позже проблема была изучена на предмет ограничения на перестановочные автоматы. В этом случае известная верхняя граница изменится на $O(n^{1/2})$.