اليوم: السبت 27 ابريل 2024 , الساعة: 2:19 م
لم يعلق احد حتى الآن .. كن اول من يعلق بالضغط هنا
اخر المشاهدات
- [ وسطاء عقاريين السعودية ] علي حسن سعيد العمري ... الخبر ... المنطقة الشرقية # اخر تحديث اليوم 2024-04-27
- [ أطفال ] سبب نقص الصفائح الدموية عند الأطفال # اخر تحديث اليوم 2024-04-25
- [ تعرٌف على ] ميليسا بينويست # اخر تحديث اليوم 2024-04-27
- [ تعرٌف على ] قائمة قرارات مجلس الأمن التابع للأمم المتحدة لعام 1948 # اخر تحديث اليوم 2024-04-27
- [ بنوك وصرافة الامارات ] صراف آلى مصرف أبوظبي الاسلامي ... دبي # اخر تحديث اليوم 2024-04-27
- [ ظواهر اجتماعية ] 6 أسباب لإنشاء مشروع السد الأخضر # اخر تحديث اليوم 2024-04-27
- [ تعرٌف على ] فريتس شتيدري # اخر تحديث اليوم 2024-04-27
- [ شركات طبية عيادات مستشفيات قطر ] عيادات المستشفى الأمريكية American Hospital Clinics DOHA ... الدوحة # اخر تحديث اليوم 2024-04-27
- [ تأجير سيارات الامارات ] Car Fare Rent A Car LLC # اخر تحديث اليوم 2024-04-27
- [ وسطاء عقاريين السعودية ] يعقوب شجاع عبدالمجيد السندى ... المدينه المنوره ... منطقة المدينة المنورة # اخر تحديث اليوم 2024-04-27
- [ دليل الشارقة الامارات ] قمة الجودة لتجارة الأدوات الرياضية ... الشارقة # اخر تحديث اليوم 2024-04-27
- [ تأجير سيارات الامارات ] Al Jawdah for Cars Rental # اخر تحديث اليوم 2024-04-27
- [ مقاولون الامارات ] يو كيه انفوتيك انترناشيونال # اخر تحديث اليوم 2024-04-27
- [ تعرٌف على ] العلاقات الأرمينية الليسوتوية # اخر تحديث اليوم 2024-04-27
- [ تعرٌف على ] خلية دم حمراء # اخر تحديث اليوم 2024-04-27
- [ أحكام شرعية ] حكم خروج المرأة بعد وفاة زوجها # اخر تحديث اليوم 2024-04-27
- [ مؤسسات البحرين ] شركة فيرست يونيفورمز ذ م م ... المنطقة الشمالية # اخر تحديث اليوم 2024-04-27
- [ وسطاء عقاريين السعودية ] ندى مطلب خضير الحربي ... المدينه المنوره ... منطقة المدينة المنورة # اخر تحديث اليوم 2024-04-27
- [ وسطاء عقاريين السعودية ] ياسر سليمان عبدالله الغفيلي ... الرياض ... منطقة الرياض # اخر تحديث اليوم 2024-04-24
- [ متاجر السعودية ] اركان القهوة ... المجمعة ... منطقة الرياض # اخر تحديث اليوم 2024-04-27
- [ وسطاء عقاريين السعودية ] عبدالله بن سليمان بن محمد الشويمان ... الرياض ... منطقة الرياض # اخر تحديث اليوم 2024-04-27
- [ تعرٌف على ] ذكريات قصر الحمراء # اخر تحديث اليوم 2024-04-27
- [ دليل دبي الامارات ] دبي باركس آند ريزورتس إتش كيو ... دبي # اخر تحديث اليوم 2024-04-27
- [ مستشفيات الامارات ] Medcare Women & Children Hospital # اخر تحديث اليوم 2024-04-27
- [ تعرٌف على ] ماري روكويل هوك # اخر تحديث اليوم 2024-04-27
- [ اعمال النظافة ومعداتها و تجارة قطر ] جوهرة اسيا للضيافة والتنظيفات العامة # اخر تحديث اليوم 2024-04-27
- [ وسطاء عقاريين السعودية ] ثمراء علي فارس الاحمري ... المحاله ... منطقة عسير # اخر تحديث اليوم 2024-04-27
- [ خذها قاعدة ] وبكُل هَشاشتك لا يحقُ لكَ أن تميل لأنّ ثمة من يتَّكئ عليكْ. - شارل بودلير # اخر تحديث اليوم 2024-04-27
- [ أطباق شرقية ] عمل خضار سوتيه # اخر تحديث اليوم 2024-04-27
- [ دليل دبي الامارات ] قمة الطيران ... دبي # اخر تحديث اليوم 2024-04-27
- [ تعرٌف على ] سيم التقسيم # اخر تحديث اليوم 2024-04-27
- [ خدمات قطر ] دليل مستشفيات قطر| مستشفي السدرة # اخر تحديث اليوم 2024-04-27
- الثانوية الدولية ألكسندر دوماس الروابط الخارجية # اخر تحديث اليوم 2024-04-27
- [ دليل رأس الخيمة الامارات ] شركة الكابتن لمقاولات البناء ذ م م. ... راس الخيمة # اخر تحديث اليوم 2024-04-27
- - دكتور رائد ابو الحسن # اخر تحديث اليوم 2024-04-09
- [ مقاهي الامارات ] مقهى ومطعم سلطنة Saltanah cafe & restaurant # اخر تحديث اليوم 2024-04-27
- [ العناية بالشعر ] أضرار عصير البصل للشعر # اخر تحديث اليوم 2024-04-27
- [ مؤسسات البحرين ] جومو كوفي روسترس ذ.م.م ... منامة # اخر تحديث اليوم 2024-04-27
- [ تعرٌف على ] صوفتي # اخر تحديث اليوم 2024-04-27
- [ تأجير سيارات الامارات ] Rent Supercar Dubai # اخر تحديث اليوم 2024-04-27
- [ وسطاء عقاريين السعودية ] حمدان بن دخيل الله بن مبارك الغامدي ... الباحة ... منطقة الباحة # اخر تحديث اليوم 2024-04-27
- [ مستوصفات وعيادات السعودية ] مجمع دواء الجنوب الطبي # اخر تحديث اليوم 2024-04-27
- [ تعرٌف على ] العلاقات البريطانية المغربية # اخر تحديث اليوم 2024-04-27
- [ تعرٌف على ] بولاكيشين الثاني # اخر تحديث اليوم 2024-04-27
- [ تعرٌف على ] مهمة مستحيلة: أمة مارقة # اخر تحديث اليوم 2024-04-27
- [ وسطاء عقاريين السعودية ] تركي مشرع جفين الزيادي ... الرياض ... منطقة الرياض # اخر تحديث اليوم 2024-04-07
- [ تأجير سيارات الامارات ] Rent a Car in Dubai # اخر تحديث اليوم 2024-04-27
- [ تعرٌف على ] قائمة ملوك أراغون # اخر تحديث اليوم 2024-04-27
- [ منوعات اجتماعية ] 5 نقاط أساسية عن أهمية الوقت # اخر تحديث اليوم 2024-04-27
- [ تغذية الطفل ] أضرار الرضاعة الصناعية # اخر تحديث اليوم 2024-04-27
- [ كيف أهتم بطفلي ] علاج ارتفاع درجة حرارة الجسم عند الأطفال # اخر تحديث اليوم 2024-04-27
- [ فوائد الفيتامينات والمعادن ] فوائد فيتامين هـ للحمل # اخر تحديث اليوم 2024-04-27
- [ محامين السعودية ] المها حماد ناصر القريني ... الرياض # اخر تحديث اليوم 2024-04-27
- [ تعرٌف على ] مدرسة دبي البريطانية # اخر تحديث اليوم 2024-04-27
- [ محامين السعودية ] حنان حسين محمد محزري ... الرياض # اخر تحديث اليوم 2024-04-27
- [ تنمية المهارات ] 6 عوامل رئيسية لمهارات التفكير عند الإنسان # اخر تحديث اليوم 2024-04-27
- [ تعرٌف على ] العلاقات البيروفية الليسوتوية # اخر تحديث اليوم 2024-04-27
- [ تعرٌف على ] لوفتهانزا # اخر تحديث اليوم 2024-04-27
- [ تعرٌف على ] العلاقات الأوكرانية العراقية # اخر تحديث اليوم 2024-04-27
- [ مؤسسات البحرين ] رضيه يوسف غلوم عباس ... المنطقة الجنوبية # اخر تحديث اليوم 2024-04-27
- [ شركات طبية عيادات مستشفيات قطر ] مركز بريميوم الطبي Premium ... الدوحة # اخر تحديث اليوم 2024-04-27
- [ دليل دبي الامارات ] بوديوركس توتال للياقة البدنية والعافية ... دبي # اخر تحديث اليوم 2024-04-27
- [ مؤسسات البحرين ] كاريبو كوفي ... المحرق # اخر تحديث اليوم 2024-04-27
- [ صحة وطب الامارات ] مركز جلو للطب و الأسنان ذ.م.م. ... دبي # اخر تحديث اليوم 2024-04-27
- [ مقاهي الامارات ] Hard Rock Cafe DXB # اخر تحديث اليوم 2024-04-27
- [ الخدمات و الخياطة والتطريز قطر ] العبدلي للملابس النسائية والاقمشة والخياطة # اخر تحديث اليوم 2024-04-27
- [ رقم هاتف ] مطعم سبونج بوب في مدينة حمد البحرين وعنوان مطعم اكلات بحرينية وعربية # اخر تحديث اليوم 2024-03-25
- [ دليل دبي الامارات ] فطيرة الوجه ... دبي # اخر تحديث اليوم 2024-04-27
- [ تعرٌف على ] تشكيل الشجر # اخر تحديث اليوم 2024-04-27
- [ جمال ورشاقة الامارات ] جلوريس مركز تجميل ... أبوظبي # اخر تحديث اليوم 2024-04-27
- [ خذها قاعدة ] هي كل نساء العالم أما الحب فأنا أعيشه معها ، أحياه كأنني لم أعرف من قبلها الحب. - نزار قباني # اخر تحديث اليوم 2024-04-27
- [ تعرٌف على ] بلاستيدة خضراء # اخر تحديث اليوم 2024-04-27
- [ خطوط جوية الامارات ] سيف لخدمات الطيران # اخر تحديث اليوم 2024-04-27
- [ خطوط جوية الامارات ] طيران الإمارات # اخر تحديث اليوم 2024-04-27
- [ مستوصفات وعيادات السعودية ] مجمع ركن البطحاء الطبى # اخر تحديث اليوم 2024-04-27
- [ تعرٌف على ] متلازمة ما بعد التجلط # اخر تحديث اليوم 2024-04-27
- [ تعرٌف على ] توم سوفت # اخر تحديث اليوم 2024-04-27
- [ وسطاء عقاريين السعودية ] منير علي فايز الشهري ... الرياض ... منطقة الرياض # اخر تحديث اليوم 2024-04-27
- [ سيارات السعودية ] مجمع ورش مؤسسة عبد الكريم عبد المحسن اللويمى # اخر تحديث اليوم 2024-04-27
- [ تعرٌف على ] العلاقات التشيكية الباكستانية # اخر تحديث اليوم 2024-04-27
- [ دليل دبي الامارات ] غلوريا جينز كوفيز ... دبي # اخر تحديث اليوم 2024-04-27
- [ تعرٌف على ] هيلين إيفانز براون # اخر تحديث اليوم 2024-04-27
- [ سياحة وترفيه الامارات ] سيكس فلاجز دبي باركس آند ريزورتس ... دبي # اخر تحديث اليوم 2024-04-27
- [ تخفيف الوزن ] كيف أضعف في أسبوعين # اخر تحديث اليوم 2024-04-27
- [ رقم تلفون ] طرادة للوازم الخياطة ... البحرين # اخر تحديث اليوم 2024-02-26
- [ المخللات ] طريقة عمل مخلل الزيتون الأخضر # اخر تحديث اليوم 2024-04-27
- [ دليل أبوظبي الامارات ] صالون موون جيلوري للسيدات ... أبوظبي # اخر تحديث اليوم 2024-04-27
- [ مؤسسات البحرين ] موسكو العاصمة لتشييد المباني ... المنطقة الشمالية # اخر تحديث اليوم 2024-04-27
- حلمت اني اتوحم وانا عزباء # اخر تحديث اليوم 2024-02-29
- [ شركات السيارات قطر ] خدمات جاكوار لاند روفر Jaguar Land Rover Service ... الدوحة # اخر تحديث اليوم 2024-04-27
- [ تعرٌف على ] قلعة مكونة # اخر تحديث اليوم 2024-04-25
- [ تعرٌف على ] ماء الوجه # اخر تحديث اليوم 2024-04-27
- [ دليل أبوظبي الامارات ] محل الشجر لقطع غيار السيارات ... أبوظبي # اخر تحديث اليوم 2024-04-27
- [ مؤسسات البحرين ] نيو سكاي ديستريبيوترز ... منامة # اخر تحديث اليوم 2024-04-27
- [ صحة وطب الامارات ] عيادة الأسنان السويدية ... الشارقة # اخر تحديث اليوم 2024-04-27
- [ عقود البناء و المقاولات قطر ] مجموعة النعيمى # اخر تحديث اليوم 2024-04-27
- [ أدعية ] دعاء ليلة الزواج و4 معلومات مهمة عن الزواج # اخر تحديث اليوم 2024-04-27
- [ تخفيف الوزن ] فوائد عصير الأناناس للتخسيس # اخر تحديث اليوم 2024-04-27
- [ مقاهي الامارات ] Café Bubble Shisha Lounge # اخر تحديث اليوم 2024-04-27
- [ تعرٌف على ] جيري براون # اخر تحديث اليوم 2024-04-27
الأكثر قراءة
- مريم الصايغ في سطور
- سؤال و جواب | ما هى أسباب نزول الدم الاحمر بعد البراز؟ وهل هناك أسباب مرضية؟ وما الحل ؟
- سؤال وجواب | هل يجوز للرجل حلق شعر المؤخرة؟ وهل هناك طريقة محددة لذلك ؟
- سؤال و جواب | حلق شعر المؤخرة بالكامل و الأرداف ماحكمه شرعاً
- هل للحبة السوداء"حبة البركة "فوائد ؟
- كيف أتخلص من الغازات الكريهة التى تخرج مني باستمرار؟
- هناك ألم عندى فى الجانب الأيسر للظهر فهل من الممكن أن يكون بسبب الكلى ؟
- هل هناك علاج للصداع الئى أانيه فى الجانب الأيسر من الدماغ مع العين اليسرى ؟
- تعرٌف على ... مريم فايق الصايغ | مشاهير
- تفسير حلم رؤية القضيب أو العضو الذكري في المنام لابن سيرين
- مبادرة لدعم ترشيح رجل السلام صاحب السمو الشيخ محمد بن زايد لجائزة «نوبل للسلام»
- [ رقم تلفون ] مستر مندوب ... مع اللوكيشن المملكه العربية السعودية
- أرقام طوارئ الكهرباء بالمملكة العربية السعودية
- الفضاء اللوني (ص ش ض) و (ص ش ق) الاستخدام
- ارقام وهواتف مستشفى الدمرداش عباسية,بالقاهرة
- طرق الاجهاض المنزلية و ماهى افضل ادوية للاجهاض السريع واسقاط الجنين فى الشهر الاول
- تفسير رؤية لبس البدلة في المنام لابن سيرين
- تفسير حلم رؤية النكاح والجماع في المنام لابن سيرين
- [رقم هاتف] مؤسسة قرض الحسن .. لبنان
- نزع شوك السمك في المنام
- عبارات ترحيب قصيرة 40 من أجمل عبارات ترحيب للأحباب والأصدقاء 2021
- رؤية طفل بعيون خضراء في المنام
- ارقام وهواتف عيادة د. فاروق قورة - 3 أ ش يوسف الجندى باب اللوق بالقاهرة
- الحصول على رخصة بسطة في سوق الجمعة بدولة الكويت
- معلومات هامة عن سلالة دجاج الجميزة
- ارقام وهواتف مستشفى الهلال الاحمر 34 ش رمسيس وسط البلد بالقاهرة
- جريمة قتل آمنة الخالدي تفاصيل الجريمة
- رسائل حب ساخنة للمتزوجين +18
- خليفة بخيت الفلاسي حياته
- تعرٌف على ... عائشة العتيبي | مشاهير
- هل توجيه الشطاف للمنطقة الحساسة يعد عادة سرية؟ وهل يؤثر على البكارة؟
- رقم هاتف مكتب النائب العام وكيفية تقديم بلاغ للنائب العام
- [ رقم تلفون و لوكيشن ] شركة متجر كل شششي - المملكه العربية السعودية
- تفسير رؤية شخص اسمه محمد في المنام لابن سيرين
- ارقام وهواتف مطعم الشبراوى 33 ش احمد عرابى المهندسين, بالجيزة
- أسعار الولادة في مستشفيات الإسكندرية
- ارقام وهواتف عيادة د. هشام عبد الغنى - 10 ش مراد الجيزة بالجيزة
- ارقام وهواتف عيادة د. ياسر المليجى - 139 ش التحرير الدقى بالجيزة
- ارقام وهواتف مستشفى النور المحمدى الخيرى التخصصى المطرية, بالقاهرة
- تفسير رؤية الحشرات في المنام لابن سيرين
- [رقم هاتف] مؤسسة مركز اصلاح وتأهيل بيرين .. بالاردن الهاشمية
- قسم رقم 8 (فلم) قصة الفلم
- تفسير حلم رؤية الميت يشكو من ضرسه في المنام
- هل أستطيع الاستحمام بعد فض غشاء البكارة ليلة الدخلة مباشرة؟
- أعشاب تفتح الرحم للإجهاض
- يخرج المني بلون بني قريب من لون الدم، فما نصيحتكم؟!
- قناة تمازيغت برامج القناة
- ارقام وهواتف مكتب صحة - السادس من اكتوبر ميدان الحصرى السادس من اكتوبر, بالجيزة
- سور القران لكل شهر من شهور الحمل
- تفسير رؤية براز الكلاب في المنام لابن سيرين
- زخرفة اسماء تصلح للفيس بوك
- مدرسة ب/ 141 حكومي للبنات بجدة
- إلغ (برمجية) التاريخ
- [ رقم هاتف ] جمعية قرض الحسن، .... لبنان
- أشيقر سكان وقبائل بلدة أشيقر
- تفسير حلم رؤية قلب الخروف في المنام
- تفسير حلم الكلب لابن سيرين
- [ رقم هاتف ] عيادة د. حازم ابو النصر - 20 ش عبد العزيز جاويش عابدين بالقاهرة
- انا بنت عندي 13 سنة لسة مجتليش الدورة الشهرية ......كنت ببات عند خالتي وكل ما
- هل تمرير الإصبع بشكل أفقي على فتحة المهبل يؤدي إلى فض غشاء البكارة؟
- [رقم هاتف] شركة الحراسة و التوظيف و التنظيف.. المغرب
- قبيلة الهزازي أقسام قبيلة الهزازي
- ذا إكس فاكتور آرابيا فكرة البرنامج
- السلام عليكم ، أنا مشكلتي بصراحة الجنس من الخلف مع زوجي الأن صار ويحب حيل
- فتحة المهبل لدي واسعة وليست كما تبدو في الصور.. فهل هو أمر طبيعي؟
- لالة لعروسة (برنامج) الفائزون
- أنا حامل في الشهر الرابع وينزل مني دم .. هل هذا طبيعي؟
- [ رقم هاتف ] عيادة د. عادل الريس .. وعنوانها
- هل إدخال إصبع الزوج في مهبل الزوجة له أضرار؟
- تفسير حلم اصلاح الطريق في المنام
- هل الشهوة الجنسية الكثيرة تؤثر على غشاء البكارة؟ أفيدوني
- تفسير حلم تنظيف البيت في المنام للعزباء والمتزوجة والحامل والمطلقة
- إيمان ظاظا حياتها ومشوارها المهني
- أهمية وضرورة إزالة الخيط الأسود من ظهر الجمبري
- اسماء فيس بنات مزخرفة | القاب بنات مزخرفه
- لهجة شمالية (سعودية) بعض كلمات ومفردات اللهجة
- تفسير رؤية المشاهير في المنام لابن سيرين
- هل شد الشفرات والمباعدة الشديدة للساقين يمكن أن تفض غشاء البكارة؟
- [بحث جاهز للطباعة] بحث عن حرب 6 اكتوبر 1973 بالصور pdf doc -
- فوائد عشبة الفلية و الكمية المناسبة يوميا
- تفسير رؤية المخدة في المنام لابن سيرين
- [رقم هاتف] شركة الرفق بالحيوان و الطبيعة.. المغرب
- كلمات - انت روحي - حمود السمه
- أعاني من لحمة زائدة في الدبر ، فلدي قطعة لحمية صغيرة في فتحة الشرج من الخارج
- ما الفرق بين الغشاء السليم وغير السليم؟
- تفسير حلم رؤية الإصابة بالرصاص في الكتف بالمنام
- [ رقم هاتف ] مركز المصطفى للاشعة
- أدخلت إصبعي في المهبل وأخرجته وعليه دم، هل فقدت بكارتي؟
- عمر فروخ
- هل الضغط بالفخذين على الفرج يؤذي غشاء البكارة?
- إدمان الزوج للمواقع الإباحية: المشكلة والأسباب والعلاج
- بسبب حكة قويط للمنطقة الحساسة ونزول الدم، أعيش وسواس فض الغشاء.
- ما تفسير رؤية كلمة كهيعص في المنام
- تظهر عندي حبوب في البظر والشفرتين بين حين وآخر.. هل لها مضاعفات، وما علاجها؟
- طريقة إرجاع حساب الفيس بوك المعطل
- الكرة الحديدية قواعد اللعبة
- تفسير رؤية مدرس الرياضيات في المنام لابن سيرين
- [بحث جاهز للطباعة] بحث عن اللغة العربية والكفايات اللغويه -
- تفسير حلم رؤية الكنز فى المنام لابن سيرين
- كيف أصل إلى النشوة مع زوجي أثناء الإيلاج وليس بيده بعد الجماع؟
روابط تهمك
مرحبا بكم في شبكة بحوث وتقارير ومعلومات
عزيزي زائر شبكة بحوث وتقارير ومعلومات.. تم إعداد وإختيار هذا الموضوع [ تعرٌف على ] أوتومات الدفع السفلي # اخر تحديث اليوم 2024-04-27 فإن كان لديك ملاحظة او توجيه يمكنك مراسلتنا من خلال الخيارات الموجودة بالموضوع.. وكذلك يمكنك زيارة القسم , وهنا نبذه عنها وتصفح المواضيع المتنوعه... آخر تحديث للمعلومات بتاريخ اليوم 24/03/2024
[ تعرٌف على ] أوتومات الدفع السفلي # اخر تحديث اليوم 2024-04-27
آخر تحديث منذ 1 شهر و 4 يوم
2 مشاهدة
تم النشر اليوم 2024-04-27 | أوتومات الدفع السفلي
=
(
Q
,
Δ
,
Γ
,
δ
, q i
n
, A i
n
,
F
)
{\displaystyle {\mathcal {A}}=(Q,\Delta ,\Gamma ,\delta ,q_{in},A_{in},F)} حيث يتحقق:
Q
{\displaystyle Q} هي مجموعة منتهية من الحالات.
Δ
\Delta هي أبجدية المُدخل (أي من اية حروف يمكن أن تتركب سلسلة المُدخل)
Γ
{\displaystyle \Gamma } هي أبجدية المُكدس (يجب أن تحوي حروفا غير تلك التي نستخدمها للمُدخل)
δ
⊆
Q
×
(
Δ
∪
{
λ
}
)
×
Γ
×
Q
× Γ ∗
{\displaystyle \delta \subseteq Q\times (\Delta \cup \{\lambda \})\times \Gamma \times Q\times \Gamma ^{*}} أي انها مجموعة جزئية منتهية ل- Q
×
(
Δ
∪
{
λ
}
)
×
Γ
×
Q
× Γ ∗
{\displaystyle Q\times (\Delta \cup \{\lambda \})\times \Gamma \times Q\times \Gamma ^{*}} ، وتُسمى علاقة الانتقال (transition relation). وكل (
p
,
a
,
A
,
q
,
α
)
∈
δ
{\displaystyle (p,a,A,q,\alpha )\in \delta } تُسمى أمر (أو نقلة) وهو يصف الانتقال من الحالة p
{\displaystyle p} للحالة q
{\displaystyle q} في حين أنَّ a
a هو الحرف التالي من المُدخل و- A
{\displaystyle A} هو الرمز الواقع في أعلى المُكدس. والتغيير يتحقق بقراءة الحرف a
a وإخراج A
{\displaystyle A} من المُكدس واحلال α
{\displaystyle \alpha } مكانه في المُكدس.
الحالة الابتدائية
q i
n
∈
Q
{\displaystyle q_{in}\in Q}
رمز المُكدس الابتدائي
A i
n
∈
Γ
{\displaystyle A_{in}\in \Gamma }
F
⊆
Q
{\displaystyle F\subseteq Q} مجموعة الحالات النهائية.
ملاحظات: يمكن اعتبار δ
{\displaystyle \delta } دالة من المجموعة Q
×
(
Δ
∪
{
λ
}
)
×
Γ
{\displaystyle Q\times (\Delta \cup \{\lambda \})\times \Gamma } لمجموعة جزئية ل- Q
× Γ ∗
{\displaystyle Q\times \Gamma ^{*}} حينها يمكننا ان نكتب: (
q
,
α
)
∈
δ
(
p
,
a
,
A
)
{\displaystyle (q,\alpha )\in \delta (p,a,A)} .
نرمز ب-
Γ ∗
{\displaystyle \Gamma ^{*}} مجموعة كل السلاسل (أو الكلمات) التي تتركب من المجموعة Γ
{\displaystyle \Gamma } وكذا الأمر ل-
Δ ∗
{\displaystyle \Delta ^{*}} .
صورة فورية
صورة فورية (configuration) لأوتومات الدفع السفلي A
{\displaystyle {\mathcal {A}}} مُكونة من حروف المُدخل التي لم يتم قراءتها بعد والحالة الحالية والمحتوى الحالي للمُكَّدس أي انه مجموعة الصور الفورية هي مجموعة جزئية ل-
Δ ∗
×
Q
×
Γ
{\displaystyle \Delta ^{*}\times Q\times \Gamma } . علاقة الخطوة
دالة الانتقال δ
\delta يمكننا بواسطتها تعريف علاقة الخطوة،
⊢
A {\displaystyle \vdash _{\mathcal {A}}} ، والعلاقة مُعرفة على مجموعة الصور الفورية: (
a
x
,
p
,
A
γ
) ⊢
A (
x
,
q
,
α
γ
) ⟺ (
p
,
a
,
A
,
q
,
α
)
∈
δ
,
x
∈ Δ ∗
,
γ
∈ Γ ∗
{\displaystyle (ax,p,A\gamma )\vdash _{\mathcal {A}}(x,q,\alpha \gamma )\iff (p,a,A,q,\alpha )\in \delta ,x\in \Delta ^{*},\gamma \in \Gamma ^{*}} من تبعيات هذا التعريف انَّ الأوتومات لا يمكنه المتابعة إذا ما فرغ المُكَدس لانه بكل خطوة عليه إخراج حرف أو رمز من المكدس. حساب
حساب أوتومات ذو مكدس هو متتالية خطوات متلاحقة، وعلاقة الحساب هي المنغلق الانعكاسي والمتعدي،
⊢
A ∗
{\displaystyle \vdash _{\mathcal {A}}^{*}} ، لعلاقة الخطوة.
من وجهة نظر عملية أوتومات الدفع السفلي بصورته هذه لا يُعتبر مفيدا لتمييز اللغات أو حتى للتحليل النحوي (parsing)، وذلك لانه ليس قطعيا أي انه في كل خطوة عليه ان يتحزر الصواب ويسلك طريقه. وخلافا لاتومات الحالات المنتهية فان أوتومات الدفع السفلي القطعي لا ينتج كل لغة حرة السياق أي انه ليس موديل لهذه اللغات كما هو الحال مع القواعد حرة السياق وكذا أوتومات الدفع السفلي غير القطعي. تعريف
أوتومات الدفع السفلي A
=
(
Q
,
Δ
,
Γ
,
δ
, q i
n
, A i
n
,
F
)
{\displaystyle {\mathcal {A}}=(Q,\Delta ,\Gamma ,\delta ,q_{in},A_{in},F)} قطعي إذا تحقق التالي: لكل p
∈
Q
{\displaystyle p\in Q} ، كل a
∈
Δ
{\displaystyle a\in \Delta } وايضا كل A
∈
Γ
{\displaystyle A\in \Gamma } , δ
\delta لا تحوي التعليم (instruction) (
p
,
λ
,
A
,
q
,
α
)
{\displaystyle (p,\lambda ,A,q,\alpha )} وكذلك التعليم (
p
,
a
,
A
, q
′ , α
′ )
{\displaystyle (p,a,A,q',\alpha ')}
لكل p
∈
Q
{\displaystyle p\in Q} ، ولكل a
∈
Δ
∪
{
λ
}
{\displaystyle a\in \Delta \cup \{\lambda \}} ولكل A
∈
Γ
{\displaystyle A\in \Gamma } يوجد في δ
\delta على الأكثر تعليم واحد (
p
,
a
,
A
,
q
,
α
)
{\displaystyle (p,a,A,q,\alpha )} .
ملاحظة: لاحظ انه مسموح تواجد التعليمين (
p
,
λ
,
A
,
q
,
α
)
,
(
p
,
a
, A
′ , q
′ , α
′ )
{\displaystyle (p,\lambda ,A,q,\alpha )\ ,\ (p,a,A',q',\alpha ')} في δ
\delta في حين أن a
≠
λ
{\displaystyle a\neq \lambda } وكذلك A
≠ A
′ {\displaystyle A\neq A'} أي أن الاختيار يكون حسب رأس المكدس العلوي وخلاف هذا الصورتين الفوريتين متساويتين.
لغات الأوتومات القطعي
كما هو الحال مع الأوتومات الدفع السفلي الغير قطعي عندنا طريقتين لتعريف لغة الأوتومات: اما عن طريق الوصول إلى حالة نهائية مع انتهاء المُدخل أو بفراغ المُكدس مع انتهاء المُدخل. اما اللغات من الطريقة الثانية فهي لغات حرة البدايات (prefix free) أي: انَّ هذه اللغات لا تحوي الكلمة أو ايا من بدايتها في نفس الوقت. ولهذا السبب فإن هذه العائلة لا يمكن مقارنتها بعائلة اللغات المنتظمة (regular). وكما كان الحال مع اللغات حرة السياق وعلاقتها بأوتومات الدفع السفلي يمكن أيضا هنا في هذه الحالة قول نفس الشيء بالنسبة لعلاقة اللغات حرة البدايات مع الأوتومات القطعي. أي انه: لغة تُقبل بواسطة أوتومات دفع سفلي قطعي عن طريق فراغ المُكدس فقط إذا هي حرة السياق ويمكن أن تُقبل عن طريق أوتومات دفع سفلي قطعي (ربما اخر) عن طريق الوصول لحالة نهائية (وهذا يعني انه ليس كل لغة تُقبل عن الحالة النهائية يمكن أيضا أن تقبل عن طريق فراغ المُكدس لذا فالشرط أن اللغة حرة البدايات ضروري). قواعد حرة السياق قطعية
وهي مجموعة اللغات التي تُقبل بواسطة أوتومات دفع سفلي قطعي عن طريق الوصول لحالة نهائية. ولها يُرمز DCF . وهذه المجموعة تحوي مجموعة اللغات النظامية (regular languages) على أنها مجموعة جزئية فعلية أي R
E
G
⊂
D
C
F
{\displaystyle REG\subset DCF} ، وهذا لان الأوتومات ذو الحالات النهائية القطعي يمكن النظر إليه على أنه أوتومات دفع سفلي قطعي يتجاهل المُكدس، وكذلك يمكن بناء أوتومات دفع سفلي قطعي بسهولة للغة غير النظامية { a n
b a n | n
>
1
}
{\displaystyle \{a^{n}ba^{n}|n>1\}} . مجموعة اللغات حرة السياق (يُرمز لها CF) تحوي هذه المجموعة فعليا أي: D
C
F
⊂
C
F
{\displaystyle DCF\subset CF} .
PDA يقبل المدخل إذا حسابه على المُدخل بداية من الحالة الابتدائية مع وجود رمز المُكدس الابتدائي وتمام قراءة المُدخل واحد الامرين التاليين يتحقق: ينتهي الأمر بحالةٍ نهائية.
أو ينتهي الأمر بمُكدس فارغ.
بشكل عام هاتان اللغتان، لأوتومات مُعين، ليستا بالضرورة متساويان. لاحظ انه في الحالة الثانية لا يهم أية حالة وقفنا عليها (سواء كانت نهائية أو لا). بناء على ما تقدم سالفا نُعرف اللغتين بالشكل التالي: فليكن A
{\displaystyle {\mathcal {A}}} أوتومات دفع سفلي، نعرف اللغتين التاليتين: لغة الحالة النهائية للأوتومات A
{\displaystyle {\mathcal {A}}} هي: L
(
A
)
=
{
x
∈ Δ ∗ | (
x
, q i
n
, A i
n
) ⊢
A ∗
(
λ
,
q
,
γ
)
for some
q
∈
F
,
γ
∈ Γ ∗
}
{\displaystyle L({\mathcal {A}})=\{x\in \Delta ^{*}|(x,q_{in},A_{in})\vdash _{\mathcal {A}}^{*}(\lambda ,q,\gamma )\ {\mbox{for some}}\ q\in F,\gamma \in \Gamma ^{*}\}}
لغة المُكدس الفارغ للاتومات A
{\displaystyle {\mathcal {A}}} هي: N
(
A
)
=
{
x
∈ Δ ∗ | (
x
, q i
n
, A i
n
) ⊢
A ∗
(
λ
,
q
,
λ
)
for some
q
∈
Q
}
{\displaystyle N({\mathcal {A}})=\{x\in \Delta ^{*}|(x,q_{in},A_{in})\vdash _{\mathcal {A}}^{*}(\lambda ,q,\lambda )\ {\mbox{for some}}\ q\in Q\}}
بشكل عام لا يتحقق التساوي بين اللغتين لكل أوتومات، ولكن يمكن بناء أوتومات اخر بحيث يتحقق التساوي، أي انه يتحقق التالي: فليكن A
{\displaystyle {\mathcal {A}}} أوتومات دفع سفلي حينها يمكننا بناء أوتومات
A
′ {\displaystyle {\mathcal {A}}'} بحيث يتحقق: N
(
A
)
=
L
( A
′ )
{\displaystyle N({\mathcal {A}})=L({\mathcal {A}}')} . وكذا العكس.
فلتكن A , B لغتين اللتين تُمَيَّزَان (recognized) بواسطة اوتماتي الدفع السفلي
M A
, M B
{\displaystyle M_{A},M_{B}} على التوالي. 1. الاتحاد: اللغة A
∪
B
{\displaystyle A\cup B} يمكن أن تُمَيَّز بواسطة أوتومات دفع سفلي
M A
∪
B
{\displaystyle M_{A\cup B}} . بحيث أن
M A
∪
B
{\displaystyle M_{A\cup B}} مركب من الأوتوماتين
M A
, M B
{\displaystyle M_{A},M_{B}} مع إضافة حالة جديدة وفي دالة العبور نضيف لهذه الحالة عبور بواسطة λ
{\displaystyle \lambda } ، كما هو مبين في الصورة.
2. التسلسل: اللغة A
∘
B
{\displaystyle A\circ B} يمكن أن تُمَيَّز بواسطة أوتومات دفع سفلي
M A
∘
B
{\displaystyle M_{A\circ B}} . بحيث أن
M A
∘
B
{\displaystyle M_{A\circ B}} مركب من الأوتوماتين
M A
, M B
{\displaystyle M_{A},M_{B}} ، وفي دالة العبور نضيف عبور بواسطة λ
{\displaystyle \lambda } من مجموعة الحالات النهائية التي في A لبداية B . 3. فلتكن R لغة منظمة (regular language) حينها اللغة A
∩
R
{\displaystyle A\cap R} يمكن تميزها بواسطة أوتومات دفع سفلي. 4. نجمة كليين: اللغة
A ∗
{\displaystyle A^{*}} يمكن أن تُمَيَّز بواسطة أوتومات دفع سفلي
M
A ∗
{\displaystyle M_{A^{*}}} . هذا يُبرهن بواسطة القواعد حرة السياق. 5. مورفزم عكسي: فليكن h
:
Σ
→ Δ ∗
{\displaystyle h:\Sigma \to \Delta ^{*}} مورفزم حينها اللغة:
h −
1
(
A
)
⊆ Σ ∗
{\displaystyle h^{-1}(A)\subseteq \Sigma ^{*}} يمكن أيضا ان تُميز بواسطة أوتومات دفع سفلي.
كل قواعد حر السياق الذي ينتج لغة يمكن تحويله بسهولة إلى أوتومات دفع سفلي يتعرف (recognize) على اللغة عينها. فليكن G
=
(
N
,
T
,
S
,
P
)
{\displaystyle G=(N,T,S,P)} نعرف الأوتومات التالي ذي الحالة الواحدة: A
=
( q ,
T
,
N
∪
T
,
δ
,
q
,
S
,
∅
)
{\displaystyle {\mathcal {A}}=({q},T,N\cup T,\delta ,q,S,\emptyset )} بحيث أنَّ δ
\delta قوانينها كالتالي: (
q
,
λ
,
A
,
q
,
α
)
{\displaystyle (q,\lambda ,A,q,\alpha )} لكل A
→
α
∈
P
{\displaystyle A\to \alpha \in P} . «توسيع»
(
q
,
a
,
a
,
q
,
λ
)
{\displaystyle (q,a,a,q,\lambda )} لكل a
∈
T
{\displaystyle a\in T} . «تطابق»
حسابات A
{\displaystyle {\mathcal {A}}} تقابل الاشتقاقات الأكثر يسارا (leftmost derivations)
⇒ G
,
l
∗
{\displaystyle \Rightarrow _{G,l}^{*}} ل- G ، رسميا: فليكن x
∈ T ∗
{\displaystyle x\in T^{*}} وليكن α
∈
(
N
∪
T ) ∗
{\displaystyle \alpha \in (N\cup T)^{*}} إذا (
x
,
q
,
S
) ⊢
A ∗
(
λ
,
q
,
α
)
{\displaystyle (x,q,S)\vdash _{\mathcal {A}}^{*}(\lambda ,q,\alpha )} حينها يتحقق: S ⇒ G
,
l
∗
x
α
{\displaystyle S\Rightarrow _{G,l}^{*}x\alpha } . كما أن العكس يتحقق لكل α
∈
N
(
N
∪
T ) ∗
∪
{
λ
}
{\displaystyle \alpha \in N(N\cup T)^{*}\cup \{\lambda \}} . حينما نأخذ α
=
λ
{\displaystyle \alpha =\lambda } نجد أن: S ⇒ G
,
l
∗
x
{\displaystyle S\Rightarrow _{G,l}^{*}x} فقط إذا (
x
,
q
,
S
) ⊢
A ∗
(
λ
,
q
,
λ
{\displaystyle (x,q,S)\vdash _{\mathcal {A}}^{*}(\lambda ,q,\lambda } لكل x
∈ T ∗
{\displaystyle x\in T^{*}} ، وهذا يعني أنَّ L
(
G
)
=
N
(
A
)
{\displaystyle L(G)=N({\mathcal {A}})} ، هذا التوافق يُظهر أنَّ الأوتومات ذي الحالة الواحدة (حين الاخذ بالاعتبار لغة المُكدس الفارغ كما سبق تعريفها) مكافئ
للقواعد
حرة
السياق. التكافؤ لا يقف عند هذا الحد إذ أنَّ التكافؤ الكامل بين أوتومات الدفع السفلي وبين القواعد حرة السياق هو تكافؤ شامل وهذه النتيجة توصل إليها كل من نعوم تشومسكي ومارسيل-بوول شوتزنبرجر، وإيفي. والمبرهنة تنص على أن كل لغة تُقبل بواسطة اتومات دفع سفلي سواء اكان ذلك بفراغ المُكدس ام بالوصول إلى حالة نهائية من مجموعة الحالات النهائية، فقط إذا كانت هذه اللغة هي لغة حرة السياق.
في علم الحاسوب، الأوتومات الدفع السفلي أو باختصار "PDA" هو نموذج حاسوبي بسيط يقوم على فكرة بنية البيانات المكدس (stack)، حيث أنه يستخدمه بأنه ذاكرة اضافية يُخزن فيها النتائج غير نهائية ليُعيد استخدامها لاحقا ضمن العمليات المُتاحة لهذا النموذج.[1][2][3] هنالك نوعان من أوتوماتات الدفع السفلي: أوتومات الدفع السفلي القطعي (DPA)، أوتومات الدفع السفلي غير القطعي (PDA). على خلاف النماذج الابسط أوتومات الدفع السفلي غير القطعي «اقوى» من قرينه القطعي، أي يوجد لغات التي يمكن تقريرها بواسطة PDA ولكن ليس بواسطة DPA .
أوتومات الدفع السفلي عمليا هو أوتومات حالات محدودة مُزود بمكدس LIFO أي من يدخل اخرا يخرج أولا، أول من أنتج الPDA's هو Anthony Oettinger في عام 1963 وقد كان المُكَّدس مستخدماً منذ زمن طويل، إلا أن أبحاثه نَظَّمت دمجه في أوتومات منتهي.ولعل أحد أهم المبرهنات في هذا المجال هي: لكل PDA يمكن بناء قواعد حرة السياق تنتج نفس اللغة. أهمية هذا الأوتومات تتبين من حقيقة انه يُستخدم كثيرا في عملية التجزئة (parsing) وخاصة انه أسهل للبرمجة من القواعد حرة السياق وقد تبين انهما ذوي قوة مضارعة.
تعريف
أوتومات الدفع السفلي هو السباعية: A=
(
Q
,
Δ
,
Γ
,
δ
, q i
n
, A i
n
,
F
)
{\displaystyle {\mathcal {A}}=(Q,\Delta ,\Gamma ,\delta ,q_{in},A_{in},F)} حيث يتحقق:
Q
{\displaystyle Q} هي مجموعة منتهية من الحالات.
Δ
\Delta هي أبجدية المُدخل (أي من اية حروف يمكن أن تتركب سلسلة المُدخل)
Γ
{\displaystyle \Gamma } هي أبجدية المُكدس (يجب أن تحوي حروفا غير تلك التي نستخدمها للمُدخل)
δ
⊆
Q
×
(
Δ
∪
{
λ
}
)
×
Γ
×
Q
× Γ ∗
{\displaystyle \delta \subseteq Q\times (\Delta \cup \{\lambda \})\times \Gamma \times Q\times \Gamma ^{*}} أي انها مجموعة جزئية منتهية ل- Q
×
(
Δ
∪
{
λ
}
)
×
Γ
×
Q
× Γ ∗
{\displaystyle Q\times (\Delta \cup \{\lambda \})\times \Gamma \times Q\times \Gamma ^{*}} ، وتُسمى علاقة الانتقال (transition relation). وكل (
p
,
a
,
A
,
q
,
α
)
∈
δ
{\displaystyle (p,a,A,q,\alpha )\in \delta } تُسمى أمر (أو نقلة) وهو يصف الانتقال من الحالة p
{\displaystyle p} للحالة q
{\displaystyle q} في حين أنَّ a
a هو الحرف التالي من المُدخل و- A
{\displaystyle A} هو الرمز الواقع في أعلى المُكدس. والتغيير يتحقق بقراءة الحرف a
a وإخراج A
{\displaystyle A} من المُكدس واحلال α
{\displaystyle \alpha } مكانه في المُكدس.
الحالة الابتدائية
q i
n
∈
Q
{\displaystyle q_{in}\in Q}
رمز المُكدس الابتدائي
A i
n
∈
Γ
{\displaystyle A_{in}\in \Gamma }
F
⊆
Q
{\displaystyle F\subseteq Q} مجموعة الحالات النهائية.
ملاحظات: يمكن اعتبار δ
{\displaystyle \delta } دالة من المجموعة Q
×
(
Δ
∪
{
λ
}
)
×
Γ
{\displaystyle Q\times (\Delta \cup \{\lambda \})\times \Gamma } لمجموعة جزئية ل- Q
× Γ ∗
{\displaystyle Q\times \Gamma ^{*}} حينها يمكننا ان نكتب: (
q
,
α
)
∈
δ
(
p
,
a
,
A
)
{\displaystyle (q,\alpha )\in \delta (p,a,A)} .
نرمز ب-
Γ ∗
{\displaystyle \Gamma ^{*}} مجموعة كل السلاسل (أو الكلمات) التي تتركب من المجموعة Γ
{\displaystyle \Gamma } وكذا الأمر ل-
Δ ∗
{\displaystyle \Delta ^{*}} .
صورة فورية
صورة فورية (configuration) لأوتومات الدفع السفلي A
{\displaystyle {\mathcal {A}}} مُكونة من حروف المُدخل التي لم يتم قراءتها بعد والحالة الحالية والمحتوى الحالي للمُكَّدس أي انه مجموعة الصور الفورية هي مجموعة جزئية ل-
Δ ∗
×
Q
×
Γ
{\displaystyle \Delta ^{*}\times Q\times \Gamma } . علاقة الخطوة
دالة الانتقال δ
\delta يمكننا بواسطتها تعريف علاقة الخطوة،
⊢
A {\displaystyle \vdash _{\mathcal {A}}} ، والعلاقة مُعرفة على مجموعة الصور الفورية: (
a
x
,
p
,
A
γ
) ⊢
A (
x
,
q
,
α
γ
) ⟺ (
p
,
a
,
A
,
q
,
α
)
∈
δ
,
x
∈ Δ ∗
,
γ
∈ Γ ∗
{\displaystyle (ax,p,A\gamma )\vdash _{\mathcal {A}}(x,q,\alpha \gamma )\iff (p,a,A,q,\alpha )\in \delta ,x\in \Delta ^{*},\gamma \in \Gamma ^{*}} من تبعيات هذا التعريف انَّ الأوتومات لا يمكنه المتابعة إذا ما فرغ المُكَدس لانه بكل خطوة عليه إخراج حرف أو رمز من المكدس. حساب
حساب أوتومات ذو مكدس هو متتالية خطوات متلاحقة، وعلاقة الحساب هي المنغلق الانعكاسي والمتعدي،
⊢
A ∗
{\displaystyle \vdash _{\mathcal {A}}^{*}} ، لعلاقة الخطوة.
أوتومات دفع سفلي قطعي
من وجهة نظر عملية أوتومات الدفع السفلي بصورته هذه لا يُعتبر مفيدا لتمييز اللغات أو حتى للتحليل النحوي (parsing)، وذلك لانه ليس قطعيا أي انه في كل خطوة عليه ان يتحزر الصواب ويسلك طريقه. وخلافا لاتومات الحالات المنتهية فان أوتومات الدفع السفلي القطعي لا ينتج كل لغة حرة السياق أي انه ليس موديل لهذه اللغات كما هو الحال مع القواعد حرة السياق وكذا أوتومات الدفع السفلي غير القطعي. تعريف
أوتومات الدفع السفلي A
=
(
Q
,
Δ
,
Γ
,
δ
, q i
n
, A i
n
,
F
)
{\displaystyle {\mathcal {A}}=(Q,\Delta ,\Gamma ,\delta ,q_{in},A_{in},F)} قطعي إذا تحقق التالي: لكل p
∈
Q
{\displaystyle p\in Q} ، كل a
∈
Δ
{\displaystyle a\in \Delta } وايضا كل A
∈
Γ
{\displaystyle A\in \Gamma } , δ
\delta لا تحوي التعليم (instruction) (
p
,
λ
,
A
,
q
,
α
)
{\displaystyle (p,\lambda ,A,q,\alpha )} وكذلك التعليم (
p
,
a
,
A
, q
′ , α
′ )
{\displaystyle (p,a,A,q',\alpha ')}
لكل p
∈
Q
{\displaystyle p\in Q} ، ولكل a
∈
Δ
∪
{
λ
}
{\displaystyle a\in \Delta \cup \{\lambda \}} ولكل A
∈
Γ
{\displaystyle A\in \Gamma } يوجد في δ
\delta على الأكثر تعليم واحد (
p
,
a
,
A
,
q
,
α
)
{\displaystyle (p,a,A,q,\alpha )} .
ملاحظة: لاحظ انه مسموح تواجد التعليمين (
p
,
λ
,
A
,
q
,
α
)
,
(
p
,
a
, A
′ , q
′ , α
′ )
{\displaystyle (p,\lambda ,A,q,\alpha )\ ,\ (p,a,A',q',\alpha ')} في δ
\delta في حين أن a
≠
λ
{\displaystyle a\neq \lambda } وكذلك A
≠ A
′ {\displaystyle A\neq A'} أي أن الاختيار يكون حسب رأس المكدس العلوي وخلاف هذا الصورتين الفوريتين متساويتين.
لغات الأوتومات القطعي
كما هو الحال مع الأوتومات الدفع السفلي الغير قطعي عندنا طريقتين لتعريف لغة الأوتومات: اما عن طريق الوصول إلى حالة نهائية مع انتهاء المُدخل أو بفراغ المُكدس مع انتهاء المُدخل. اما اللغات من الطريقة الثانية فهي لغات حرة البدايات (prefix free) أي: انَّ هذه اللغات لا تحوي الكلمة أو ايا من بدايتها في نفس الوقت. ولهذا السبب فإن هذه العائلة لا يمكن مقارنتها بعائلة اللغات المنتظمة (regular). وكما كان الحال مع اللغات حرة السياق وعلاقتها بأوتومات الدفع السفلي يمكن أيضا هنا في هذه الحالة قول نفس الشيء بالنسبة لعلاقة اللغات حرة البدايات مع الأوتومات القطعي. أي انه: لغة تُقبل بواسطة أوتومات دفع سفلي قطعي عن طريق فراغ المُكدس فقط إذا هي حرة السياق ويمكن أن تُقبل عن طريق أوتومات دفع سفلي قطعي (ربما اخر) عن طريق الوصول لحالة نهائية (وهذا يعني انه ليس كل لغة تُقبل عن الحالة النهائية يمكن أيضا أن تقبل عن طريق فراغ المُكدس لذا فالشرط أن اللغة حرة البدايات ضروري). قواعد حرة السياق قطعية
وهي مجموعة اللغات التي تُقبل بواسطة أوتومات دفع سفلي قطعي عن طريق الوصول لحالة نهائية. ولها يُرمز DCF . وهذه المجموعة تحوي مجموعة اللغات النظامية (regular languages) على أنها مجموعة جزئية فعلية أي R
E
G
⊂
D
C
F
{\displaystyle REG\subset DCF} ، وهذا لان الأوتومات ذو الحالات النهائية القطعي يمكن النظر إليه على أنه أوتومات دفع سفلي قطعي يتجاهل المُكدس، وكذلك يمكن بناء أوتومات دفع سفلي قطعي بسهولة للغة غير النظامية { a n
b a n | n
>
1
}
{\displaystyle \{a^{n}ba^{n}|n>1\}} . مجموعة اللغات حرة السياق (يُرمز لها CF) تحوي هذه المجموعة فعليا أي: D
C
F
⊂
C
F
{\displaystyle DCF\subset CF} .
لغة الأوتومات
PDA يقبل المدخل إذا حسابه على المُدخل بداية من الحالة الابتدائية مع وجود رمز المُكدس الابتدائي وتمام قراءة المُدخل واحد الامرين التاليين يتحقق: ينتهي الأمر بحالةٍ نهائية.
أو ينتهي الأمر بمُكدس فارغ.
بشكل عام هاتان اللغتان، لأوتومات مُعين، ليستا بالضرورة متساويان. لاحظ انه في الحالة الثانية لا يهم أية حالة وقفنا عليها (سواء كانت نهائية أو لا). بناء على ما تقدم سالفا نُعرف اللغتين بالشكل التالي: فليكن A
{\displaystyle {\mathcal {A}}} أوتومات دفع سفلي، نعرف اللغتين التاليتين: لغة الحالة النهائية للأوتومات A
{\displaystyle {\mathcal {A}}} هي: L
(
A
)
=
{
x
∈ Δ ∗ | (
x
, q i
n
, A i
n
) ⊢
A ∗
(
λ
,
q
,
γ
)
for some
q
∈
F
,
γ
∈ Γ ∗
}
{\displaystyle L({\mathcal {A}})=\{x\in \Delta ^{*}|(x,q_{in},A_{in})\vdash _{\mathcal {A}}^{*}(\lambda ,q,\gamma )\ {\mbox{for some}}\ q\in F,\gamma \in \Gamma ^{*}\}}
لغة المُكدس الفارغ للاتومات A
{\displaystyle {\mathcal {A}}} هي: N
(
A
)
=
{
x
∈ Δ ∗ | (
x
, q i
n
, A i
n
) ⊢
A ∗
(
λ
,
q
,
λ
)
for some
q
∈
Q
}
{\displaystyle N({\mathcal {A}})=\{x\in \Delta ^{*}|(x,q_{in},A_{in})\vdash _{\mathcal {A}}^{*}(\lambda ,q,\lambda )\ {\mbox{for some}}\ q\in Q\}}
بشكل عام لا يتحقق التساوي بين اللغتين لكل أوتومات، ولكن يمكن بناء أوتومات اخر بحيث يتحقق التساوي، أي انه يتحقق التالي: فليكن A
{\displaystyle {\mathcal {A}}} أوتومات دفع سفلي حينها يمكننا بناء أوتومات
A
′ {\displaystyle {\mathcal {A}}'} بحيث يتحقق: N
(
A
)
=
L
( A
′ )
{\displaystyle N({\mathcal {A}})=L({\mathcal {A}}')} . وكذا العكس.
صفات انغلاق
فلتكن A , B لغتين اللتين تُمَيَّزَان (recognized) بواسطة اوتماتي الدفع السفلي
M A
, M B
{\displaystyle M_{A},M_{B}} على التوالي. 1. الاتحاد: اللغة A
∪
B
{\displaystyle A\cup B} يمكن أن تُمَيَّز بواسطة أوتومات دفع سفلي
M A
∪
B
{\displaystyle M_{A\cup B}} . بحيث أن
M A
∪
B
{\displaystyle M_{A\cup B}} مركب من الأوتوماتين
M A
, M B
{\displaystyle M_{A},M_{B}} مع إضافة حالة جديدة وفي دالة العبور نضيف لهذه الحالة عبور بواسطة λ
{\displaystyle \lambda } ، كما هو مبين في الصورة.
2. التسلسل: اللغة A
∘
B
{\displaystyle A\circ B} يمكن أن تُمَيَّز بواسطة أوتومات دفع سفلي
M A
∘
B
{\displaystyle M_{A\circ B}} . بحيث أن
M A
∘
B
{\displaystyle M_{A\circ B}} مركب من الأوتوماتين
M A
, M B
{\displaystyle M_{A},M_{B}} ، وفي دالة العبور نضيف عبور بواسطة λ
{\displaystyle \lambda } من مجموعة الحالات النهائية التي في A لبداية B . 3. فلتكن R لغة منظمة (regular language) حينها اللغة A
∩
R
{\displaystyle A\cap R} يمكن تميزها بواسطة أوتومات دفع سفلي. 4. نجمة كليين: اللغة
A ∗
{\displaystyle A^{*}} يمكن أن تُمَيَّز بواسطة أوتومات دفع سفلي
M
A ∗
{\displaystyle M_{A^{*}}} . هذا يُبرهن بواسطة القواعد حرة السياق. 5. مورفزم عكسي: فليكن h
:
Σ
→ Δ ∗
{\displaystyle h:\Sigma \to \Delta ^{*}} مورفزم حينها اللغة:
h −
1
(
A
)
⊆ Σ ∗
{\displaystyle h^{-1}(A)\subseteq \Sigma ^{*}} يمكن أيضا ان تُميز بواسطة أوتومات دفع سفلي.
لغات حرة السياق
كل قواعد حر السياق الذي ينتج لغة يمكن تحويله بسهولة إلى أوتومات دفع سفلي يتعرف (recognize) على اللغة عينها. فليكن G
=
(
N
,
T
,
S
,
P
)
{\displaystyle G=(N,T,S,P)} نعرف الأوتومات التالي ذي الحالة الواحدة: A
=
( q ,
T
,
N
∪
T
,
δ
,
q
,
S
,
∅
)
{\displaystyle {\mathcal {A}}=({q},T,N\cup T,\delta ,q,S,\emptyset )} بحيث أنَّ δ
\delta قوانينها كالتالي: (
q
,
λ
,
A
,
q
,
α
)
{\displaystyle (q,\lambda ,A,q,\alpha )} لكل A
→
α
∈
P
{\displaystyle A\to \alpha \in P} . «توسيع»
(
q
,
a
,
a
,
q
,
λ
)
{\displaystyle (q,a,a,q,\lambda )} لكل a
∈
T
{\displaystyle a\in T} . «تطابق»
حسابات A
{\displaystyle {\mathcal {A}}} تقابل الاشتقاقات الأكثر يسارا (leftmost derivations)
⇒ G
,
l
∗
{\displaystyle \Rightarrow _{G,l}^{*}} ل- G ، رسميا: فليكن x
∈ T ∗
{\displaystyle x\in T^{*}} وليكن α
∈
(
N
∪
T ) ∗
{\displaystyle \alpha \in (N\cup T)^{*}} إذا (
x
,
q
,
S
) ⊢
A ∗
(
λ
,
q
,
α
)
{\displaystyle (x,q,S)\vdash _{\mathcal {A}}^{*}(\lambda ,q,\alpha )} حينها يتحقق: S ⇒ G
,
l
∗
x
α
{\displaystyle S\Rightarrow _{G,l}^{*}x\alpha } . كما أن العكس يتحقق لكل α
∈
N
(
N
∪
T ) ∗
∪
{
λ
}
{\displaystyle \alpha \in N(N\cup T)^{*}\cup \{\lambda \}} . حينما نأخذ α
=
λ
{\displaystyle \alpha =\lambda } نجد أن: S ⇒ G
,
l
∗
x
{\displaystyle S\Rightarrow _{G,l}^{*}x} فقط إذا (
x
,
q
,
S
) ⊢
A ∗
(
λ
,
q
,
λ
{\displaystyle (x,q,S)\vdash _{\mathcal {A}}^{*}(\lambda ,q,\lambda } لكل x
∈ T ∗
{\displaystyle x\in T^{*}} ، وهذا يعني أنَّ L
(
G
)
=
N
(
A
)
{\displaystyle L(G)=N({\mathcal {A}})} ، هذا التوافق يُظهر أنَّ الأوتومات ذي الحالة الواحدة (حين الاخذ بالاعتبار لغة المُكدس الفارغ كما سبق تعريفها) مكافئ
للقواعد
حرة
السياق. التكافؤ لا يقف عند هذا الحد إذ أنَّ التكافؤ الكامل بين أوتومات الدفع السفلي وبين القواعد حرة السياق هو تكافؤ شامل وهذه النتيجة توصل إليها كل من نعوم تشومسكي ومارسيل-بوول شوتزنبرجر، وإيفي. والمبرهنة تنص على أن كل لغة تُقبل بواسطة اتومات دفع سفلي سواء اكان ذلك بفراغ المُكدس ام بالوصول إلى حالة نهائية من مجموعة الحالات النهائية، فقط إذا كانت هذه اللغة هي لغة حرة السياق.
شرح مبسط
في علم الحاسوب، الأوتومات الدفع السفلي أو باختصار "PDA" هو نموذج حاسوبي بسيط يقوم على فكرة بنية البيانات المكدس (stack)، حيث أنه يستخدمه بأنه ذاكرة اضافية يُخزن فيها النتائج غير نهائية ليُعيد استخدامها لاحقا ضمن العمليات المُتاحة لهذا النموذج.[1][2][3] هنالك نوعان من أوتوماتات الدفع السفلي: أوتومات الدفع السفلي القطعي (DPA)، أوتومات الدفع السفلي غير القطعي (PDA). على خلاف النماذج الابسط أوتومات الدفع السفلي غير القطعي «اقوى» من قرينه القطعي، أي يوجد لغات التي يمكن تقريرها بواسطة PDA ولكن ليس بواسطة DPA .
أوتومات الدفع السفلي عمليا هو أوتومات حالات محدودة مُزود بمكدس LIFO أي من يدخل اخرا يخرج أولا، أول من أنتج الPDA's هو Anthony Oettinger في عام 1963 وقد كان المُكَّدس مستخدماً منذ زمن طويل، إلا أن أبحاثه نَظَّمت دمجه في أوتومات منتهي.ولعل أحد أهم المبرهنات في هذا المجال هي: لكل PDA يمكن بناء قواعد حرة السياق تنتج نفس اللغة. أهمية هذا الأوتومات تتبين من حقيقة انه يُستخدم كثيرا في عملية التجزئة (parsing) وخاصة انه أسهل للبرمجة من القواعد حرة السياق وقد تبين انهما ذوي قوة مضارعة.
شاركنا رأيك
التعليقات
لم يعلق احد حتى الآن .. كن اول من يعلق بالضغط هنا
أقسام شبكة بحوث وتقارير ومعلومات عملت لخدمة الزائر ليسهل عليه تصفح الموقع بسلاسة وأخذ المعلومات تصفح هذا الموضوع [ تعرٌف على ] أوتومات الدفع السفلي # اخر تحديث اليوم 2024-04-27 ويمكنك مراسلتنا في حال الملاحظات او التعديل او الإضافة او طلب حذف الموضوع ...آخر تعديل اليوم 24/03/2024
اعلانات العرب الآن