قواعد اللغة الرئيسية

📅 آخر تحديث: ٢٨ يوليو ٢٠٢٦
✍️ نُشر في: ٢٨ يوليو ٢٠٢٦
📷 يحتوي على 37 صور
الموسوعة الحرة

قواعد الرأس ( HG ) هي شكلية نحوية قدمها كارل بولارد (1984) [ 1 ] كامتداد لفئة القواعد الخالية من السياق . ولذلك، تُعد قواعد الرأس نوعًا من قواعد بنية العبارة ، على عكس قواعد التبعية . وتُمثل فئة قواعد الرأس مجموعة فرعية من أنظمة إعادة الكتابة الخطية الخالية من السياق .

إحدى الطرق الشائعة لتعريف قواعد الرأس هي استبدال السلاسل الطرفية لقواعد السياق الحر بسلاسل طرفية مفهرسة، حيث يشير الفهرس إلى كلمة "الرأس" في السلسلة. على سبيل المثال، قاعدة سياق حر مثلأ→أبج{\displaystyle A\to abc}قد يكون بدلاً من ذلكأ→(أبج،0){\displaystyle A\to (abc,0)}حيث يمثل الطرف الصفري، وهو الحرف a ، رأس سلسلة الأطراف الناتجة. ولتبسيط الترميز، يمكن كتابة هذه القاعدة ببساطة على شكل سلسلة الأطراف، مع الإشارة إلى الطرف الرأسي بعلامة ما، كما فيأ→أ^بج{\displaystyle A\to {\widehat {a}}bc}.

ثم تُضاف عمليتان أساسيتان إلى جميع قواعد إعادة الكتابة: التغليف والربط.

العمليات على السلاسل ذات الرؤوس

لفائف

التغليف هو عملية على سلسلتين نصيتين برأسين، ويتم تعريفها على النحو التالي:

يتركαx^β{\displaystyle \alpha {\widehat {x}}\beta }وγy^دلتا{\displaystyle \gamma {\widehat {y}}\delta }تكون السلاسل الطرفية التي تبدأ بـ x و y على التوالي.

w(αx^β،γy^دلتا)=αxγy^دلتاβ{\displaystyle w(\alpha {\widehat {x}}\beta ,\gamma {\widehat {y}}\delta )=\alpha x\gamma {\widehat {y}}\delta \beta }

سلسلة

عملية الربط هي مجموعة من العمليات على السلاسل النصية ذات الرؤوس n > 0، وهي معرفة لـ n = 1، 2، 3 على النحو التالي:

يتركαx^β{\displaystyle \alpha {\widehat {x}}\beta }،γy^دلتا{\displaystyle \gamma {\widehat {y}}\delta }، وζz^η{\displaystyle \zeta {\widehat {z}}\eta }تكون سلاسل طرفية تبدأ بـ x و y و z على التوالي.

ج1،0(αx^β)=αx^β{\displaystyle c_{1,0}(\alpha {\widehat {x}}\beta )=\alpha {\widehat {x}}\beta }

ج2،0(αx^β،γy^دلتا)=αx^βγyدلتا{\displaystyle c_{2,0}(\alpha {\widehat {x}}\beta ,\gamma {\widehat {y}}\delta )=\alpha {\widehat {x}}\beta \gamma y\delta }

ج2،1(αx^β،γy^دلتا)=αxβγy^دلتا{\displaystyle c_{2,1}(\alpha {\widehat {x}}\beta ,\gamma {\widehat {y}}\delta )=\alpha x\beta \gamma {\widehat {y}}\delta }

ج3،0(αx^β،γy^دلتا،ζz^η)=αx^βγyدلتاζzη{\displaystyle c_{3,0}(\alpha {\widehat {x}}\beta ,\gamma {\widehat {y}}\delta ,\zeta {\widehat {z}}\eta )=\alpha {\widehat {x}}\beta \gamma y\delta \zeta z\eta }

ج3،1(αx^β،γy^دلتا،ζz^η)=αxβγy^دلتاζzη{\displaystyle c_{3,1}(\alpha {\widehat {x}}\beta ,\gamma {\widehat {y}}\delta ,\zeta {\widehat {z}}\eta )=\alpha x\beta \gamma {\widehat {y}}\delta \zeta z\eta }

ج3،2(αx^β،γy^دلتا،ζz^η)=αxβγyدلتاζz^η{\displaystyle c_{3,2}(\alpha {\widehat {x}}\beta ,\gamma {\widehat {y}}\delta ,\zeta {\widehat {z}}\eta )=\alpha x\beta \gamma y\delta \zeta {\widehat {z}}\eta }

وهكذا بالنسبة لـجم،ن:0≤ن<م{\displaystyle c_{m,n}:0\leq n<m}يمكن تلخيص النمط هنا ببساطة على أنه "دمج عدد من السلاسل الطرفية m ، مع تحديد رأس السلسلة n كرأس للسلسلة الناتجة".

شكل القواعد

تُعرَّف قواعد النحو الرئيسية من خلال هاتين العمليتين، وتأخذ القواعد أحد الشكلين التاليين

X→w(α،β){\displaystyle X\to w(\alpha ,\beta )}

X→جم،ن(α،β،...){\displaystyle X\to c_{m,n}(\alpha ,\beta ,...)}

أينα{\displaystyle \alpha }،β{\displaystyle \beta }... كل منها إما سلسلة طرفية أو رمز غير طرفي.

مثال

تستطيع قواعد اللغة الرئيسية توليد اللغة{أنبنجندن:ن≥0}{\displaystyle \{a^{n}b^{n}c^{n}d^{n}:n\geq 0\}}يمكننا تعريف القواعد النحوية على النحو التالي:

S→ج1،0(ϵ^){\displaystyle S\to c_{1,0}({\widehat {\epsilon }})}

S→ج3،1(أ^،تي،د^){\displaystyle S\to c_{3,1}({\widehat {a}},T,{\widehat {d}})}

تي→w(S،ب^ج){\displaystyle T\to w(S,{\widehat {b}}c)}

وبالتالي فإن اشتقاق كلمة "abcd" هو:

S{\displaystyle S}

ج3،1(أ^،تي،د^){\displaystyle c_{3,1}({\widehat {a}},T,{\widehat {d}})}

ج3،1(أ^،w(S،ب^ج)،د^){\displaystyle c_{3,1}({\widehat {a}},w(S,{\widehat {b}}c),{\widehat {d}})}

ج3،1(أ^،w(ج1،0(ϵ^)،ب^ج)،د^){\displaystyle c_{3,1}({\widehat {a}},w(c_{1,0}({\widehat {\epsilon }}),{\widehat {b}}c),{\widehat {d}})}

ج3،1(أ^،w(ϵ^،ب^ج)،د^){\displaystyle c_{3,1}({\widehat {a}},w({\widehat {\epsilon }},{\widehat {b}}c),{\widehat {d}})}

ج3،1(أ^،ب^ج،د^){\displaystyle c_{3,1}({\widehat {a}},{\widehat {b}}c,{\widehat {d}})}

أب^جد{\displaystyle a{\widehat {b}}cd}

وبالنسبة لـ " aabbccdd ":

S{\displaystyle S}

ج3،1(أ^،تي،د^){\displaystyle c_{3,1}({\widehat {a}},T,{\widehat {d}})}

ج3،1(أ^،w(S،ب^ج)،د^){\displaystyle c_{3,1}({\widehat {a}},w(S,{\widehat {b}}c),{\widehat {d}})}

ج3،1(أ^،w(ج3،1(أ^،تي،د^)،ب^ج)،د^){\displaystyle c_{3,1}({\widehat {a}},w(c_{3,1}({\widehat {a}},T,{\widehat {d}}),{\widehat {b}}c),{\widehat {d}})}

ج3،1(أ^،w(ج3،1(أ^،w(S،ب^ج)،د^)،ب^ج)،د^){\displaystyle c_{3,1}({\widehat {a}},w(c_{3,1}({\widehat {a}},w(S,{\widehat {b}}c),{\widehat {d}}),{\widehat {b}}c),{\widehat {d}})}

ج3،1(أ^،w(ج3،1(أ^،w(ج1،0(ϵ^)،ب^ج)،د^)،ب^ج)،د^){\displaystyle c_{3,1}({\widehat {a}},w(c_{3,1}({\widehat {a}},w(c_{1,0}({\widehat {\epsilon }}),{\widehat {b}}c),{\widehat {d}}),{\widehat {b}}c),{\widehat {d}})}

ج3،1(أ^،w(ج3،1(أ^،w(ϵ^،ب^ج)،د^)،ب^ج)،د^){\displaystyle c_{3,1}({\widehat {a}},w(c_{3,1}({\widehat {a}},w({\widehat {\epsilon }},{\widehat {b}}c),{\widehat {d}}),{\widehat {b}}c),{\widehat {d}})}

ج3،1(أ^،w(ج3،1(أ^،ب^ج،د^)،ب^ج)،د^){\displaystyle c_{3,1}({\widehat {a}},w(c_{3,1}({\widehat {a}},{\widehat {b}}c,{\widehat {d}}),{\widehat {b}}c),{\widehat {d}})}

ج3،1(أ^،w(أب^جد،ب^ج)،د^){\displaystyle c_{3,1}({\widehat {a}},w(a{\widehat {b}}cd,{\widehat {b}}c),{\widehat {d}})}

ج3،1(أ^،أبب^ججد،د^){\displaystyle c_{3,1}({\widehat {a}},ab{\widehat {b}}ccd,{\widehat {d}})}

أأبب^ججدد{\displaystyle aab{\widehat {b}}ccdd}

الخصائص الرسمية

المكافئات

يوضح فيجاي شانكر ووير (1994) [ 2 ] أن القواعد النحوية الخطية المفهرسة ، والقواعد النحوية الفئوية التوافقية ، والقواعد النحوية المجاورة للشجرة ، والقواعد النحوية الرأسية هي أشكال متكافئة بشكل ضعيف ، حيث أنها جميعًا تحدد نفس لغات السلسلة.

مراجع

  1. ↑ بولارد، سي. 1984. قواعد بنية العبارة المعممة، وقواعد الرأس، واللغة الطبيعية . أطروحة دكتوراه، جامعة ستانفورد، كاليفورنيا.
  2. ↑ فيجاي شانكر، ك. ووير، ديفيد ج. 1994. تكافؤ أربعة امتدادات لقواعد اللغة الخالية من السياق . نظرية الأنظمة الرياضية 27(6): 511-546.