Кіріспе
Автоматтар теориясындағы шекті күй машинасы. Автоматтар теориясында пермутациялық автомат немесе таза топтық автомат — бұл әрбір кіріс символы күйлер жиынтығын өзгертетін детерминистік шекті автомат. Формальды түрде, детерминистік шекті автомат A (Q, Σ, δ, q0, F) түпл арқылы анықталады, мұнда Q — автоматтың күйлерінің жиынтығы, Σ — кіріс символдарының жиынтығы, δ — күй q және кіріс символы x үшін жаңа күй δ(q, x) беретін ауысу функциясы, q0 — автоматтың бастапқы күйі, ал F — автоматтың қабылдау күйлерінің (сонымен қатар: соңғы күйлері) жиынтығы. A пермутациялық автомат болып табылады, егер және тек қана егер, Q жиынтығындағы кез келген екі түрлі күй qi және qj және Σ жиынтығындағы кез келген кіріс символы 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 ұзындығы бар екі сөзді, біреуін қабылдап, екіншісін қабылдамай ажыратады. Жалпы жағдайда белгілі жоғарғы шек – . Бұл мәселе кейіннен пермутациялық автоматтарына шектеу қойылып зерттелді. Осы жағдайда белгілі жоғарғы шек өзгеріп .