مرجع
آخر الزيارات

نموذج تشومسكي الطبيعي

576 كلمة•0 مشاهدة•🗒️ منذ 11 يوماً
باختصار: صيغة تشومسكي العادية تسمى اللغة الخالية من السياق في علوم الحاسب الآلي بأنها صيغة تشومسكي العادية (Chomsky normal form)، إذا كانت كافة قواعد إنتاجها على الصيغة: أو أو حيث , و رموزا تمثل قيمة متغيرة، بينما رمزا α يمثل قيمة ثابتة، و S رمز…. في هذه المقالة 9 أقسام: «أدخل S0»، «نحذف كل قاعده فيها B على اليمين» و«فيديو» وغيرها.
المحتويات
  1. أدخل S0
  2. نحذف كل قاعده فيها B على اليمين
  3. فيديو
  4. أو
  5. أو
  6. لحذف
  7. صيغة تشومسكي العادية
  8. تعريف بديل
  9. احذف كافة قواعد الوحدة
نموذج تشومسكي الطبيعي

أدخل S0

قم بحذف أية قاعدة تكون على يمينها. لكل قاعدة تكون على يمينها قم بإضافة مجموعة من القواعد الجديدة التي تتألف من التجميعات المختلفة الممكنة لـ والتي أبدلت أو لم تبدل بـ . إذا كان لقاعدة A على يمينها، قم بإضافة قاعدة جديدة ، ما لم تكن R قد حذفت بالفعل في هذه العملية. فمثلا، أدرس المثال التالي:

وفي هذا الصدد، قم بحذف جميع القواعد القواعد هي قواعد على الصيغة ، حيث و ، بينما V متغير نحر خالي من السياق CFG.

فيما سبق قاعدة واحدة. وعندما نحذف، نحصل على التالي:

وفي هذا السياق، أدخل متغير بداية جديد ، وقاعدة جديدة ، حيث هي متغير البداية السابق.

ومن جهة أخرى، لاحظ أننا ذكرنا كل احتمالات، وبالتالي ننتهي إلى إضافة 3 قواعد.

نحذف كل قاعده فيها B على اليمين

نضور على كل قاعده فيها B على اليسار ونضيف لها A على اليسار

فيديو

من جانب آخر، شرح مادة نظرية الحوسبة والأتوماتا (اللغات والنحو في هرمية تشومسكي Chomsky ) Theory of Automata

أو

كذلك، حيث A B C رموز لقيم متغيرة و α رمز لقيمة ثابتة. وباستخدام هذا التعريف قد يكون B و C رمز بداية.

تحويل لغة إلى صيغة تشومسكي العادية

أو

وفي السياق ذاته، كل لغة بصيغة تشومسكي العادية خالية من السياق، وبالعكس يمكن تحويل كل لغة خالية من السياق إلى لغة بصيغة تشومسكي العادية. وهناك عدة لوغريتمات معروفة للقيام بمثل هذا التحويل. وتوصف التحويلات في أغلب الكتب الدراسية المتخصصة في نظرية الأتمتة، ومنها كتاب هوبكروفت وأولمان (Hopcroft and Ullman, 1979). وكما بيّن لانغ ولايس، فإن العيب في هذه التحويلات هو أنها قد تؤدي إلى مط غير مرغوب في حجم اللغة. وباستخدام – G – للرمز إلى حجم اللغة الأصلية G، فإن حجم المط في أسوأ الحالات قد يتراوح ما بين – G – 2 إلى 22 – G – ، تبعاً للتحول في اللوغاريتم المستعمل (Lange and Leiß, 2009).

ومن جهة أخرى، حيث , و رموزا تمثل قيمة متغيرة، بينما رمزا α يمثل قيمة ثابتة، و S رمز بداية، و ε حقل فارغ. كما أن B أو C لا يمكن أن يمثلا رمز بداية.

لحذف

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

صيغة تشومسكي العادية

أو

كذلك، تسمى اللغة الخالية من السياق في علوم الحاسب الآلي بأنها صيغة تشومسكي العادية (Chomsky normal form)، إذا كانت كافة قواعد إنتاجها على الصيغة:

تعريف بديل

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

وفي هذا الصدد، هناك وسيلة أخرى لتعريف صيغة تشومسكي العادية (Hopcroft and Ullman 1979, and Hopcroft et al. 2006):

احذف كافة قواعد الوحدة

من جهة ثانية، بعد حذف كل قواعد ε، يمكنك أن تبدأ في حذف قواعد الوحدة، أو القواعد التي يحتوي حدها الأيمن على متغير واحد ولا يحتوي رموزاً لقيم ثابتة (وهو ما يتسق مع صيغة تشومسكي العادية).

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.