فهرس |
من المعلوم أن صف اللغات التي تولد بواسطة القواعد الخالية من السياق والمسماة اختصاراCFG أكبر من صف اللغات المعرفة بواسطة التعابير النظامية.هذا يعني أن كل اللغات النظامية يمكن أن تعرف بواسطة قواعد خالية من السياق,وكذلك بعض اللغات ذات التعابير غير النظامية أيضاً.وكذلك فإن لكل لغة نظامية آلية واحدة على الأقل تعمل بنجاح فقط في سلاسل دخل من تلك اللغة .
لذلك فإنه من المفيد جداً لو استطعنا تعريف نمط آلية بدائية تشابه الCFG's نحن بحاجة إلى قبولات اللغة الخالية من السياق بشكل مشابه لقبولات الأوتوماتات النهائية للغة النظامية.ولبناء هذه الآليات الجديدة سوف نبدأ بأوتوماتات منتهية وثم نضيف لها بعض الأدوات الجديدة لنجعلها أكثر قوة.
الخطوة الأولى:
هي تطوير تمثيلات مختلفة للأوتوماتات المنتهية وذلك بتعريف سلسلة الدخل على أنها شريط دخل ذا طول منتهي ويقرأ باتجاه واحد ومحدد ،وبذلك نستطيع التميز بين الدخل الرمز الأول,الثاني..وهكذا.كل رمز يأخذ موقع محدد يسمى خلية ،الرمز¢ يشير إلى خلية فارغة من خلال هذه المعالجة للشريط فإننا سنقرأ فقط رمزاً واحداً في كل مرة ونحذفه إذا مااستهلك من قبل سلسلة الدخل,وبالطبع فإننا لايمكننا العودة إلى الخلف.ويتم التوقف عندما نصل إلى الخلية ¢
وباستخدام هذا التمثيل التصويري للـFA's فنحن بحاجة على الرموز التالية
ومن المهم ملاحظة الفرق بين هذه الحالات وبين الحالات النهائية للأوتومات فنحن نستطيع التنقل بعدد نهائي من الحالات من خلال قراءة رموز الدخل ونصل إلى إحدى الحالات النهائية من خلال رموز القبول,بينما لا نستطيع الخروج مع رموز الرفض.
تعديل أخر للتمثيل التصويري يمكن ان يكون بتمثيل كل تابع منجز في حالة معينة بصندوق الأختبار النمطي المنجز في حالة معينة هو "القراءةRead والتقسيمBranch" والتي يمكن تمثيلها بصندوق على شكل معين كما في الأسفل
لذلك مع هذه الرموز الجديدة يكون الأوتومات المنتهي التالي وتمثيله كما يلي
نلاحظ أن¢ تقود فقط من صناديق القراءة إلى نوع من نصف الحالة والتي تعين نهاية سلسلة الدخل. السبب في تعريف هذا التمثيل الجديد للـFA's هو لسهولة إضافة آلية جديدة مما يعزز أدوات قبول الCFL's .
هذه التقنية الجديدة هي المكدس (Pushdown Stack). وهوالمكان الذي نستطيع تخزين الموز فيه حتى نفاضل بينهم مرة أخرى الدفعPush يضيف رمز جديد إلى المكدس دافعاً كافة الرموز الأخرى إلى الاسفل, أما الاسترجاع Pop يزيل العنصر العلوي من قمة المكدس .وحتى لا نحصل على حالة استرجاع من مكدس فارغ فإننا نهيأ قمة المكدس برمز فراغ مشابه لعمل ¢ .ويمكن غضافة المكس على تمثيلنا على الشكل التالي
عندما تكون الأوتوماتات المنتهية FA's معززة بالمكدسات,ندعوهم بالPDA's(PushDown Automata).أول من أنتج الPDA's هو Anthony Oettinger في عام 1963 المكدس كبنية معطيات كان مستخدماً منذ زمن طويل,إلا أن هذه الأبحاث نظمت دمجه في أوتومات منتهي أدى إلى زيادة سبات وتنظيم لغته بشكل ملحوظ.
لنلاحظ أثر العملية على هذه الألة عندما ندخل السلسلة "aaabbb" .في البداية ندفع 3 a على المكدس وبعدها نقرأ b .نسترجع a التي على قمة المكدس ونقرأ b أخرى وهكذا ..فنلاحظ أننا نقرأ 3 a و3b حتى نواجه ¢ ،والتي تأخذنا إلى عملية استرجاع نهائية . وعندها نسترجع ¢ من قعر المكدس.وبالتالي هذه السلسلة مقبولة.
اللغة المؤلفة من الكلمات المقبولة من هذا الPDA هي {anbn for n=0,1,2,…}
وهذا واضح من حالات القراءة والدفع للمكدس بعد الحالة الابتدائية .
عندما كل الa's تدفع إلى المكدس نكون أمام احتمالين في الشريط:¢ أوb .
إذا كان ¢ عندها سنسترجع العنصر من قمة المكدس .فإن كان هذا العنصر ¢ فإن الشريط كان فارغ منذ البداية ،أما إذا كان العنصر المسترجع هو a فعندها تكون سلسلة الدخل مرفوضة وبالتالي a+ مرفوضة من هذا الPDA الاحتمال الأخر هو أن نقرأ b وهنا يجب علينا أن نسترجع ونقرأ.هذه السلسلة من الحالات تتضمن أن القبول سيكون فقط إذا كان عدد الb's التي
سنقرأها مساوياً لعدد الa's المسترجعة .
وكل الحلات الأخرى يؤدي إلى رفض السلسلة.
هذه هي اللغة,والتي نعلم أنها ليست نظامية.ولذلك فإن الPDA's أكثر فائدة من الFA's .
ذلك أنه يمكن تمثيل أي FA برموز جديدة من الPDA حتى بالنسبة للغات غير النظامية
==مالذي يجعل هذه الأليات أكثر فائدة؟!! بماذا يزود المكدس حقيقةً؟!==
PDA's لها عدد محدد من الحالات نهائية تماماً كما FA ولكنها بالاضافة لذلك تمتلك ذاكرة.ولذلك فهي قادرة على تحديد أين كان العناصر وكم مرة. وعلى سبيل المثال فمن الصعب بناء FA للمثال الذي طرحناه قبل قليل وذلك نظراً لكبر n
وكذلك فإنها لن تكون قادرة على التمييز بين ambn وanbn ذلك أن الa's سوف تدور في دائرة والألة لايمكن أن تحدد مسار لعدد مرات دوراتها .أما PDA فالمكدس سيعمل كذاكرة ،ولكن هل هذه الذاكرة بقوة ذاكرة الكومبيوتر؟!!ليس بعد.
إذاً نحن بحاجة لتطويرات أكثر.
رأينا كيف أن إضافة المكدس يسمح لنا ببناء ألة تقبل لغة مولدة من CFG.ولكن هل هذه الإضافة هي كل ماتحتاجه هذه الآلة لقبول كل اللغات الخالية من السياق CFL's ؟!.
المثال السابق كان PDA محدد ،أي ان كل سلسلة دخل لها مسار وحيد عبر الألة .الأوتومات ذا المكدس غير المحدد أو non-determinstic PDA هو أن يكون لدينا أكثر من خيارعبر عدة مسارات محتملة .ونقول عن سلسلة دخل أنها مقبولة من مثل هذه الآلات إذا ما قادة بعض الخيارات إلى حالة نهائية مقبولة.
والPDA's المساوية للCFG's ماهي إلا صف من نظيراتها غير المحددة.والشكل التالي يوضح ذلك:
فيما يلي مثال على CFLوالتي يمكن قبولها من خلالPDA غير محدد حصراً ولايمكن ذلك من PDA محدد.ODD-PALINDROME هي عبارة عن لغة مشكلة من كل السلاسل المؤلفة من a's وb's والتي يمكن قرأتها من الجهتين ولها عدد فردي من الاحرف. ODD-PALINDROME = {a b aaa aba bab bbb …..} CFG لهذه اللغة هي ذاتها لل PALINDROMEماعدا أننا لن نسمح بالزوجيات
ولكن..
تعتبرPALINDROME من اللغات الصعبة لأن الحرف الأوسط ليس معزول مما يجعل من الصعب(بل ربما من المستحيل) معرفة أين انتهى القسم الأول وأين بدأ القسم الثاني.
PDA(وكذلك FA)يقرأ فقط السلسلة من اليسار إلى اليمين.وليس لديه أية فكرة عن عدد الأحرف المتبقية في السلسلة.ولكن لو كان الحرف الاوسط وليكن "X" معزول فعلاً لكان العمل أسهل بكثيراً.
إذاً لنفترض الألة التالية:
نلاحظ أنها غير محددة طالما أن القراءة من اليسار لها أختيارين للخروج لكل من a,b إذا ماقمنا بالتقسيم في نفس الوقت فإن الآلة ستقبل الكلمة في هذه اللغة وإلا فلا.
ولكن بالعودة إلى تعريف عدم التحديد في PDA :إذا أخترنا الخيار الصحيح,الألة ستقبل. وعلى ذلك فإن علينا ان نجد وضع واحد للاختيار الصحيح فمثلاً الكلمة aba تكون مقبولة من هذه الآلة فقط إذا قررنا أن نقرأ b بدلاً من دفعها إلى المكدس
بشكل عام:الأوتومات ذا المكدس الغير محدد (N-PDA) يتألف من:
شيء أخير يجب توفره وهو ارتباط بين الحالات لتشكيل غراف مترابط ومباشر.
هل كل اللغات هي لغات خالية من السياق؟!! بالطبع لا. مجموعة من CFL's تحوي مجموعة من اللغات النظامية ،ولكن كليهما مجموعات جزئية من مجموعات اكبر.
مثال: ليكن لدينا اللغة {anbnan for n=1,2,3,….}={aba aabbaa aaabbbaaa ……}
لنبحث عن PDA والذي يقبل هذه اللغة.نبدأ بقراءة a's ونحفظ عدد ماقرأناه منها حتى نستطيع مقابلته مع عدد الb's التي سوف نقرأها.وهنا المكدس كما وضحنا سابقاً يستخدم لتسيير هذه المعلومات.هذا العمل جيد حتى الآن بالنسبة للقسم الأول anbn ولكن عندما يأتي الوقت لتحديد الجزء الأخير an سيكون المكدس فارغ ذلك أننا استرجعنا كل الa's بمقابلتها مع الb's ربما يمكننا تجربة طريقة أخرى:من اجل كل a تقرأ من الجزء الأول ،نقوم بدفع 2 a's إلى المكدس.وبعدها عندما نقرأ الb's نقوم بمقابلتها مع نصف عدد الa's ،وعندما نصل على الكتلة الاخيرة an يجب أن يكون لدينا نفس العدد من الa's في المكدس وفي سلسلة الدخل على حد سواء.
ولكن هل ستعمل هذه الفكرة؟!!في الحقيقة نعم ستعمل,ولكن لسوء الحظ فإن هذا الPDA سيقبل أكثر مما تقبله اللغة المخصصة ذاتها.
والسبب في ذلك أننا لانملك طريقة لمعرفة فيما إذا كانت الb's هي نصف عدد الa's في المكدس أم لا.فمثلاً الكلمة a10b8a12 ستكون ايضاً مقبولة من هذا الPDA.
في الحقيقة وبعد بحث طويل في شبكة الانترنت لم نجد أي PDA يقبل هذه اللغة,ولكننا لم نجد مايدل على أن القواعد غير الخالية من السياق لايمكن تمثيلها.
لمزيد من المعلومات : موقع يتحدث عن الاوتومات غير المنتهي ذو المكدس
http://en.wikipedia.org/wiki/Pushdown_automaton
تقديم : راما القدور