Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
В теории автоматов, чередующийся конечный автомат (AFA) — это недетерминированный конечный автомат, переходы которого разделены на экзистенциальные и универсальные переходы. Например, пусть A — чередующийся автомат. Для экзистенциального перехода δ(q, a), A недетерминированно выбирает перейти в состояние q₁ или q₂, считывая символ a. Таким образом, он ведёт себя как обычный недетерминированный конечный автомат. Для универсального перехода δ(q, a), A переходит в состояния q₁ и q₂, считывая символ a, имитируя поведение параллельной машины. Обратите внимание, что из-за универсальной квантификации ход выполнения представляется деревом выполнения. A принимает слово w, если существует дерево выполнения для w, такое что каждый путь в этом дереве заканчивается в принимающем состоянии. Основная теорема утверждает, что любой AFA эквивалентен детерминированному конечному автомату (DFA), следовательно, AFA распознают только регулярные языки. Альтернативная модель, которая часто используется, представляет булевы комбинации в дизъюнктивной нормальной форме, так что, например, (p ∧ q) представляется как (p ∧ q). В этом случае состояние "истина" (true) представлено как 1, а состояние "ложь" (false) — как 0. Это представление обычно более эффективно. Чередующиеся конечные автоматы могут быть расширены для распознавания деревьев аналогично конечным автоматам на деревьях, что приводит к чередующимся автоматам на деревьях.
In automata theory, an alternating finite automaton (AFA) is a nondeterministic finite automaton whose transitions are divided into existential and universal transitions. For example, let A be an alternating automaton. For an existential transition , A nondeterministically chooses to switch the state to either or , reading a. Thus, behaving like a regular nondeterministic finite automaton. For a universal transition , A moves to and , reading a, simulating the behavior of a parallel machine. Note that due to the universal quantification a run is represented by a run tree. A accepts a word w, if there exists a run tree on w such that every path ends in an accepting state. A basic theorem states that any AFA is equivalent to a deterministic finite automaton (DFA), hence AFAs accept exactly the regular languages. An alternative model which is frequently used is the one where Boolean combinations are in disjunctive normal form so that, e. g., would represent The state tt (true) is represented by in this case and ff (false) by This representation is usually more efficient. Alternating finite automata can be extended to accept trees in the same way as tree automata, yielding alternating tree automata.
Сложность состояния
Несмотря на то, что AFA может распознавать только регулярные языки, они отличаются от других типов конечных автоматов лаконичностью описания, измеряемой числом состояний. Чандра и др. преобразуют AFA с *n* состояний в недетерминированный конечный автомат (NFA) с не более чем 2^n состояний, выполняя конструкцию подмножеств, аналогичную той, что используется для преобразования NFA в DFA.
Even though AFA can accept exactly the regular languages, they are different from other types of finite automata in the succinctness of description, measured by the number of their states. Chandra et al. converts an AFA with states to a nondeterministic finite automaton (NFA) with up to states by performing a similar kind of powerset construction as used for the transformation of an NFA to a DFA.
Комплексность вычислений
Задача о членстве спрашивает, для заданного AFA и слова , принимает ли этот AFA данное слово. Эта задача является P-полной. Это верно даже для однобуквенного алфавита, то есть когда автомат принимает унитарный язык. Задача о непустоте (не пуст ли язык заданного AFA?), задача об универсальности (пуст ли комплемент языка заданного AFA?) и задача об эквивалентности (определяют ли два заданных AFA один и тот же язык) являются PSPACE-полными для AFA.
The membership problem asks, given an AFA and a word , whether accepts This problem is P complete. This is true even on a singleton alphabet, i. e., when the automaton accepts a unary language. The non emptiness problem (is the language of an input AFA non empty? ), the universality problem (is the complement of the language of an input AFA empty? ), and the equivalence problem (do two input AFAs recognize the same language) are PSPACE complete for AFAs.