آلة الضغط المدمجة

آلة الدفع المدمجة ( EPDA ) هي نموذج حسابي لتحليل اللغات المولدة بواسطة قواعد النحو المتجاورة الشجرية (TAGs). وهي تشبه آلة الدفع لتحليل قواعد النحو الخالية من السياق ، ولكن بدلاً من استخدام مكدس عادي لتخزين الرموز، تستخدم مكدسًا من المكدسات المتكررة لتخزين الرموز، مما يمنح قواعد النحو المتجاورة الشجرية قدرة توليدية تقع بين قواعد النحو الخالية من السياق وقواعد النحو الحساسة للسياق ، أو مجموعة فرعية من قواعد النحو الحساسة للسياق بشكل طفيف . يجب عدم الخلط بين آلات الدفع المدمجة وآلات المكدس المتداخلة التي تتمتع بقدرة حسابية أكبر.

وُصفت قواعد البيانات المكانية المُحسَّنة (EPDAs) لأول مرة من قِبل ك. فيجاي شانكر في أطروحته للدكتوراه عام 1988. ^{[ 1 ]} ومنذ ذلك الحين، طُبِّقت هذه القواعد على أوصاف أكثر شمولاً لفئات القواعد النحوية الحساسة للسياق بشكل طفيف، ولعبت أدوارًا مهمة في تحسين التسلسل الهرمي لتشومسكي . وبذلك، يُمكن تعريف قواعد نحوية فرعية متنوعة، مثل القواعد النحوية الخطية المفهرسة . ^{[ 2 ]}

على الرغم من أن اللغات الطبيعية تُحلل تقليديًا باستخدام قواعد نحوية خالية من السياق (انظر القواعد النحوية التحويلية التوليدية واللغويات الحاسوبية )، إلا أن هذا النموذج لا يُجدي نفعًا مع اللغات ذات التبعيات المتقاطعة، مثل اللغة الهولندية، وهي حالات يُناسبها تحليل EPDA. يتوفر تحليل لغوي مفصل في كتاب جوشي وشابيس (1997). ^{[ 3 ]}

آلة EPDA هي آلة حالة محدودة مزودة بمجموعة من المكدسات التي يمكن الوصول إليها من خلال المكدس المضمن . يحتوي كل مكدس على عناصر من أبجدية المكدس.${\displaystyle \,\Gamma }$وهكذا نُعرّف عنصرًا من عناصر المكدس بواسطة${\displaystyle \,\sigma _{i}\in \Gamma ^{*}}$، حيث يمثل النجم إغلاق كلين للأبجدية.

يمكن تعريف كل مجموعة من العناصر بدلالة مكوناتها، لذلك نرمز إلى${\displaystyle \,j}$المكدس رقم 1 في الآلة باستخدام رمز الخنجر المزدوج:${\displaystyle \,\Upsilon _{j}=\ddagger \sigma _{j}=\{\sigma _{j,k},\sigma _{j,k-1},\ldots ,\sigma _{j,1}\}}$، أين${\displaystyle \,\sigma _{j,k}}$سيكون الرمز التالي الذي يمكن الوصول إليه في المكدس. المكدس المضمن لـ${\displaystyle \,m}$وبالتالي يمكن الإشارة إلى المكدسات بواسطة${\displaystyle \,\{\Upsilon _{j}\}=\{\ddagger \sigma _{m},\ddagger \sigma _{m-1},\ldots ,\ddagger \sigma _{1}\}\in (\ddagger \Gamma ^{+})^{*}}$.

نُعرّف EPDA بواسطة المجموعة السباعية (مجموعة من 7 عناصر).

${\displaystyle \,M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},Q_{\textrm {F}},\sigma _{0})}$أين

• ${\displaystyle \,Q}$هي مجموعة محدودة من الحالات ؛
• ${\displaystyle \,\Sigma }$هي المجموعة المحدودة من أبجدية الإدخال ؛
• ${\displaystyle \,\Gamma }$هي الأبجدية ذات المكدس المحدود ؛
• ${\displaystyle \,q_{0}\in Q}$هي حالة البداية ؛
• ${\displaystyle \,Q_{\textrm {F}}\subseteq Q}$هي مجموعة الحالات النهائية ؛
• ${\displaystyle \,\sigma _{0}\in \Gamma }$هو رمز المكدس الأولي
• ${\displaystyle \,\delta :Q\times \Sigma \times \Gamma \rightarrow S}$هي دالة الانتقال ، حيث${\displaystyle \,S}$هي مجموعات جزئية منتهية من${\displaystyle \,Q\times (\ddagger \Gamma ^{+})^{*}\times \Gamma ^{*}\times (\ddagger \Gamma ^{+})^{*}}$.

وبالتالي، تأخذ دالة الانتقال حالةً، والرمز التالي من سلسلة الإدخال، والرمز العلوي للمكدس الحالي، وتُنشئ الحالة التالية، والمكدسات التي سيتم دفعها وسحبها إلى المكدس المُضمّن ، ودفع وسحب المكدس الحالي، والمكدسات التي ستُعتبر المكدسات الحالية في الانتقال التالي. وبعبارة أخرى، يتم دفع المكدس المُضمّن وسحبه، ويمكن دفع المكدس الحالي مرة أخرى إلى المكدس المُضمّن ، ويتم دفع أي مكدسات أخرى مطلوبة فوقه، مع كون المكدس الأخير هو الذي تتم قراءته في التكرار التالي. لذلك، يمكن دفع المكدسات فوق المكدس الحالي أو تحته.

يتم تعريف التكوين المحدد بواسطة

${\displaystyle \,C(M)=\{q,\Upsilon _{m}\ldots \Upsilon _{1},x_{1},x_{2}\}\in Q\times (\ddagger \Gamma ^{+})^{*}\times \Sigma ^{*}\times \Sigma ^{*}}$

أين${\displaystyle \,q}$هذا هو الوضع الحالي،${\displaystyle \,\Upsilon }$s هي المكدسات في المكدس المضمن ، مع${\displaystyle \,\Upsilon _{m}}$المكدس الحالي، وبالنسبة لسلسلة الإدخال${\displaystyle \,x=x_{1}x_{2}\in \Sigma ^{*}}$،${\displaystyle \,x_{1}}$هو جزء من السلسلة تمت معالجته بالفعل بواسطة الآلة و${\displaystyle \,x_{2}}$هذا هو الجزء المراد معالجته، ورأسه هو الرمز المقروء حاليًا. لاحظ أن السلسلة الفارغة${\displaystyle \,\epsilon \in \Sigma }$يُعرَّف ضمنيًا على أنه رمز إنهاء، فإذا كانت الآلة في حالة نهائية عند قراءة السلسلة الفارغة، تُقبل سلسلة الإدخال بأكملها ، وإلا تُرفض . وتُعد هذه السلاسل المقبولة عناصر من عناصر اللغة.

${\displaystyle \,L(M)=\left\{x|\{q_{0},\Upsilon _{0},\epsilon ,x\}\rightarrow _{M}^{*}\{q_{\textrm {F}},\Upsilon _{m}\ldots \Upsilon _{1},x,\epsilon \}\right\}}$

أين${\displaystyle \,q_{\textrm {F}}\in Q_{\textrm {F}}}$و${\displaystyle \,\rightarrow _{M}^{*}}$تحدد دالة الانتقال التي يتم تطبيقها عدة مرات حسب الحاجة لتحليل السلسلة.

يمكن أيضًا العثور على وصف غير رسمي لـ EPDA في Joshi, Schabes (1997), ^{[ 3 ]} القسم 7، ص  23-25.

وضع ديفيد ج. وير تصنيفًا أكثر دقة للغات التي تتوافق مع فئة اللغات الحساسة للسياق بشكل طفيف. ^{[ 4 ]} استنادًا إلى عمل نبيل أ. خباز، ^{[ 5 ] [ 6 ]} يُعد تصنيف وير للغات التحكم تصنيفًا احتواءً لمجموعة قابلة للعد من فئات اللغات، حيث يُعرَّف المستوى 1 بأنه خالٍ من السياق، والمستوى 2 هو فئة قواعد النحو المتجاورة الشجرية والقواعد النحوية الثلاث الأخرى.

فيما يلي بعض خصائص لغات المستوى k في التسلسل الهرمي:

• تُصنف اللغات من المستوى k بشكل صحيح ضمن فئة اللغة من المستوى ( k  +  1).
• يمكن تحليل لغات المستوى k في${\displaystyle O(n^{3\cdot 2^{k-1}})}$وقت
• يحتوي المستوى k على اللغة${\displaystyle \{a_{1}^{n}\dotso a_{2^{k}}^{n}|n\geq 0\}}$لكن ليس${\displaystyle \{a_{1}^{n}\dotso a_{2^{k+1}}^{n}|n\geq 0\}}$
• يحتوي المستوى k على اللغة${\displaystyle \{w^{2^{k-1}}|w\in \{a,b\}^{*}\}}$لكن ليس${\displaystyle \{w^{2^{k-1}+1}|w\in \{a,b\}^{*}\}}$

تتوافق هذه الخصائص بشكل جيد (على الأقل بالنسبة لـ k  >  1 الصغيرة) مع شروط اللغات الحساسة للسياق بشكل طفيف التي فرضها جوشي، ومع ازدياد قيمة k ، تصبح فئة اللغة، بمعنى ما، أقل حساسية للسياق بشكل طفيف.

• القواعد النحوية الفئوية التوافقية

• لورا كالمير (2010). التحليل النحوي بما يتجاوز قواعد اللغة الخالية من السياق . سبرينغر ساينس آند بيزنس ميديا. ISBN 978-3-642-14846-0.