موقع الو بقاله توصيل الصباحيه - ملاك محل العزيزيه - فطائر قصر الريان المنقف 23731003 - مطعم مندي الريان - يخت جزيرة فيلكا - خالي علي الفودري - Al Rasheedi Abdullah - مطعم كويك ميل المحدود ماما نور سابقا - ابراهيم السوداني علاج الابهر - قاسم ابوفجر - مدربة موضي. ام حبيب - الرومانسيه - جمعية الرميثيه - بلال معلم بلاط - رشيد كهربائي - سالب الرياض - عطار الرسيني ابو عبدالعزيز - بين سبورت . قطر - مطعم هيه صباح الناصر - ظافر مطعم مايدنوس التركي - صالون شعر اثيوبي - ناصر العالول - د. محمد عبدالله جاد عيون أرضي - مذكرات شمس 5 - لا داعي لمدرس خصوصي مع مذكرات #الدرجة_الكاملة تحتوي المذكرة - لينا مساج - فطاير الرابية - مطعم فتوش /جمعيه عبدالله مبارك - مطعم هيا الرقعي - مكتب شيخه ابا الخيل الهندسيه - م هندي جباتي أحمر - سعود البقمي - ا/مبارك الحربي - شيميل المهبوله ريم - بقاله ق1 - عادل الريفي مجبر - د عبد المحسن هادي الحويله - احمد العمودي فوزيه الجفالي - شريف فيزيا - حلويات ناطع حلو ناطع - غازي الشمني - راشد المري بوسالم - فيصل خلف جلعود الجذع - عبدالرحمن التميمي - مطعم مشويات العارضيه - عيادة ابن اليافعي - معرض العنثري شحن - بوعمر حجامة المنقف - ع دكتور طلال عويد المحيسن الشمري - الراقي - فرح البستكي -
الجديد داء البلعمة الأنواع - عزلة الاجعوم (إب) مراجع وروابط خارجية - نظرية المدارات الجزيئية الاتصال بمخططات «MO» المدار الجزيئي والهندسة الجزيئية - مولي افرايم المسيرة الفنية - منصور عزيز حمود الزنداني فترة المجلس - عزلة بني موسى (ذمار) مراجع وروابط خارجية - معركة لودر 2010 طالع أيضا - طنبدي (المنيا) طالع أيضا -
آخر المشاهدات علم النفس الفسيولوجي علم النفس - طريقة تحضير كيك بدون بيض وصفة عجيبة بطريقة سهلة - كيسة جلدانية المكان - هواتف مستشفى عسير المركزي و معلومات عنها بعسير بالسعودية - علوم شرعية أقسام العلوم الشرعية - جزيرة الكنز (فيلم 1990) الملخص - المرازيق (قبيلة) نسب المرازيق - نبذة عن الضمان الاجتماعي في الكويت - طريقة تحضير المصابيب القصيمي بطريقة سهلة - يربوع مصري صغير - علاج القوبــــــاء بالاعشاب - مثبتات للحمل لمن سبق لها الاجهاض المتكرر - بلغازي (قبيلة) النسب - شرف الدين الطوسي سيرته - طريقة تحضير البسبوسه مع الذ صوص بالصور - فيلم قصير تعريف الفيلم القصير - رابونزل (فيلم) أداء الأصوات - [بحث جاهز للطباعة] أهم وأروع بحث علمي عن حقوق الجار - - قائمة منتجات مصر للبترول زيوت مصر للمحركات - تاريخ سكيكدة أصل السكان - التهاب الجلد الهربسي الشكل الأسباب - وقعة البركة المقدمة - [بحث جاهز للطباعة] قوم عاد قوم ثمود قوم لوط قوم فرعون قوم هود - - وصفة هائلة من الطب البديل لعلاج مشاكل الدوره الشهرية و الحيض بالاعشاب - هانسل وغريتل ملخص القصة - أسطورة العشرة بالمئة من قدرة الدماغ الأصل - السندباد البحري رحلات السندباد السبع - فيزا عمل للسعودية ,, شروط واجراءات استخراجها - أدوات التهيئة العمرانية في الجزائر حسب القانون 87-03 المتعلق بالتهيئة العمرانية - الشروط المطلوب استيفاءها للحصول على رخصة تشغيل لشاحنة فردية بالسعودية - ليدز يونايتد تاريخ النادي - صباح الخير يا وطنا (أغنية) كلمات الأغنية - فيروس الورم الحليمي البشري الخصائص العامة - للاستعلام عن رقم هاتف بالكويت عن طريق الانترنت - خطوط طيف الهيدروجين فيزياء - صوفي دي السيرة الذاتية - بندق هندي أسماؤه الشائعة بالعربية - هاتف وعنوان مستوصف المغلوث الطبي - المبرز, الاحساء - القبضاي (مسلسل) قصة المسلسل - طريقة عمل شوربة الخضار بالشوفان مثل المطاعم بدقائق - وصفات الشوربات - اسباب وعلاج التهاب المفاصل الفيروسي عند الدجاج - هاتف وعنوان مطاعم ومطابخ بيت الحنيذ - ينبع - ديكستر (مسلسل) قصة المسلسل - مؤلفات الإمام النووي مؤلفات الإمام النووي - نظام مستضد كيل - هاتف وعنوان مطعم البيت الذهبي - السويدي, مدينة الرياض - سهيلة أندراوس عملية لاندس هوت - لزوجة اللزوجة الحركية للسائل - طريقة عمل السليق الطائفي مثل المطاعم - وصفات اكلات طبخات كويتية - كبرياء وتحامل (رواية) ملخص الأحداث - هواتف و عناوين مكتب الخطوط الجويه العربيه السعوديه في جاكرتا - طريقة تحضير القراقيش المصريه من الشيف منال العالم - تقلصات قوية أسفل البطن في الشهر الخامس من الحمل فما العلاج؟ - طريقة عمل النقانق علي الطريقة اللبنانية من اشهر المطاعم - طريقة تحضير حلى الرخام من كتاب النخبة بطريقة سهلة - مركز دنت كير لطب الاسنان - فوائد نبات اللالوب او تمر العبيد من عيادة العلاج بالاعشاب والطب البديل - طريقة عمل سـاتي الدجـاج بطعم لذيذ لا تفوتك - هاتف وعنوان مستوصف الكرامة الأهلي - النسيم, مدينة الرياض - تطويف بالهواء المنحل التطويف هواء بالهواء الانحلال المنحل (Dissolved air flotation (DAF - بوابة NOR الرموز - قائمة موانئ الجزائر - هواتف وأرقام مجمع العيادة الأولى الحديثةThe First Clinic والعنوان - تلبيسة الاسنان .. هل يمكن ازالة التلبيسه الدائمه؟ - وصفة تساعد على التئام الجروح: بسرعة بخلطات الاعشاب - وصفات تعمل بالمنزل - هواتف الخطوط الجوية العربية السعودية في سلطنة عمان - حفرة تحت الصدغ حدود حفرة تحت الصدغ - وداعا للسلاح (رواية) قصة الرواية - فرق الجهد الفعال التعريف - هاتف وعنوان مستشفى غسان نجيب فرعون - السلامه, جدة - [بحث جاهز للطباعة] بحث علمي جاهز عن الفلسفة - - صاروج الصاروج في سلطنة عمان - هاتف وعنوان مستشفى الصادق - سيهات, الدمام - وصفة هائلة من الطب البديل لعلاج القولون بالاعشاب - طريقة تحضير ساندوتشات الجتني مع الخيار خطوة بخطوة - شروط استخراج بطاقة مدنية كويتية لغير الكويتي - هواتف الخطوط الجوية العربية السعودية في المملكة المغربية - القره بوللي قصرالأخيار( قماطه_ليبيا ) - اختصارات مستخدمة في الوصفات الطبية - عنوان و هواتف سفارة السعودية فى جمهورية السودان ومعلومات شاملة عنها - هاتف وعنوان مطعم نادي المجد - ينبع - الساعة الإستراتيجية لبومان - نظرية التشعب تشعب في ال R^ 1 - عتبة بن الحباب نسبه - تدريب متواتر عالي الكثافة كيفية التمرين - هاتف ومعلومات عن مستوصف زهرة الأمل الطبي 2 بالرياض - منيرة القبيسي أنظر أيضا - وصفة هائلة من الطب البديل لعلاج النتؤات او الثؤلول او الثلول بالاعشاب - طريقة تحضير عجينة العشر دقائق من الشيف منال العالم - وصفة هائلة من الطب البديل لعلاج الأكزيما بالاعشاب - عبيد بن غثيث العنزي السيرة الذاتية - فتحة حمص - آريانوس حياته - سيدني وايت (فيلم) حبكة القصة - قلب الظلام ملخص الرواية - الحقن المجهري بشمال قبرص التركية مركز يورو كاير - مخاطر صاعق الحشرات الكهربائي - علاء الدين (حكاية) ملخص الحكاية - التهاب الشفة السفعي العلامات والأعراض - عبد القادر القصاب سيرة الشاعر - المتممات المجرورة - وصفة هائلة من الطب البديل لعلاج الالتهاب الكيسي والأوتار بالاعشاب - كلية ابن سينا رسوم الكلية - هاتف وعنوان مطبخ المعلمين للحفلات - الهفوف, الاحساء - سور القران لكل شهر من شهور الحمل - متعة الجنس (كتاب) - رف كبريتي - طريقة عمل بتر تشكين من منال العالم - محمد الهراوي الإنتاج الشعري - قائمة المستشفيات في العراق المستشفيات الحكومية - طريقة عمل فيليه السمك بالصلصة البيضاء بطعم جنان - معاهدة تافنة بنود المعاهدة - اشرف سيد احمد الكاردينال مولده ونشاته - [بحث جاهز للطباعة] قائمة بعناوين مشاريع التخرج لتخصص التربية الاسلامية - - هاتف و عنوان مستشفى دومة الجندل العام و معلومات عنها بالجوف بالسعودية - فريديريك فروبل لمحة عن حياته - حاتم جميل مختار نشأته - [بحث جاهز للطباعة] نموذج مقدمة بحث بالانجليزي , نماذج بحوث انجليزي - - - طريقة عمل اكلة الشيشبرك على الطريقة السورية من مطبخ منال العالم - طريقة عمل مقليه أهل الحجاز مع سلطة الكراث+ لقيمات بالصور - شحوح نسب الشحوح - هاتف و معلومات عن مستشفي الدار قباء بالمدينة المنورة - الترمومتر المزدوج المعدني بعض استخداماته الأخرى - كامب (فيلم) القصة - سلسلة باون التفاعلية أساس النظرية - ميزانية و تكاليف ودراسة جدوى مشروع ثلاجات التخزين - كلية الباني الجامعة الأقسام - هاتف وعنوان منجرة علي الشهراني للموبيليا - خميس مشيط, عسير - منشار أنواع المناشير - ميعاد عواد حياتها ومشوارها المهني - مانيتول الاستخدام الصيدلاني - عمود حراري - منوب مبدأ العمل - طريقة عمل رز بالتونة يجنن بطعم لذيذ لا تفوتك - الغرفة الفتية العالمية مبادئ الغرفة واهدافها - كنيسة نوتر دام دي أو تاريخ - يوليوس قيصر (مسرحية) ملخص المسرحية - عنتر بن شداد (فيلم) شخصيات الفيلم - بحثان علميان: التمرينات الرياضية تحمي العين من البقعة الصفراء - جيسي جين الافلام - العامل الوزني - هاتف وعنوان مركز الحبيب للأثاث - عنيزه, القصيم - [بحث جاهز للطباعة] نموذج مقدمة بحث لغة عربية doc , نماذج بحوث عربية doc - - خروب وصف شجرة الخروب - طريقة علاج الشرخ الشرجي في اسبوع واحد بإذن الله - وصفة هائلة من الطب البديل لعلاج التهاب الحنجره التهاب الحلق بالاعشاب - هواتف و معلومات عن جوازات منفذ الحديثة بالسعودية - هاتف وعنوان مطعم بلاد الشام - مشرفه, جدة - [طب بديل ] طرق علاج ضعف الذاكره بالأعشاب الطبية - مواضيع صحية - أشكال سطح الأرض أشكال اليابسة - هاتف وعنوان مستشفى الجدعاني - الصفا, جدة - معلومات هامة عن سلالة دجاج الفيومى - هاتف و معلومات عن فرع وزارة التجارة والصناعة بمكة المكرمة بالسعودية - طريقة تحضير فتة المكدوس بالباذنجان من الشيف منال العالم - شبكة محلية فوائد الشبكات المحلية - علاج الجلطة الدماغية و الشلل النصفي - فلامنكو (موسيقى) أصل الفلامنكو - كشف الأخطاء وتصحيحها التعريفات - [بحث جاهز للطباعة] فهرس حول مظاهر الحياة العقلية في العصر الجاهلي - - المحارمة (قبيلة) ومن ابرز رجالات وشيوخ المحارمة - هاتف ومعلومات عن مطعم الناجي بالرياض - مذكرات طالب (سلسلة) نظرة تاريخية للسلسلة - هاتف وعنوان البراء لأبواب الكراجات الأتوماتيكية - سلطانه, المدينة المنورة - وفورات الحجم تعريف - وصفة هائلة من الطب البديل لعلاج الإسهال والقيء بالاعشاب - محلول منظم الأساس الكيميائي للمحلول المنظم - قانون الكشافة صفات الكشافة - شبه فعل أنواع شبه الفعل - هاتف وعنوان مطبخ النخيل - عوالي, المدينة المنورة - شبرا هارس السكان - [بحث] العصر الحجري القديم - ملخصات وتقارير - هاتف وعنوان مطعم التابل - بريده, القصيم - لانا القسوس حياتها الشخصية - فرط ثنائي أكسيد الكربون في الدم الأسباب - تخفيف (كيمياء) معادلة التخفيف - مطيافية الأشعة السينية المشتتة للطاقة مبدأ العمل - دراسة جدوى مفصلة لمشروع انتاج الزيوت العطرية - أسرة بني نبهان أصل بني نبهان ونسبهم - الكرة الحديدية قواعد اللعبة - كعب بن زهير حياته - علي الطالقاني (الولادة) - ويليام جونسون التعليم - جائزة إمباير لأفضل قادم جديد الفائزون - محاولة عيش كاتب الرواية - سمات الطفل فى سن التسع سنوات - 2016 في السعودية الحكم - متلازمة أوغيلفي السبب - وصفة لعلاج الربو و حساسية الصدر بالاعشاب الطبيعية - فيصل بن لبده نسبه - تادف موجز عن مدينة تادف - قائمة محطات مترو القاهرة الخط الأول - تاريخ الموضة موضات الملابس - مايناسبك وما لا يناسبك في دنيا الموضة - الكرفس اللفتي استخدامات الكرفس في المطبخ - إستديو جونزو أعمال الأستوديو - لغز ليستراد القصص - لوحات تسجيل المركبات في تونس أصناف سلاسل التسجيل في تونس - هواتف وأرقام مستشفى الهلال الأخضر بالسعودية - نظائر النيتروجين نيتروجين-13 -
اليوم: الجمعة 18 اكتوبر 2019 , الساعة: 12:28 م / اسعار صرف العملات ليوم الجمعة 18/10/2019


اعلانات
محرك البحث


اوتومات الدفع السفلي تعريف

آخر تحديث منذ 3 سنة و 1 شهر 60 مشاهدة

شاركنا رأيك بالموضوع

تعريف


اوتومات الدفع السفلي هو السباعية mathcal A (Q,Delta,Gamma,delta,q_ in ,A_ in ,F) حيث يتحقق Pushdown-overview.svg تصغير


  1. Q هي مجموعة منتهية من الحالات .

  2. Delta هي ابجدية المُدخل (اي من اية حروف يمكن ان تتركب سلسلة المُدخل)

  3. Gamma هي ابجدية المُكدس (يجب ان تحوي حروفا غير تلك التي نستخدمها للمُدخل )

  4. delta subseteq Q imes (Delta cup lambda ) imes Gamma imes Q imes Gamma^* اي انها مجموعة جزئية منتهية ل- Q imes (Delta cup lambda ) imes Gamma imes Q imes Gamma^* , وتُسمى علاقة الانتقال (transition relation). وكل (p,a,A,q,alpha)in delta تُسمى أمر (او نقلة) وهو يصف الانتقال من الحالة p للحالة q في حين أنَّ a هو الحرف التالي من المُدخل و- A هو الرمز الواقع في اعلى المُكدس . والتغيير يتحقق بقراءة الحرف a واخراج A من المُكدس واحلال alpha مكانه في المُكدس .

  5. الحالة الابتدائية q_ in in Q

  6. رمز المُكدس الابتدائي A_ in in Gamma

  7. Fsubseteq Q مجموعة الحالات النهائية .



ملاحظات




  1. يمكن اعتبار delta دالة من المجموعة Q imes (Delta cup lambda ) imes Gamma لمجموعة جزئية ل- Q imes Gamma^* حينها يمكننا ان نكتب (q,alpha)in delta(p,a,A) .

  2. نرمز ب- Gamma^* مجموعة كل السلاسل (او الكلمات) التي تتركب من المجموعة Gamma وكذا الامر ل- Delta^* .


صورة فورية


صورة فورية(configuration) لاوتومات الدفع السفلي mathcal A مُكونة من حروف المُدخل التي لم يتم قراءتها بعد والحالة الحالية والمحتوى الحالي للمُكَّدس اي انه مجموعة الصور الفورية هي مجموعة جزئية ل-Delta^* imes Q imes Gamma .

علاقة الخطوة


دالة الانتقال delta يمكننا بواسطتها تعريف علاقة الخطوة , vdash_ mathcal A , والعلاقة مُعرفة على مجموعة الصور الفورية

(ax,p,Agamma) vdash_ mathcal A (x,q,alphagamma) iff (p,a,A,q,alpha)in delta ,xin Delta^* , gammainGamma^*

من تبعيات هذا التعريف انَّ الاوتومات لا يمكنه المتابعة اذا ما فرغ المُكَدس لانه بكل خطوة عليه اخراج حرف او رمز من المكدس .


حساب


حساب اوتومات ذو مكدس هو متتالية خطوات متلاحقة , وعلاقة الحساب هي المنغلق الانعكاسي والمتعدي ,vdash^*_ mathcal A , لعلاقة الخطوة .

لغة الاوتومات


PDA يقبل المدخل اذا حسابه على المُدخل بداية من الحالة الابتدائية مع وجود رمز المُكدس الابتدائي وتمام قراءة المُدخل واحد الامرين التاليين يتحقق



  1. ينتهي الامر بحالةٍ نهائية .

  2. او ينتهي الامر بمُكدس فارغ .



بشكل عام هاتان اللغتان , لاوتومات مُعين , ليستا بالضرورة متساويان . لاحظ انه في الحالة الثانية لا يهم أية حالة وقفنا عليها (سواء كانت نهائية او لا ) .


بناء على ما تقدم سالفا نُعرف اللغتين بالشكل التالي


فليكن mathcal A اوتومات دفع سفلي , نعرف اللغتين التاليتين


  1. لغة الحالة النهائية للاوتومات mathcal A هي L(mathcal A ) xinDelta^* (x,q_ in ,A_ in ) vdash^*_ mathcal A (lambda,q,gamma) mbox for some qin F ,gammain Gamma^*

  2. لغة المُكدس الفارغ للاتومات mathcal A هي N(mathcal A ) xinDelta^* (x,q_ in ,A_ in ) vdash^*_ mathcal A (lambda,q,lambda) mbox for some qin Q



بشكل عام لا يتحقق التساوي بين اللغتين لكل اوتومات , ولكن يمكن بناء اوتومات اخر بحيث يتحقق التساوي , اي انه يتحقق التالي


فليكن mathcal A اوتومات دفع سفلي حينها يمكننا بناء اوتومات mathcal A ' بحيث يتحقق N(mathcal A ) L(mathcal A ') . وكذا العكس .

لغات حرة السياق


كل قواعد حر السياق الذي ينتج لغة يمكن تحويله بسهولة إلى اوتومات دفع سفلي يتعرف (recognize) على اللغة عينها . فليكن G (N,T,S,P) نعرف الاوتومات التالي ذي الحالة الواحدة mathcal A ( q ,T,Ncup T ,delta , q,S, ptyset) بحيث أنَّ delta قوانينها كالتالي




  • (q,lambda,A,q,alpha) لكل A o alphain P . توسيع

  • (q,a,a,q,lambda) لكل ain T . تطابق


حسابات mathcal A تقابل الاشتقاقات الاكثر يسارا ( most derivations) Rightarrow^* _ G,l ل- G , رسميا فليكن xin T^* وليكن alphain (Ncup T)^* اذا (x,q,S)vdash^*_mathcal A (lambda,q,alpha) حينها يتحقق SRightarrow^*_ G,l xalpha . كما ان العكس يتحقق لكل alpha in N (Ncup T)^* cup lambda .

حينما نأخذ alpha lambda نجد أن SRightarrow^* _ G,l x فقط اذا (x,q,S) vdash^*_mathcal A (lambda,q,lambda لكل xin T^* , وهذا يعني أنَّ L(G) N(mathcal A ) , هذا التوافق يُظهر أنَّ الاوتومات ذي الحالة الواحدة (حين الاخذ بالاعتبار لغة المُكدس الفارغ كما سبق تعريفها) مكافئ
للقواعد

حرة

السياق . التكافؤ لا يقف عند هذا الحد إذ أنَّ التكافؤ الكامل بين اوتومات الدفع السفلي وبين القواعد حرة السياق هو تكافؤ شامل وهذه النتيجة توصل اليها كل من نعوم تشومسكي و يل-بوول شوتزنبرجر , وإيفي . والمبرهنة تنص على أن كل لغة تُقبل بواسطة اتومات دفع سفلي سواء اكان ذلك بفراغ المُكدس ام بالوصول إلى حالة نهائية من مجموعة الحالات النهائية , فقط اذا كانت هذه اللغة هي لغة حرة السياق .


صفات انغلاق


فلتكن A , B لغتين اللتين تُمَيَّزَان (recognized) بواسطة اوتماتي الدفع السفلي M_A,M_B على التوالي .

1. الاتحاد اللغة Acup B يمكن أن تُمَيَّز بواسطة اوتومات دفع سفلي M_ Acup B . بحيث أن M_ Acup B مركب من الاوتوماتين M_A,M_B مع اضافة حالة جديدة وفي دالة العبور نضيف لهذه الحالة عبور بواسطة lambda , كما هو مبين في الصورة .
PDA close under union.png 300


2. التسلسل اللغة Acirc B يمكن أن تُمَيَّز بواسطة اوتومات دفع سفلي M_ Acirc B . بحيث أن M_ Acirc B مركب من الاوتوماتين M_A,M_B , وفي دالة العبور نضيف عبور بواسطة lambda من مجموعة الحالات النهائية التي في A لبداية B .

3. فلتكن R لغة منظمة(regular language) حينها اللغة Acap R يمكن تميزها بواسطة اوتومات دفع سفلي .

4. نجمة كليين اللغة A^* يمكن أن تُمَيَّز بواسطة اوتومات دفع سفلي M_ A^* . هذا يُبرهن بواسطة القواعد حرة السياق .

5. تطبيق محافظ على الشكل مورفزم عكسي فليكن h Sigma o Delta^* مورفزم حينها اللغة h^ -1 (A) subseteq Sigma^* يمكن أيضا ان تُميز بواسطة اوتومات دفع سفلي .

اوتومات دفع سفلي قطعي

من وجهة نظر عملية اوتومات الدفع السفلي بصورته هذه لا يُعتبر مفيدا لتمييز اللغات او حتى للتحليل النحوي (parsing) , وذلك لانه ليس قطعيا اي انه في كل خطوة عليه ان يتحزر الصواب ويسلك طريقه . وخلافا لاتومات الحالات المنتهية فان اوتومات الدفع السفلي القطعي لا ينتج كل لغة حرة السياق اي انه ليس موديل لهذه اللغات كما هو الحال مع القواعد حرة السياق وكذا اوتومات الدفع السفلي غير القطعي .

تعريف


اوتومات الدفع السفلي mathcal A (Q,Delta,Gamma,delta,q_ in ,A_ in ,F) قطعي اذا تحقق التالي


  • لكل pin Q , كل ain Delta وايضا كل Ain Gamma , delta لا تحوي التعليم (instruction) (p,lambda,A,q,alpha) وكذلك التعليم (p,a,A,q',alpha')

  • لكل pin Q ,ولكل ain Deltacup lambda ولكل Ain Gamma يوجد في delta على الاكثر تعليم واحد (p,a,A,q,alpha) .



ملاحظة

  • لاحظ انه مسموح تواجد التعليمين (p,lambda,A,q,alpha) , (p,a,A',q',alpha') في delta في حين أن a
    e lambda وكذلك A
    e A' اي أن الاختيار يكون حسب رأس المكدس العلوي وخلاف هذا الصورتين الفوريتين متساويتين .


  • لغات الاوتومات القطعي


    كما هو الحال مع الاوتومات الدفع السفلي الغير قطعي عندنا طريقتين لتعريف لغة الاوتومات اما عن طريق الوصول إلى حالة نهائية مع انتهاء المُدخل او بفراغ المُكدس مع انتهاء المُدخل . اما اللغات من الطريقة الثانية فهي لغات حرة البدايات (prefix free) اي انَّ هذه اللغات لا تحوي الكلمة او ايا من بدايتها في نفس الوقت . ولهذا السبب فإن هذه العائلة لا يمكن مقارنتها بعائلة اللغات المنتظمة (regular) .


    وكما كان الحال مع اللغات حرة السياق وعلاقتها بأوتومات الدفع السفلي يمكن أيضا هنا في هذه الحالة قول نفس الشيء بالنسبة لعلاقة اللغات حرة البدايات مع الاوتومات القطعي . اي انه لغة تُقبل بواسطة اوتومات دفع سفلي قطعي عن طريق فراغ المُكدس فقط اذا هي حرة السياق ويمكن ان تُقبل عن طريق اوتومات دفع سفلي قطعي (ربما اخر) عن طريق الوصول لحالة نهائية (وهذا يعني انه ليس كل لغة تُقبل عن الحالة النهائية يمكن أيضا أن تقبل عن طريق فراغ المُكدس لذا فالشرط أن اللغة حرة البدايات ضروري) .

    قواعد حرة السياق قطعية


    وهي مجموعة اللغات التي تُقبل بواسطة اوتومات دفع سفلي قطعي عن طريق الوصول لحالة نهائية . ولها يُرمز DCF . وهذه المجموعة تحوي مجموعة اللغات النظامية (regular languages) على انها مجموعة جزئية فعلية اي REGsubset DCF , وهذا لان الاوتومات ذو الحالات النهائية القطعي يمكن النظر اليه على انه اوتومات دفع سفلي قطعي يتجاهل المُكدس , وكذلك يمكن بناء اوتومات دفع سفلي قطعي بسهولة للغة غير النظامية a^nba^n n>1 . مجموعة اللغات حرة السياق(يُرمز لها CF) تحوي هذه المجموعة فعليا اي DCFsubset CF .
    في علم الحاسوب , الأوتومات الدفع السفلي او بإختصار PDA هو نموذج حاسوبي بسيط يقوم على فكرة بنية البيانات المكدس (stack) , حيث انه يستخدمه بأنه ذاكرة اضافية يُخزن فيها النتائج غير نهائية ليُعيد استخدامها لاحقا ضمن العمليات المُتاحة لهذا النموذج . هنالك نوعان من اوتوماتات الدفع السفلي اوتومات الدفع السفلي القطعي (DPA) , اوتومات الدفع السفلي غير القطعي (PDA) . على خلاف النماذج الابسط اوتومات الدفع السفلي غير القطعي اقوى من قرينه القطعي , اي يوجد لغات التي يمكن تقريرها بواسطة PDA ولكن ليس بواسطة DPA .


    اوتومات الدفع السفلي عمليا هو اوتومات حالات محدودة مُزود بمكدس LIFO اي من يدخل اخرا يخرج اولا , أول من أنتج الPDA's هو Anthony Oettinger في عام 1963 وقد كان المُكَّدس مستخدماً منذ زمن طويل ، إلا أن أبحاثه نَظَّمت دمجه في أوتومات منتهي .ولعل أحد أهم المبرهنات في هذا المجال هي لكل PDA يمكن بناء قواعد حرة السياق تنتج نفس اللغة . اهمية هذا الاوتومات تتبين من حقيقة انه يُستخدم كثيرا في عملية التجزئة (parsing) وخاصة انه أسهل للبرمجة من القواعد حرة السياق وقد تبين انهما ذوي قوة مضارعة .
     
    التعليقات

    لم يعلق احد حتى الآن .. كن اول من يعلق بالضغط هنا

    تصنيفات الموقع
    شاهد الجديد لهذه المواقع
    بئر السبع ميسوكسيمايد تل هشومير المرجة الزرقاء أسامة بن زيد الغاف دراسة جدوى خطة عمل روبرك الطاقة الداخلية مذكرات دورية نحو الشرق ايو جيما العياضي برباس العياضي شركة مكافحة حشرات خوارزمية ديكسترا مرفأ بيروت الكايد طاش ما طاش شركة كايد البسقلون كورونا سد حراض الفن البيزنطي عبد السلام بنعبد العالي رائد عودة مستشفى طيبة التخصصي غزوة خيبر شركة فواز لعامة للدراسات والمستندات كلوفيس الأول لمع جميل خطاب ويلان نظم المعلومات المحاسبية محمود بن محمود البان باقادر مؤسسة بن شيهون الصحة الصين معلمات اتجاه البطولي أرضروم تنافسية محمد الحاج سالم تكرلي مبرهنة عدم الاكتمال علاج عرق النسا سنهدريم كهربا الحكومة الحكومة التونسية معاهدة فاليتا مستشفي بدر مشاغل مراكز التجميل محمد حافظ الشريدة وديع سعادة مشغل جرافيزم الربان حديقة التجارة نقليات الهباس بن دعجم بطباط حمود بوعلام حميدة معركة ثابسوس براتا البن الاخضر الزكاه ديدفورت تاريخ فواصل الكتب توسعة المسجد النبوي نادي الفتح telnet 1978 عصبام اللوزتين سبيكمان 213 الاقتصاد رمادي عادي فندق العليا تشويه سمعه اسماك الأسماك الجهاز القلبي الوعائي italia قراي سجاد الجامعة السويسرية المفتوحة بيرو هاري فواز الحاتم الفم تمسكنت فتمكنت مقالي سهير أومري