آلة دفع حتمية

في نظرية الأوتوماتا ، تُعدّ الأوتوماتا الحتمية ذات الدفع السفلي ( DPDA أو DPA ) نوعًا من أنواع الأوتوماتا ذات الدفع السفلي . وتقبل فئة الأوتوماتا الحتمية ذات الدفع السفلي اللغات الحتمية الخالية من السياق ، وهي مجموعة فرعية مناسبة من اللغات الخالية من السياق . ^{[ 1 ]}

تعتمد انتقالات الآلة على الحالة الحالية ورمز الإدخال، بالإضافة إلى الرمز العلوي الحالي في المكدس. الرموز الموجودة في أسفل المكدس غير مرئية وليس لها تأثير فوري. تشمل إجراءات الآلة دفع أو سحب أو استبدال الرمز العلوي في المكدس. تحتوي آلة الدفع السفلية الحتمية على انتقال واحد مسموح به على الأكثر لنفس تركيبة رمز الإدخال والحالة والرمز العلوي في المكدس. هذا هو الفرق بينها وبين آلة الدفع السفلية غير الحتمية.

آلة دفع ذاتي (ليست بالضرورة حتمية)${\displaystyle M}$يمكن تعريفها على أنها مجموعة سباعية:

${\displaystyle M=(Q\,,\Sigma \,,\Gamma \,,q_{0}\,,Z_{0}\,,A\,,\delta \,)}$

أين

• ${\displaystyle Q\,}$هي مجموعة محدودة من الحالات
• ${\displaystyle \Sigma \,}$هي مجموعة محدودة من رموز الإدخال
• ${\displaystyle \Gamma \,}$هي مجموعة محدودة من رموز المكدس
• ${\displaystyle q_{0}\,\in Q\,}$هي حالة البداية
• ${\displaystyle Z_{0}\,\in \Gamma \,}$هو رمز بداية المكدس
• ${\displaystyle A\,\subseteq Q\,}$، أين${\displaystyle A}$هي مجموعة الحالات المقبولة أو النهائية
• ${\displaystyle \delta \,}$هي دالة انتقال، حيث

${\displaystyle \delta \colon (Q\,\times (\Sigma \,\cup \left\{\varepsilon \,\right\})\times \Gamma \,)\longrightarrow {\mathcal {P}}(Q\times \Gamma ^{*})}$

أين${\displaystyle *}$هو نجم كلين ، مما يعني أن${\displaystyle \Gamma ^{*}}$هي "مجموعة جميع السلاسل المنتهية (بما في ذلك السلسلة الفارغة)${\displaystyle \varepsilon }$) من عناصر${\displaystyle \Gamma }$",${\displaystyle \varepsilon }$يشير إلى السلسلة الفارغة ، و${\displaystyle {\mathcal {P}}(X)}$هي مجموعة القوى لمجموعة${\displaystyle X}$.

تكون M حتمية إذا استوفت الشرطين التاليين:

• لأي${\displaystyle q\in Q,a\in \Sigma \cup \left\{\varepsilon \right\},x\in \Gamma }$، المجموعة${\displaystyle \delta (q,a,x)\,}$يحتوي على عنصر واحد على الأكثر.
• لأي${\displaystyle q\in Q,x\in \Gamma }$، لو${\displaystyle \delta (q,\varepsilon ,x)\not =\emptyset \,}$، ثم${\displaystyle \delta \left(q,a,x\right)=\emptyset }$لكل${\displaystyle a\in \Sigma .}$

هناك معياران محتملان للقبول: القبول بناءً على حالة المكدس الفارغة والقبول بناءً على الحالة النهائية . لا يتطابق هذان المعياران في حالة آلة الدفع الحتمية (مع أنهما يتطابقان في حالة آلة الدفع غير الحتمية). اللغات المقبولة بناءً على حالة المكدس الفارغة هي تلك اللغات التي تُقبل بناءً على الحالة النهائية وتكون خالية من البادئات: أي لا توجد كلمة في اللغة تُشكل بادئة لكلمة أخرى فيها. ^{[ 2 ] [ 3 ]}

المعيار المعتاد للقبول هو الحالة النهائية ، وهذا هو معيار القبول الذي يستخدم لتحديد اللغات الحتمية الخالية من السياق .

لو${\displaystyle L(A)}$هي لغة مقبولة بواسطة جهاز المساعد الرقمي الشخصي (PDA)${\displaystyle A}$ويمكن أيضًا قبولها بواسطة DPDA إذا وفقط إذا كانت هناك عملية حسابية واحدة من التكوين الأولي حتى عملية قبول لجميع السلاسل التي تنتمي إلى${\displaystyle L(A)}$. لو${\displaystyle L(A)}$إذا كان من الممكن قبولها بواسطة جهاز مساعد رقمي شخصي (PDA)، فهي لغة خالية من السياق، وإذا كان من الممكن قبولها بواسطة جهاز مساعد رقمي شخصي (DPDA)، فهي لغة حتمية خالية من السياق (DCFL).

ليست كل اللغات الخالية من السياق حتمية. وهذا ما يجعل آلة الأوتوماتية ذات التكرار المزدوج (DPDA) أضعف بكثير من آلة الأوتوماتية ذات التكرار المفرد (PDA). على سبيل المثال، لغة L p، التي تتكون من متواليات زوجية الطول على أبجدية 0 و1، لها قواعد نحوية خالية من السياق S → 0S0 | 1S1 | ε. إذا وُجدت آلة أوتوماتية ذات تكرار مزدوج لهذه اللغة، ورأت سلسلة نصية 0 n ، فيجب عليها استخدام مكدسها لحفظ طول السلسلة n ، لكي تتمكن من التمييز بين استمراراتها المحتملة 0 n  11 0 n ∈ L p و 0  n  11 0  n  + 2 ∉ L p . وبالتالي، بعد قراءة 0 n  11 0 n ، فإن مقارنة الطول بعد "11" بالطول قبل "11" ستجعل المكدس فارغًا مرة أخرى. لهذا السبب، لا يمكن التمييز بين السلسلتين 0 n 11 0 n 0 n 11 0 n ∈ L p و 0 n 11 0 n 0 n +2 11 0 n +2 ∉ L p . [ 4 ]

يؤدي تقييد آلة الدفع الآلي ذات الحالة الواحدة (DPDA) إلى تقليص فئة اللغات المقبولة إلى لغات LL(1) ، ^{[ 5 ]} وهي فئة فرعية مناسبة من لغة DCFL. ^{[ 6 ]} أما في حالة آلة الدفع الآلي (PDA)، فلا يؤثر هذا التقييد على فئة اللغات المقبولة.

• هامبرغر، هنري؛ دانا س. ريتشاردز (2002). نماذج المنطق واللغة لعلوم الحاسوب . أبر سادل ريفر، نيوجيرسي 07458: برنتيس هول. الصفحات 284-331 . ISBN  0-13-065487-6.{{cite book}}: CS1 maint: location ( link )