الإنتاج (علوم الحاسب)

من أرابيكا، الموسوعة الحرة
اذهب إلى التنقل اذهب إلى البحث

الإنتاج أو قاعدة الإنتاج (بالإنجليزية: Production)‏ في علم الحاسوب هي قاعدة إعادة كتابة. والتي تصف أو تحدد استبدال أو اشتقاق رمز (على الغالب يكون رمز يمكننا الاشتقاق منه) لأكثر من مرة للوصول إلى جملة مطلوبة. لا ينبغي الخلط بينه وبين نظام الإنتاج (علوم الكمبيوتر).

(P) هي مجموعة منتهية أو محددة  يعتبر  المكون الرئيسي من مكونات القواعد الرسمية (خاصة قواعد اللغة التوليدية). المكونات الأخرى (N) عبارة عن مجموعة منتهية من (nonterminal) رموز القابلة للاشتقاق ومجموعات متفارقة عن N تعرف بال (α)، والرموز الغير قابلة للاشتقاق(terminal) (Σ)، ورمز البداية والذي يعتبر رمز قابل للاشتقاق S ∈ N.

في القواعد غير مقيدة، سيكون الإنتاج في الشكل التالي u → v حيث إن   u و v عبارة عن سلسلة من الرموز القابلة للاشتقاق (α) والغير قابلة للاشتقاق  (Σ ،u) قد لا تكون سلسلة فارغة،  وإذا كانت V  هي سلسلة فارغة هذا يدل رمز ε أو λ. لذا فان الانتاجات هي من أعضاء جداء ديكارتي

V*NV*×V*=(V*Σ)×V*

حيث V:=N ∪ Σ هي مفردات، ∗ هي نجمة كيلين لدلاله على  أن  الرمز إما انه لا يتكرر أبدا أو انه يتكرر مرة أو أكثر من مرة (صفر أو أكثر)  يشير إلى مجموعة من السلسلة و ∪ يدل على اتحاد (نظرية المجموعات). إذا لم نسمح بوضع رمز البداية في v(الكلمة على الجانب الأيمن) سيتطلب منا استبدال *V  بـ *(V ∖ { S }) على الجانب الأيمن من رمز جداء ديكارتي.[1]

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

N(NΣ)*

توليد القواعد

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

SaSb

Sba

على سبيل المثال، افترض أن الأبجدية تتكون من a و b ، مع رمز بداية S ، ولدينا القواعد التالية

نبدأ بـ S عند اختيارنا القاعدة الأولى فاننا سوف نقوم باستبدال S بaSb سوف نحصل على aSb

إذا اخترنا القاعدة 1 مرة أخرى، فإننا نستبدل S بـ aSb ونحصل على السلسلة aaSbb. نكرر هذا العملية إلى ان يتم الوصول إلى سسلسله مكونه من رموز غير قابله للاشتقاق (مثل  aوb), وعند اختيارنا القاعدة الثانية  فاننا سوف نقوم باستبدال S بـba  و سوف نحصل على aababb

باستخدام الرموز SaSbaaSbbaababb لغة القواعد هي مجموعة من كل السلاسل التي يمكن توليدها باستخدام هذه العملية

{ba,abab,aababb,aaababbb}

انظر أيضا

المراجع

  1. ^ Prioritatszahlerautomaten und die Synchronisation von Halbspursprachen نسخة محفوظة 17 يناير 2018 على موقع واي باك مشين.