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

تصغير|200بك|يسار

صيغة تشومسكي العادية
تسمى اللغة الخالية من السياق في علوم الحاسب الآلي بأنها صيغة تشومسكي العادية (Chomsky normal form)، إذا كانت كافة قواعد إنتاجها على الصيغة:
: A \rightarrow BC أو
: A \rightarrow \alpha أو
: S \rightarrow \varepsilon
  
حيث A, B و C رموزا تمثل قيمة متغيرة، بينما رمزا α يمثل قيمة ثابتة، و S رمز بداية، و ε حقل فارغ. كما أن B أو C لا يمكن أن يمثلا رمز بداية.
كل لغة بصيغة تشومسكي العادية خالية من السياق، وبالعكس يمكن تحويل كل لغة خالية من السياق إلى لغة بصيغة تشومسكي العادية. وهناك عدة لوغريتمات معروفة للقيام بمثل هذا التحويل. وتوصف التحويلات في أغلب الكتب الدراسية المتخصصة في نظرية الأتمتة، ومنها كتاب هوبكروفت وأولمان (Hopcroft and Ullman, 1979). وكما بيّن لانغ ولايس، فإن العيب في هذه التحويلات هو أنها قد تؤدي إلى مط غير مرغوب في حجم اللغة. وباستخدام | G | للرمز إلى حجم اللغة الأصلية G، فإن حجم المط في أسوأ الحالات قد يتراوح ما بين | G | 2 إلى 22 | G | ، تبعاً للتحول في اللوغاريتم المستخدم (Lange and Leiß, 2009).

## تعريف بديل
هناك وسيلة أخرى لتعريف صيغة تشومسكي العادية (Hopcroft and Ullman 1979, and Hopcroft et al. 2006):
تكون اللغة الصورية في صيغة تشومسكي المختزلة إذا كانت كل قواعد إنتاجها على الصيغة:
: A \rightarrow\, BC أو
: A \rightarrow\, \alpha
 
حيث A B C رموز لقيم متغيرة و α رمز لقيمة ثابتة. وباستخدام هذا التعريف قد يكون B و C رمز بداية.

## تحويل لغة إلى صيغة تشومسكي العادية
# أدخل S0
#: أدخل متغير بداية جديد S_0 ، وقاعدة جديدة S_0 \rightarrow S ، حيث S  هي متغير البداية السابق.
# قم بحذف جميع القواعد *<math>\epsilon</math>
#: القواعد *\epsilon هي قواعد على الصيغة A \rightarrow \epsilon ، حيث A \not= S_0 و A \in V ، بينما V متغير نحر خالي من السياق CFG.

#: قم بحذف أية قاعدة تكون \epsilon على يمينها. لكل قاعدة تكون A على يمينها قم بإضافة مجموعة من القواعد الجديدة التي تتألف من التجميعات المختلفة الممكنة لـ A والتي أبدلت أو لم تبدل بـ \epsilon. إذا كان لقاعدة A على يمينها، قم بإضافة قاعدة جديدة R = A \rightarrow \epsilon ، ما لم تكن R قد حذفت بالفعل في هذه العملية. فمثلا، أدرس المثال التالي:
#:: S \rightarrow AbA | B
#:: B \rightarrow b | c
#:: A \rightarrow \epsilon
 
فيما سبق قاعدة واحدة. وعندما نحذف، نحصل على التالي:
#:: S \rightarrow AbA | Ab | bA | b | B
#:: B \rightarrow b | c
 
#: لاحظ أننا ذكرنا كل احتمالات، وبالتالي ننتهي إلى إضافة 3 قواعد.
# احذف كافة قواعد الوحدة
#: A \rightarrow B \ni A,B \in V

بعد حذف كل قواعد ε، يمكنك أن تبدأ في حذف قواعد الوحدة، أو القواعد التي يحتوي حدها الأيمن على متغير واحد ولا يحتوي رموزاً لقيم ثابتة (وهو ما يتسق مع صيغة تشومسكي العادية).
# نحذف كل قاعده فيها B على اليمين
# نضور على كل قاعده فيها B على اليسار ونضيف لها A على اليسار
#:: لحذف A \rightarrow B
#:: \forall B \rightarrow Uأضف القاعدة A \rightarrow U ، ما لم تكن قاعدة وحدة تم حذفها بالفعل.

# قم بتنقية القواعد المتبقية التي ليست على صيغة تشومسكي العادية
قم باستبدال A \rightarrow u_1,u_2, ... u_k, k \ge 3, u_1 \in V \cup \Sigma بـ A \rightarrow u_1 A_1 , A_1 \rightarrow u_2 A_2 , ... , A_{k-2} \rightarrow u_{k-1} u_k ، حيث A_i متغيرات جديدة.
إذا u_i \in \Sigma ، قم باستبدال u_i في القواعد أعلاه بمتغير جديد v_i ثم أضف القاعدة v_i \rightarrow u_i.

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

## مراجع

* John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. *Introduction to Automata Theory, Languages, and Computation*, 3rd Edition, Addison-Wesley, 2006. ISBN 0-321-45536-3. *(See subsection 7.1.5, page 272.)*
* John E. Hopcroft and Jeffrey D. Ullman, *Introduction to Automata Theory, Languages and Computation*, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-02988-X. *(See chapter 4.)*
*  *(Pages 98–101 of section 2.1: context-free grammars. Page 156.)*
*  *(Pages 237–240 of section 6.6: simplified forms and normal forms.)*
*  *(Pages 103–106.)*
* Lange, Martin and Leiß, Hans. *To CNF or not to CNF? An Efficient Yet Presentable Version of the CYK Algorithm.* Informatica Didactica 8, 2009. ((pdf) 
* Cole, Richard. *Converting CFGs to CNF (Chomsky Normal Form)*, October 17, 2007. (pdf)
* Sipser, Michael. *Introduction to the Theory of Computation,* 2nd edition.

تصنيف:لغات شكلية
تصنيف:نعوم تشومسكي