[ تعرٌف على ] نموذج تشومسكي الطبيعي # اخر تحديث اليوم 2024-04-28

تم النشر اليوم 2024-04-28 | نموذج تشومسكي الطبيعي

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

أدخل S0
أدخل متغير بداية جديد
S 0
{\displaystyle S_{0}} ، وقاعدة جديدة
S 0
→
S
{\displaystyle S_{0}\rightarrow S} ، حيث S
{\displaystyle S} هي متغير البداية السابق.
قم بحذف جميع القواعد ϵ
{\displaystyle \epsilon }
القواعد ϵ
{\displaystyle \epsilon } هي قواعد على الصيغة A
→
ϵ
{\displaystyle A\rightarrow \epsilon } ، حيث A
≠ S 0
{\displaystyle A\not =S_{0}} و A
∈
V
{\displaystyle A\in V} ، بينما V متغير نحر خالي من السياق CFG.
قم بحذف أية قاعدة تكون ϵ
{\displaystyle \epsilon } على يمينها. لكل قاعدة تكون A
{\displaystyle A} على يمينها قم بإضافة مجموعة من القواعد الجديدة التي تتألف من التجميعات المختلفة الممكنة لـ A
{\displaystyle A} والتي أبدلت أو لم تبدل بـ ϵ
{\displaystyle \epsilon } . إذا كان لقاعدة A على يمينها، قم بإضافة قاعدة جديدة R
=
A
→
ϵ
{\displaystyle R=A\rightarrow \epsilon } ، ما لم تكن R قد حذفت بالفعل في هذه العملية. فمثلا، أدرس المثال التالي:
S
→
A
b
A | B
{\displaystyle S\rightarrow AbA|B}
B
→
b | c
{\displaystyle B\rightarrow b|c}
A
→
ϵ
{\displaystyle A\rightarrow \epsilon }
فيما سبق قاعدة واحدة. وعندما نحذف، نحصل على التالي: S
→
A
b
A | A
b | b
A | b | B
{\displaystyle S\rightarrow AbA|Ab|bA|b|B}
B
→
b | c
{\displaystyle B\rightarrow b|c}
لاحظ أننا ذكرنا كل احتمالات، وبالتالي ننتهي إلى إضافة 3 قواعد.
احذف كافة قواعد الوحدة
A
→
B
∋
A
,
B
∈
V
{\displaystyle A\rightarrow B\ni A,B\in V}
بعد حذف كل قواعد ε، يمكنك أن تبدأ في حذف قواعد الوحدة، أو القواعد التي يحتوي حدها الأيمن على متغير واحد ولا يحتوي رموزاً لقيم ثابتة (وهو ما يتسق مع صيغة تشومسكي العادية). نحذف كل قاعده فيها B على اليمين
نضور على كل قاعده فيها B على اليسار ونضيف لها A على اليسار
لحذف A
→
B
{\displaystyle A\rightarrow B}
∀
B
→
U
{\displaystyle \forall B\rightarrow U} أضف القاعدة A
→
U
{\displaystyle A\rightarrow U} ، ما لم تكن قاعدة وحدة تم حذفها بالفعل.
قم بتنقية القواعد المتبقية التي ليست على صيغة تشومسكي العادية
قم باستبدال A
→ u 1
, u 2
,
.
.
. u k
,
k
≥
3
, u 1
∈
V
∪
Σ
{\displaystyle A\rightarrow u_{1},u_{2},...u_{k},k\geq 3,u_{1}\in V\cup \Sigma } بـ A
→ u 1 A 1
, A 1
→ u 2 A 2
,
.
.
.
, A k
−
2
→ u k
−
1 u k
{\displaystyle A\rightarrow u_{1}A_{1},A_{1}\rightarrow u_{2}A_{2},...,A_{k-2}\rightarrow u_{k-1}u_{k}} ، حيث
A i
{\displaystyle A_{i}} متغيرات جديدة.
إذا
u i
∈
Σ
{\displaystyle u_{i}\in \Sigma } ، قم باستبدال
u i
{\displaystyle u_{i}} في القواعد أعلاه بمتغير جديد
v i
{\displaystyle v_{i}} ثم أضف القاعدة
v i
→ u i
{\displaystyle v_{i}\rightarrow u_{i}} .

فيديو

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

تعريف بديل

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

شرح مبسط

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