القواعد الرسمية

لنفترض أن لدينا قواعد الإنتاج التالية:

1.${\displaystyle S\rightarrow aSb}$

2.${\displaystyle S\rightarrow ba}$

ثم نبدأ بالحرف S ، ويمكننا اختيار قاعدة لتطبيقها عليه. إذا اخترنا القاعدة 1، نحصل على السلسلة aSb . إذا اخترنا القاعدة 1 مرة أخرى، نستبدل S بـ aSb فنحصل على السلسلة aaSbb . إذا اخترنا الآن القاعدة 2، نستبدل S بـ ba فنحصل على السلسلة aababb ، وبذلك نكون قد انتهينا. يمكننا كتابة هذه السلسلة من الخيارات بإيجاز أكبر باستخدام الرموز:${\displaystyle S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aababb}$.

لغة القواعد النحوية هي المجموعة اللانهائية${\displaystyle \{a^{n}bab^{n}\mid n\geq 0\}=\{ba,abab,aababb,aaaabbb,\dotsc \}}$، أين${\displaystyle a^{k}}$يكون${\displaystyle a}$كرر${\displaystyle k}$مرات (و${\displaystyle n}$يمثل هذا الرقم تحديدًا عدد مرات تطبيق قاعدة الإنتاج رقم 1). هذه القواعد النحوية خالية من السياق (تظهر الرموز غير الطرفية المفردة فقط على الجانب الأيسر) وغير مبهمة.

لنفترض أن القواعد هي هذه بدلاً من ذلك:

1.${\displaystyle S\rightarrow a}$

2.${\displaystyle S\rightarrow SS}$

3.${\displaystyle aSa\rightarrow b}$

لا تُعتبر هذه القواعد النحوية خالية من السياق بسبب القاعدة 3، وهي غامضة بسبب الطرق المتعددة التي يمكن من خلالها استخدام القاعدة 2 لتوليد تسلسلات من${\displaystyle S}$س.

ومع ذلك، فإن اللغة التي تولدها هي ببساطة مجموعة جميع السلاسل غير الفارغة التي تتكون من${\displaystyle a}$s و/أو${\displaystyle b}$من السهل ملاحظة ذلك: لإنشاء${\displaystyle b}$من${\displaystyle S}$استخدم القاعدة 2 مرتين لإنشاء${\displaystyle SSS}$ثم قم بتطبيق القاعدة 1 مرتين والقاعدة 3 مرة واحدة لإنتاج${\displaystyle b}$وهذا يعني أنه يمكننا توليد متواليات غير فارغة عشوائية من${\displaystyle S}$ثم استبدل كل منها بـ${\displaystyle a}$أو${\displaystyle b}$كما يحلو لنا.

يمكن توليد تلك اللغة نفسها، بدلاً من ذلك، بواسطة قواعد نحوية غير غامضة وخالية من السياق؛ على سبيل المثال، القواعد النحوية المنتظمة ذات القواعد

1.${\displaystyle S\rightarrow aS}$

2.${\displaystyle S\rightarrow bS}$

3.${\displaystyle S\rightarrow a}$

4.${\displaystyle S\rightarrow b}$

في الصياغة الكلاسيكية للقواعد التوليدية التي اقترحها نعوم تشومسكي لأول مرة في الخمسينيات من القرن العشرين، ^{[ 2 ] [ 3 ]} تتكون القاعدة G من المكونات التالية:

• مجموعة محدودة N من الرموز غير الطرفية ، وهي منفصلة عن السلاسل المكونة من G.
• مجموعة منتهية${\displaystyle \Sigma }$من الرموز الطرفية المنفصلة عن N.​
• مجموعة محدودة P من قواعد الإنتاج ، كل قاعدة منها على الشكل التالي:

${\displaystyle (\Sigma \cup N)^{*}N(\Sigma \cup N)^{*}\rightarrow (\Sigma \cup N)^{*}}$

أين${\displaystyle {*}}$هو المشغل النجمي في شركة كلين و${\displaystyle \cup }$يرمز إلى اتحاد المجموعات . أي أن كل قاعدة إنتاج تربط سلسلة من الرموز بأخرى، حيث تحتوي السلسلة الأولى (الرأس) على عدد عشوائي من الرموز بشرط أن يكون واحد منها على الأقل رمزًا غير طرفي. في حالة كون السلسلة الثانية (الجسم) تتكون فقط من سلسلة فارغة - أي أنها لا تحتوي على أي رموز على الإطلاق - يمكن الإشارة إليها برمز خاص (غالبًا ما يكون${\displaystyle \Lambda }$، أو​${\displaystyle \epsilon }$) لتجنب الالتباس. وتسمى هذه القاعدة قاعدة المحو . ^{[ 4 ]}

• رمز مميز${\displaystyle S\in N}$هذا هو رمز البداية ، ويسمى أيضاً رمز الجملة .

تُعرَّف القواعد النحوية رسميًا على أنها مجموعة من العناصر${\displaystyle (N,\Sigma ,P,S)}$يُطلق على هذا النوع من القواعد النحوية الرسمية في الأدبيات اسم نظام إعادة الكتابة أو قواعد بنية العبارة . ^{[ 5 ] [ 6 ]}

يمكن تعريف عملية القواعد النحوية من حيث العلاقات على السلاسل النصية:

• بالنظر إلى قواعد اللغة${\displaystyle G=(N,\Sigma ,P,S)}$العلاقة الثنائية${\displaystyle {\underset {G}{\Rightarrow }}}$(يُنطق "G derives in one step") على الأوتار في${\displaystyle (\Sigma \cup N)^{*}}$يُعرَّف بما يلي:

  ${\displaystyle x{\underset {G}{\Rightarrow }}y\iff \exists u,v,p,q\in (\Sigma \cup N)^{*}:(x=upv)\wedge (p\rightarrow q\in P)\wedge (y=uqv)}$

• العلاقة${\displaystyle {\overset {*}{\underset {G}{\Rightarrow }}}}$(يُنطق كما في G، ويشتق في صفر أو أكثر من الخطوات ) يُعرَّف بأنه الإغلاق الانعكاسي المتعدي لـ${\displaystyle {\underset {G}{\Rightarrow }}}$
• أيُعدّ شكل الجملة أحد أنواع${\displaystyle (\Sigma \cup N)^{*}}$والتي يمكن اشتقاقها في عدد محدود من الخطوات من رمز البداية${\displaystyle S}$أي أن الصيغة الجملية هي عضو في${\displaystyle \left\{w\in (\Sigma \cup N)^{*}\mid S{\overset {*}{\underset {G}{\Rightarrow }}}w\right\}}$صيغة جملية لا تحتوي على رموز غير طرفية (أي أنها عضو في${\displaystyle \Sigma ^{*}}$يُطلق عليه اسم جملة . ^{[ 7 ]}
• لغة​​${\displaystyle G}$، المشار إليه بـ${\displaystyle {\boldsymbol {L}}(G)}$يُعرَّف بأنه مجموعة الجمل التي تم بناؤها بواسطة${\displaystyle G}$.

القواعد${\displaystyle G=(N,\Sigma ,P,S)}$وهو في الواقع نظام شبه ثيو${\displaystyle (N\cup \Sigma ,P)}$إعادة كتابة السلاسل بنفس الطريقة تمامًا؛ والفرق الوحيد هو أننا نميز بين الرموز غير الطرفية المحددة ، والتي يجب استبدالها في قواعد إعادة الكتابة، ونهتم فقط بإعادة الكتابة من رمز البداية المحدد.${\displaystyle S}$إلى سلاسل نصية بدون رموز غير طرفية.

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

ضع في اعتبارك القواعد النحوية${\displaystyle G}$أين${\displaystyle N=\left\{S,B\right\}}$،${\displaystyle \Sigma =\left\{a,b,c\right\}}$،${\displaystyle S}$هو رمز البداية، و${\displaystyle P}$يتضمن قواعد الإنتاج التالية:

1.${\displaystyle S\rightarrow aBSc}$

2.${\displaystyle S\rightarrow abc}$

3.${\displaystyle Ba\rightarrow aB}$

4.${\displaystyle Bb\rightarrow bb}$

تحدد هذه القواعد النحوية اللغة${\displaystyle L(G)=\left\{a^{n}b^{n}c^{n}\mid n\geq 1\right\}}$أين${\displaystyle a^{n}}$يشير إلى سلسلة من n متتالية${\displaystyle a}$وبالتالي، فإن اللغة هي مجموعة السلاسل التي تتكون من 1 أو أكثر${\displaystyle a}$'s، متبوعة بنفس العدد من${\displaystyle b}$'s، متبوعة بنفس العدد من${\displaystyle c}$'s.

بعض الأمثلة على اشتقاق السلاسل في${\displaystyle L(G)}$نكون:

(فيما يتعلق بالتدوين:)${\displaystyle P{\underset {i}{\Rightarrow }}Q}$يقرأ النص "السلسلة P تولد السلسلة Q عن طريق الإنتاج i "، ويتم الإشارة إلى الجزء المولد في كل مرة بخط غامق.

القواعد النحوية الخالية من السياق هي قواعد نحوية يتكون فيها الجانب الأيسر من كل قاعدة إنتاج من رمز غير طرفي واحد فقط. هذا القيد ليس بديهيًا؛ فليست كل اللغات قابلة للتوليد باستخدام القواعد النحوية الخالية من السياق. أما اللغات التي يمكن توليدها باستخدام هذه القواعد فتُسمى لغات خالية من السياق .

اللغة${\displaystyle L(G)=\left\{a^{n}b^{n}c^{n}\mid n\geq 1\right\}}$اللغة المعرّفة أعلاه ليست لغة خالية من السياق، ويمكن إثبات ذلك بدقة باستخدام نظرية الضخ للغات الخالية من السياق ، ولكن على سبيل المثال اللغة${\displaystyle \left\{a^{n}b^{n}\mid n\geq 1\right\}}$(واحد على الأقل)${\displaystyle a}$متبوعًا بنفس العدد من${\displaystyle b}$إن ('s) خالٍ من السياق، كما يمكن تعريفه بواسطة القواعد النحوية${\displaystyle G_{2}}$مع${\displaystyle N=\left\{S\right\}}$،${\displaystyle \Sigma =\left\{a,b\right\}}$،${\displaystyle S}$رمز البداية، وقواعد الإنتاج التالية:

1.${\displaystyle S\rightarrow aSb}$

2.${\displaystyle S\rightarrow ab}$

يمكن التعرف على اللغة الخالية من السياق في${\displaystyle O(n^{3})}$في زمن ( انظر ترميز Big O ) بواسطة خوارزمية مثل مُعرِّف إيرلي ، وفي زمن أقل من التكعيبي بواسطة خوارزميات ضرب المصفوفات السريعة . ^{[ 9 ]} أي أنه لكل لغة خالية من السياق، يمكن بناء آلة تأخذ سلسلة نصية كمدخل وتحدد في${\displaystyle O(n^{3})}$الوقت الذي يتم فيه تحديد ما إذا كانت السلسلة تنتمي إلى اللغة، حيث${\displaystyle n}$يمثل طول السلسلة. ^{[ 10 ]} اللغات الخالية من السياق الحتمية هي مجموعة فرعية من اللغات الخالية من السياق التي يمكن التعرف عليها في وقت خطي. ^{[ 11 ]} توجد خوارزميات متنوعة تستهدف إما هذه المجموعة من اللغات أو مجموعة فرعية منها.

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

اللغة${\displaystyle \left\{a^{n}b^{n}\mid n\geq 1\right\}}$اللغة المحددة أعلاه ليست منتظمة، ولكنها لغة${\displaystyle \left\{a^{n}b^{m}\mid m,n\geq 1\right\}}$(واحد على الأقل)${\displaystyle a}$متبوعًا بواحد على الأقل${\displaystyle b}$(حيث قد تختلف الأرقام) هو، كما يمكن تعريفه بواسطة القواعد النحوية${\displaystyle G_{3}}$مع${\displaystyle N=\left\{S,A,B\right\}}$،${\displaystyle \Sigma =\left\{a,b\right\}}$،${\displaystyle S}$رمز البداية، وقواعد الإنتاج التالية:

1. ${\displaystyle S\rightarrow aA}$
2. ${\displaystyle A\rightarrow aA}$
3. ${\displaystyle A\rightarrow bB}$
4. ${\displaystyle B\rightarrow bB}$
5. ${\displaystyle B\rightarrow \epsilon }$

يمكن التعرف على جميع اللغات التي تولدها قواعد نحوية منتظمة في${\displaystyle O(n)}$يتم حساب الوقت بواسطة آلة ذات حالات محدودة. على الرغم من أن القواعد النحوية المنتظمة تُعبَّر عنها عادةً باستخدام التعابير النمطية ، إلا أن بعض أشكال التعابير النمطية المستخدمة عمليًا لا تُولِّد اللغات المنتظمة بدقة، ولا تُظهر أداءً خطيًا في التعرف بسبب هذه الانحرافات.

طُوِّرت العديد من التوسعات والتعديلات على التسلسل الهرمي الأصلي لقواعد اللغة الرسمية لتشومسكي، من قِبَل اللغويين وعلماء الحاسوب على حد سواء، وذلك عادةً إما لزيادة قدرتها التعبيرية أو لتسهيل تحليلها أو فهمها. ومن بين أشكال القواعد التي طُوِّرت:

• تزيد قواعد النحو المتجاورة مع الشجرة من قدرة التعبير لقواعد النحو التوليدية التقليدية من خلال السماح لقواعد إعادة الكتابة بالعمل على أشجار التحليل بدلاً من السلاسل النصية فقط. ^{[ 12 ]}
• تسمح قواعد الإلحاق ^{[ 13 ]} وقواعد السمات ^{[ 14 ] [ 15 ]} بتوسيع قواعد إعادة الكتابة بالسمات والعمليات الدلالية، وهو أمر مفيد لزيادة قدرة القواعد على التعبير ولإنشاء أدوات ترجمة لغوية عملية.

القواعد النحوية التكرارية هي قواعد نحوية تحتوي على قواعد إنتاج تكرارية . على سبيل المثال، تكون القواعد النحوية للغة خالية من السياق تكرارية من اليسار إذا وُجد رمز غير طرفي A يمكن تطبيقه على قواعد الإنتاج لإنتاج سلسلة نصية يكون A فيها الرمز الأيسر. ^{[ 16 ]} ومن أمثلة القواعد النحوية التكرارية جملة فرعية ضمن جملة مفصولة بفاصلتين. ^{[ 17 ]} جميع أنواع القواعد النحوية في تسلسل تشومسكي الهرمي يمكن أن تكون تكرارية.