Автоматтар теориясы: Ауыспалы автоматтар (AFA) – экзистенциалды және универсалды өтулерге бөлінетін автоматтар. Нондетерминистік және параллель машина сияқты жұмыс істейді.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Автоматтар теориясында ауыспалы шекті автомат (АФА) — ауыспалы және әмбебап ауысуларға бөлінетін нон-детерминистік шекті автомат. Мысалы, А ауыспалы автомат болсын. Экзистенциалдық ауысу үшін А, a символын оқып, күйін немесе күйіне нон-детерминистік түрде ауыстырады. Осылайша, ол қалыпты нон-детерминистік шекті автомат сияқты жұмыс істейді. Әмбебап ауысу үшін А, a символын оқып, және күйіне өтеді, бұл параллель машинаның әрекетін имитациялайды. Әмбебап квантификацияға байланысты, орындалу жолы орындалу ағашы арқылы көрсетіледі. АFA сөз w-ны қабылдайды, егер w сөзіндегі кез келген жол қабылдау күйінде аяқталатын орындалу ағашы болса. Негізгі теорема, кез келген АFA детерминистік шекті автоматқа (DFA) эквивалентті екенін көрсетеді, сондықтан АFA тек қана тұрақты тілдерді қабылдайды. Көбінесе қолданылатын балама модель — бұл Бульдік комбинациялардың дизъюнктивті қалыпты формада болуы, мысалы, tt (true) күйін білдіреді, ал ff (false) күйі осы жағдайда арқылы белгіленеді. Бұл бейнелеу көбінесе тиімдірек болады. Ағаш автоматтары сияқты, ағаштарды қабылдау үшін ауыспалы шекті автоматтарды кеңейтуге болады, нәтижесінде ауыспалы ағаш автоматтары пайда болады.
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-ны, NFA-ны DFA-ға түрлендіруде қолданылатын қуат жиыны құрастыру сияқты әдіс арқылы, күйлеріне дейін нон-детерминистік шекті автоматқа (NFA) түрлендіреді.
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) және сөз үшін, автомат осы сөзді қабылдай ма деп сұрайды. Бұл мәселе P-толық. Бұл тіпті бір ғана символдан тұратын әліпбиде де дұрыс, яғни автомат бір символді тілді қабылдағанда да солай. Бос емес мәселе (берілген автоматты түйінделген автоматтың тілі бос емес пе?), жалпыламалық мәселесі (берілген автоматты түйінделген автоматтың тілінің толықтығы бос па?), және эквиваленттілік мәселесі (екі берілген автоматты түйінделген автомат бірдей тілді таниды ма?) автоматты түйінделген автоматтар үшін PSPACE-толық.
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.