القواعد النحوية المنتظمة

في علم الحاسوب النظري ونظرية اللغة الرسمية ، القواعد النحوية المنتظمة هي قواعد نحوية منتظمة من اليمين أو اليسار . وفي حين يختلف تعريفها الدقيق من كتاب مدرسي إلى آخر، فإنها جميعًا تتطلب أن

• تحتوي جميع قواعد الإنتاج على رمز غير نهائي واحد على الأكثر ؛
• يكون هذا الرمز دائمًا إما في نهاية الجانب الأيمن للقاعدة أو دائمًا في بدايتها.

كل قواعد اللغة المنتظمة تصف لغة منتظمة .

القواعد النحوية المنتظمة اليمنى (وتسمى أيضًا القواعد النحوية الخطية اليمنى ) هي قواعد نحوية رسمية ( N ، Σ، P ، S ) حيث تكون جميع قواعد الإنتاج في P من أحد الأشكال التالية:

1. أ → أ
2. أ → أ ب
3. أ → ε

حيث A و B و S ∈ N هي رموز غير نهائية، و a ∈ Σ هو رمز نهائي، وε يشير إلى السلسلة الفارغة ، أي السلسلة التي يبلغ طولها 0. يسمى S رمز البداية.

في قواعد النحو المنتظمة لليسار (وتسمى أيضًا قواعد النحو الخطية لليسار )، تتبع جميع القواعد الأشكال

1. أ → أ
2. أ → با
3. أ → ε

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

لا يجوز خلط قواعد النوعين؛ على سبيل المثال، القواعد النحوية التي تحتوي على مجموعة القواعد { S → aT ، T → Sb ، S→ε} ليست منتظمة، وتصف اللغة ، والتي ليست منتظمة أيضًا. ${\displaystyle \{a^{i}b^{i}:i\in \mathbb {N} \}}$

بعض الكتب المدرسية والمقالات لا تسمح بقواعد الإنتاج الفارغة، وتفترض أن السلسلة الفارغة غير موجودة في اللغات.

قواعد النحو المنتظمة الممتدة هي قواعد تخضع فيها جميع القواعد لأحد

1. A → w ، حيث A هو طرف غير طرفي في N و w موجود في سلسلة (ربما فارغة) من الأطراف الطرفية Σ ^*
2. A → wB ، حيث A و B في N و w في Σ ^* .

يُطلق بعض المؤلفين على هذا النوع من القواعد النحوية اسم قواعد نحوية منتظمة (أو قواعد نحوية خطية ) ^[1] والنوع أعلاه اسم قواعد نحوية منتظمة تمامًا (أو قواعد نحوية خطية تمامًا ). ^[2]

قواعد النحو المنتظمة الممتدة هي قواعد تخضع فيها جميع القواعد لأحد

1. A → w ، حيث A غير طرفية في N و w في Σ ^*
2. A → Bw ، حيث A و B في N و w في Σ ^* .

مثال على قواعد نحوية منتظمة قائمة G مع N = {S, A}، Σ = {a, b, c}، P يتكون من القواعد التالية

س → س

س → ب أ

أ → ε

أ → ج أ

وS هو رمز البداية. تصف هذه القواعد النحوية نفس اللغة التي تصف التعبير العادي a*bc*، أي مجموعة كل السلاسل التي تتكون من عدد عشوائي من حروف " a "، تليها حرف " b " واحد، تليها عدد عشوائي من حروف " c ".

تُعطى قواعد النحو المنتظم الأيمن الممتدة الأطول إلى حد ما ولكنها أكثر وضوحًا لنفس التعبير المنتظم بواسطة N = {S, A, B, C}، Σ = {a, b, c}، حيث تتكون P من القواعد التالية:

س → أ

أ → أأ

أ → ب

ب → ب ج

ج → ε

ج → ج ج

...حيث يتوافق كل حرف كبير مع العبارات التي تبدأ في الموضع التالي في التعبير العادي.

كمثال من مجال لغات البرمجة، يمكن وصف مجموعة جميع السلاسل التي تشير إلى رقم فاصل عائم بواسطة قواعد نحوية منتظمة يمنى موسعة G مع N = {S,A,B,C,D,E,F}، Σ = {0,1,2,3,4,5,6,7,8,9,+,−,.,e}، حيث S هو رمز البداية، ويتكون P من القواعد التالية:

س → +أ	أ → 0أ	ب → 0 ج	ج → 0ج	د → +هـ	ع → 0ف	ف → 0ف
س → −أ	أ → 1أ	ب → 1ج	ج → 1ج	د → −هـ	ع → 1ف	ف → 1ف
س → أ	أ → 2أ	ب → 2ج	ج → 2ج	د → هـ	ع → 2ف	ف → 2ف
	أ → 3أ	ب → 3ج	ج → 3ج		ع → 3ف	ف → 3ف
	أ → 4أ	ب → 4ج	ج → 4ج		ع → 4ف	ف → 4ف
	أ → 5أ	ب → 5ج	ج → 5ج		ع → 5ف	ف → 5ف
	أ → 6أ	ب → 6ج	ج → 6ج		ع → 6ف	ف → 6ف
	أ → 7أ	ب → 7ج	ج → 7ج		ع → 7ف	ف → 7ف
	أ → 8أ	ب → 8ج	ج → 8ج		ع → 8ف	ف → 8ف
	أ → 9أ	ب → 9ج	ج → 9ج		ع → 9ف	ف → 9ف
	أ → .ب		ج → د			ف → ε
	أ → ب		ج → ε

هناك تطابق مباشر واحد لواحد بين قواعد قواعد النحو المنتظم الأيمن (بشكل صارم) وقواعد الأتمتة المحدودة غير الحتمية ، بحيث تولد القواعد النحوية اللغة التي تقبلها الأتمتة بالضبط. ^[3] وبالتالي، فإن قواعد النحو المنتظم الأيمن تولد جميع اللغات المنتظمة بالضبط . تصف قواعد النحو المنتظم الأيسر عكس جميع هذه اللغات، أي اللغات المنتظمة بالضبط أيضًا.

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

إذا تم حظر الإنتاجات الفارغة، فلا يمكن إنشاء سوى جميع اللغات العادية التي لا تتضمن السلسلة الفارغة. ^[4]

في حين أن القواعد النحوية المنتظمة لا تستطيع وصف اللغات المنتظمة إلا، فإن العكس ليس صحيحًا: يمكن أيضًا وصف اللغات المنتظمة بقواعد نحوية غير منتظمة.

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

على سبيل المثال، القواعد النحوية G مع N = {S, A}، Σ = {a, b}، P مع رمز البداية S والقواعد

س → أأ

أ → سب

س → ε

يولد لغة خطية غير منتظمة نموذجية. ${\displaystyle \{a^{i}b^{i}:i\geq 0\}}$

• التعبيرات المنتظمة ، تدوين مضغوط للقواعد النحوية المنتظمة
• قواعد الشجرة المنتظمة ، تعميم من السلاسل إلى الأشجار
• قواعد البادئة
• هرم تشومسكي

• نموذج ماركوف المخفي

• بيرين، دومينيك (1990)، "الأتمتة المحدودة"، في ليوين، جان فان (المحرر)، النماذج الرسمية والدلالات ، دليل علوم الكمبيوتر النظرية، المجلد ب، إلسفير، ص  1-58
• بين، جان إيريك (أكتوبر 2012). الأسس الرياضية لنظرية الأتمتة (PDF) ., الفصل الثالث