Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Автоматтар теориясында, детерминистік pushdown автоматы (DPDA немесе DPA) – pushdown автоматының бір түрі. Детерминистік pushdown автоматтар класы детерминистік контекстсіз тілдерді қабылдайды, бұл контекстсіз тілдердің нақты кіші жиынтығы. Машинаның күйіне өтулер ағымдағы күйге, кіріс символына және стектің ең жоғарғы символына байланысты болады. Стектегі төменгі символдар көрінбейді және дереу әсер етпейді. Машинаның іс-әрекеттеріне стекке символ қосу, стек жоғарғы символын алып тастау немесе оны ауыстыру кіреді. Детерминистік pushdown автоматының кіріс символы, күй және стек жоғарғы символының бірдей комбинациясы үшін тек бір ғана заңды күйіне өту мүмкіндігі бар. Осыған байланысты ол nondeterministic pushdown автоматынан өзгеше.
In automata theory, a deterministic pushdown automaton (DPDA or DPA) is a variation of the pushdown automaton. The class of deterministic pushdown automata accepts the deterministic context free languages, a proper subset of context free languages. Machine transitions are based on the current state and input symbol, and also the current topmost symbol of the stack. Symbols lower in the stack are not visible and have no immediate effect. Machine actions include pushing, popping, or replacing the stack top. A deterministic pushdown automaton has at most one legal transition for the same combination of input symbol, state, and top stack symbol. This is where it differs from the nondeterministic pushdown automaton.
Тұлғалар мен тілдер
Егер тіл PDA-мен қабылданатын болса, ол DPDA-мен де қабылдануы мүмкін, бірақ ғана егер барлық тілдерге қатысты бастапқы конфигурациядан қабылдау конфигурациясына дейін бір ғана есептеу болса. Егер тіл PDA-мен қабылданатын болса, ол контекстсіз тіл, ал егер DPDA-мен қабылданатын болса, онда ол детерминистік контекстсіз тіл (DCFL) болып табылады. Барлық контекстсіз тілдер детерминистік емес. Бұл DPDA-ны PDA-ға қарағанда әлсіз құрылғыға айналдырады. Мысалы, 0 және 1 алфавиттеріндегі жұп ұзындығы палиндромдар Lp тілі үшін контекстсіз грамматика S → 0S0 | 1S1 | ε бар. Егер осы тіл үшін DPDA болса және ол 0n жолын көрсе, 0n 11 0n ∈ Lp және 0n 11 0n+2 ∉ Lp мүмкіндіктерін ажырату үшін, оның стегін n ұзындығын жаттау үшін пайдалану керек. Сондықтан, 0n 11 0n оқығаннан кейін, "11" алдындағы және кейінгі ұзындықтарды салыстыру стекті қайтадан бос етеді. Осы себепті 0n 11 0n 0n 11 0n ∈ Lp және 0n 11 0n 0n+2 11 0n+2 ∉ Lp тізбектерін ажырату мүмкін емес. DPDA-ны бір ғана күйге шектеу қабылданған тілдер класын DCFL-дің тиісті кіші класы LL(1) тілдеріне дейін азайтады. PDA жағдайында, бұл шектеу қабылданған тілдер класына әсер етпейді.
If is a language accepted by a PDA , it can also be accepted by a DPDA if and only if there is a single computation from the initial configuration until an accepting one for all strings belonging to If can be accepted by a PDA it is a context free language and if it can be accepted by a DPDA it is a deterministic context free language (DCFL). Not all context free languages are deterministic. This makes the DPDA a strictly weaker device than the PDA. For example, the language Lp of even length palindromes on the alphabet of 0 and 1 has the context free grammar S → 0S0 | 1S1 | ε. If a DPDA for this language exists, and it sees a string 0n, it must use its stack to memorize the length n, in order to be able to distinguish its possible continuations 0n 11 0n ∈ Lp and 0n 11 0n+2 ∉ Lp. Hence, after reading 0n 11 0n, comparing the post "11" length to the pre "11" length will make the stack empty again. For this reason, the strings 0n 11 0n 0n 11 0n ∈ Lp and 0n 11 0n 0n+2 11 0n+2 ∉ Lp cannot be distinguished. Restricting the DPDA to a single state reduces the class of languages accepted to the LL(1) languages, which is a proper subclass of the DCFL. In the case of a PDA, this restriction has no effect on the class of languages accepted.
Жабылу
Детерминистік контекстсіз тілдердің (оқырманның соңғы күйі бойынша детерминистік PDA-мен қабылданатын) жабылу қасиеттері, контекстсіз тілдерден едәуір өзгеше. Мысалы, олар (тиімді түрде) толықтыру бойынша жабық, бірақ біріктіру бойынша жабық емес. Детерминистік PDA қабылдаған тілдің толықтырылымын да детерминистік PDA қабылдайтынын дәлелдеу қиын. Негізгі принцип бойынша, шексіз есептеулерден қашу керек. Толықтырудың нәтижесінде, детерминистік PDA-ның кіріс әліпбиі бойынша барлық сөздерді қабылдайтыны, оның толықтырылымын бос екендігін тексеру арқылы анықталады. Бұл контекстсіз грамматикалар үшін (сонымен қатар, жалпы PDA үшін) мүмкін емес.
Closure properties of deterministic context free languages (accepted by deterministic PDA by final state) are drastically different from the context free languages. As an example they are (effectively) closed under complementation, but not closed under union. To prove that the complement of a language accepted by a deterministic PDA is also accepted by a deterministic PDA is tricky. In principle one has to avoid infinite computations. As a consequence of the complementation it is decidable whether a deterministic PDA accepts all words over its input alphabet, by testing its complement for emptiness. This is not possible for context free grammars (hence not for general PDA).
Теңдестік мәселесі
Жерар Сенізергю (1997) детерминистік PDA үшін баламалылық мәселесінің шешімді екенін дәлелдеді (яғни, екі детерминистік PDA A және B берілгенде, L(A)=L(B) бола ма?) Осы дәлелі үшін ол 2002 жылы Гедель сыйлығына ие болды. Ал, детерминистік емес PDA үшін баламалылық шешілмейді.
Géraud Sénizergues (1997) proved that the equivalence problem for deterministic PDA (i. e. given two deterministic PDA A and B, is L(A)=L(B)?) is decidable, a proof that earned him the 2002 Gödel Prize. For nondeterministic PDA, equivalence is undecidable.