قواعد اللغة المفهرسة

في المنشورات المعاصرة التي تتبع هوبكروفت وأولمان (1979)، ^{[ 2 ]} يتم تعريف القواعد المفهرسة رسميًا على أنها مجموعة خماسية G = ⟨ N , T , F , P , S ⟩ حيث

• N هي مجموعة من المتغيرات أو الرموز غير الطرفية ،
• T هي مجموعة (" أبجدية ") من الرموز الطرفية،
• F هي مجموعة مما يسمى برموز الفهرسة ، أو الفهارس .
• S ∈ N هو رمز البداية ، و
• P هي مجموعة منتهية من الإنتاجات .

في قواعد الإنتاج، وكذلك في اشتقاقات القواعد المفهرسة، تُلحق سلسلة (مكدس) σ ∈ F ^* من رموز الفهرسة بكل رمز غير طرفي A ∈ N ، ويُرمز لها بـ A [ σ ]. ^{[ ملاحظة 1 ]} لا يجوز أن تتبع الرموز الطرفية مكدسات فهرسة. بالنسبة لمكدس فهرسة σ ∈ F ^* وسلسلة α ∈ ( N ∪ T ) ^* من الرموز الطرفية وغير الطرفية، فإن α [ σ ] تُشير إلى نتيجة إلحاق [ σ ] بكل رمز غير طرفي في α ؛ على سبيل المثال، إذا كانت α تساوي a B C d E حيث a و d ∈ T رمز طرفي، و B و C و E ∈ N رموز غير طرفية، فإن α [ σ ] تُشير إلى a B [ σ ] C [ σ ] d E [ σ ]. باستخدام هذه الرموز، يجب أن يكون كل إنتاج في P على الشكل التالي

1. A [σ] → α[σ],
2. A [σ] → B [ f σ]، أو
3. A [ f σ] → α[σ],

حيث A و B ∈ N رموز غير طرفية، و f ∈ F فهرس، و σ ∈ F ^* سلسلة من رموز الفهرس، و α ∈ ( N ∪ T ) ^* سلسلة من الرموز غير الطرفية والطرفية. يكتب بعض المؤلفين "." بدلاً من " σ " لمكدس الفهرس في قواعد الإنتاج؛ فتصبح قاعدة النوع 1 و2 و3 على النحو التالي: A [..]→ α [..]، و A [..]→ B [ f ..]  ، و A [ f ..]→ α [..] ، على التوالي.

تتشابه الاشتقاقات مع تلك الموجودة في قواعد اللغة الخالية من السياق، باستثناء مكدس الفهرسة المرفق بكل رمز غير طرفي. عند تطبيق قاعدة إنتاج مثل A [ σ ] → B [ σ ] C [ σ ]، يُنسخ مكدس فهرسة A إلى كل من B و C. علاوة على ذلك، يمكن للقاعدة إضافة رمز فهرسة إلى المكدس، أو إزالة رمز الفهرسة "العلوي" (أي الأيسر) منه.

بشكل رسمي، يتم تعريف العلاقة ⇒ ("الاشتقاق المباشر") على مجموعة ( N [ F ^* ]∪T ) * ^من "الأشكال الجملية" على النحو التالي:

1. إذا كانت القاعدة A [ σ ] → α [ σ ] قاعدة إنتاج من النوع 1، فإن βA [ φ ] γ ⇒ βα [ φ ] γ ، وفقًا للتعريف أعلاه. أي أن مكدس الفهرسة φ في الجانب الأيسر من القاعدة يُنسخ إلى كل رمز غير طرفي في الجانب الأيمن.
2. إذا كان A [ σ ] → B [ fσ ] قاعدة إنتاج من النوع 2، فإن βA [ φ ] γ ⇒ βB [ fφ ] γ . أي أن مكدس الفهرسة في الجانب الأيمن يُستمد من مكدس الفهرسة في الجانب الأيسر φ عن طريق إضافة f إليه.
3. إذا كان A [ fσ ] → α [ σ ] قاعدة إنتاج من النوع 3، فإن βA [ fφ ] γ ⇒ βα [ φ ] γ ، باستخدام تعريف α [ σ ] مرة أخرى . أي، يتم سحب الفهرس الأول f من مكدس الجانب الأيسر، ثم يتم توزيعه على كل رمز غير طرفي في الجانب الأيمن.

وكما هو معتاد، تُعرَّف علاقة الاشتقاق ∗ ⇒ على أنها الإغلاق الانعكاسي المتعدي للاشتقاق المباشر ⇒. اللغة L ( G ) = { w ∈ T ^* : S ∗ ⇒ w } هي مجموعة جميع سلاسل الرموز النهائية القابلة للاشتقاق من رمز البداية.

تاريخيًا، طُرح مفهوم القواعد المفهرسة لأول مرة من قِبل ألفريد أهو (1968) ^{[ 3 ]} باستخدام صيغة مختلفة. عرّف أهو القاعدة المفهرسة بأنها مجموعة خماسية ( N ، T ، F ، P ، S ) حيث

1. N عبارة عن أبجدية محدودة من المتغيرات أو الرموز غير النهائية
2. T عبارة عن أبجدية محدودة من الرموز الطرفية
3. F ⊆ 2 ^{N × ( N ∪ T ) *} هي المجموعة المنتهية لما يسمى بالأعلام (كل علم هو نفسه مجموعة مما يسمى بإنتاجات المؤشر )
4. P ⊆ N × ( NF ^* ∪ T ) ^* هي المجموعة المنتهية من الإنتاجات
5. S ∈ N هو رمز البداية

وكانت الاشتقاقات المباشرة كما يلي:

• يُطابق الإنتاج p = ( A → X1η1 _... Xkηk ) من P رمزًا غير طرفي _A ∈ N متبوعًا بسلسلة علاماته (التي قد تكون فارغة) ζ ∈ F * ^. في هذا السياق، _يُشتق γAζδ _، عبر p ، إلى γX1θ1 ... Xkθkδ ، حيث θi = ηiζ إذا _كان Xi رمزًا غير طرفي ، وكلمة فارغة في غير ذلك. بالتالي، تُنسخ علامات A القديمة إلى _كل رمز غير طرفي جديد ينتجه p _. يمكن محاكاة كل إنتاج _{من هذا القبيل بواسطة} إنتاجات مناسبة من _{النوعين} 1 و2 في صيغة هوبكروفت/أولمان.
• يُطابق إنتاج الفهرس p = ( _A → X1 ... Xk ) ∈ f الرمز Afζ (يجب أن يتطابق العلم f الذي يأتي منه مع الرمز الأول الذي يلي الرمز غير الطرفي _A ) ، _وينسخ سلسلة الفهرس المتبقية ζ إلى كل رمز غير طرفي جديد: γAfζδ _، ويُشتق إلى γX1θ1 ... Xkθkδ ، حيث θi هي الكلمة الفارغة عندما _يكون Xi رمزًا طرفيًا، و ζ عندما _{يكون رمزًا غير طرفي. يتوافق كل إنتاج من هذا النوع} مع إنتاج من النوع 3 في صيغة هوبكروفت/أولمان .

وقد استخدم هاياشي (1973، ص  65-66) هذا الأسلوب الرسمي على سبيل المثال. ^{[ 4 ]}

بفرض أن σ يمثل تسلسلًا عشوائيًا من رموز المكدس، يمكننا تعريف قواعد اللغة L = { a ⁿ b ⁿ c ⁿ | n ≥ 1 } ^{[ ملاحظة 4 ]} على النحو التالي:

S [ σ ]	→	أ س [ فσ ] ج
S [ σ ]	→	T [ σ ]
T [ fσ ]	→	T [ σ ] b
T []	→	ε

لاستخلاص السلسلة abc، لدينا الخطوات التالية:

S [] ⇒ aS [ f ] c ⇒ aT [ f ] c ⇒ aT [] bc ⇒ abc

بصورة مماثلة:

S [] ⇒ aS [ f ] c ⇒ aaS [ ff ] cc ⇒ aaT [ ff ] cc ⇒ aaT [ f ] bcc ⇒ aaT [] bbcc ⇒ aabbcc

اللغات المفهرسة خطيًا هي مجموعة فرعية من اللغات المفهرسة، وبالتالي يمكن إعادة ترميز جميع اللغات المفهرسة خطيًا (LIGs) كلغات مفهرسة (IGs)، مما يجعل اللغات المفهرسة خطيًا أقل قوة من اللغات المفهرسة، وبالتالي فإن التحويل من لغة مفهرسة خطيًا إلى لغة مفهرسة بسيط نسبيًا. ^{[ 17 ]} تبدو قواعد اللغات المفهرسة خطيًا بشكل عام كما يلي تقريبًا${\displaystyle X[\sigma ]\to \alpha Y[\sigma ]\beta }$، باستثناء جزء الدفع/السحب من قاعدة إعادة الكتابة. الرموز${\displaystyle \alpha }$و${\displaystyle \beta }$تمثل سلاسل من الرموز الطرفية و/أو غير الطرفية، ويجب أن يكون لأي رمز غير طرفي في أي منهما مكدس فارغ، وفقًا لتعريف مجموعة التعليمات المنطقية (LIG). وهذا، بالطبع، يتعارض مع كيفية تعريف مجموعات التعليمات (IGs): في مجموعة التعليمات، يجب أن يكون للرموز غير الطرفية التي لا يتم دفع مكدساتها أو سحبها منه نفس المكدس تمامًا مثل الرمز غير الطرفي المعاد كتابته. وبالتالي، بطريقة ما، نحتاج إلى وجود رموز غير طرفية في${\displaystyle \alpha }$و${\displaystyle \beta }$والتي، على الرغم من امتلاكها لمكدسات غير فارغة، تتصرف كما لو كانت لديها مكدسات فارغة.

ضع في اعتبارك القاعدة${\displaystyle X[\sigma ]\to Y[]Z[\sigma f]}$كمثال توضيحي. عند تحويل هذا إلى IG، يكون البديل لـ${\displaystyle Y[]}$لا بد أن يكون هناك شيء ما${\displaystyle Y^{\prime }[\sigma ]}$يتصرف تمامًا مثل${\displaystyle Y[]}$بغض النظر عن${\displaystyle \sigma }$لتحقيق ذلك، يمكننا ببساطة وضع زوج من القواعد التي تأخذ أي${\displaystyle Y^{\prime }[\sigma ]}$أين${\displaystyle \sigma }$ليست فارغة، وتقوم بسحب الرموز من المكدس. ثم، عندما يصبح المكدس فارغًا، يمكن إعادة كتابته على النحو التالي:${\displaystyle Y[]}$.

${\displaystyle Y^{\prime }[\sigma f]\to Y^{\prime }[\sigma ]}$

${\displaystyle Y^{\prime }[]\to Y[]}$

يمكننا تطبيق هذا بشكل عام لاستخلاص مجموعة معلوماتية من مجموعة معلوماتية. على سبيل المثال، إذا كانت المجموعة المعلوماتية للغة${\displaystyle \{a^{n}b^{n}c^{n}d^{m}|n\geq 1,m\geq 1\}}$وهو كالتالي:

${\displaystyle S[\sigma ]\to T[\sigma ]V[]}$

${\displaystyle V[]\to d~|~dV[]}$

${\displaystyle T[\sigma ]\to aT[\sigma f]c~|~U[\sigma ]}$

${\displaystyle U[\sigma f]\to bU[\sigma ]}$

${\displaystyle U[]\to \epsilon }$

إن القاعدة الجملية هنا ليست قاعدة IG، ولكن باستخدام خوارزمية التحويل المذكورة أعلاه، يمكننا تحديد قواعد جديدة لـ${\displaystyle V^{\prime }}$، مع تغيير القواعد النحوية إلى:

${\displaystyle S[\sigma ]\to T[\sigma ]V^{\prime }[\sigma ]}$

${\displaystyle V^{\prime }[\sigma f]\to V^{\prime }[\sigma ]}$

${\displaystyle V^{\prime }[]\to V[]}$

${\displaystyle V[]\to d~|~dV[]}$

${\displaystyle T[\sigma ]\to aT[\sigma f]c~|~U[\sigma ]}$

${\displaystyle U[\sigma f]\to bU[\sigma ]}$

${\displaystyle U[]\to \epsilon }$

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

يُبيّن فيجاي-شانكر ووير (1994) ^{[ 18 ]} أن القواعد النحوية الخطية المفهرسة، والقواعد النحوية الفئوية التوافقية ، وقواعد النحو الشجرية المجاورة ، وقواعد النحو الرأسية ، جميعها تُعرّف نفس فئة لغات السلاسل النصية. ويختلف تعريفهم الرسمي للقواعد النحوية الخطية المفهرسة ^{[ 19 ]} عن التعريف المذكور أعلاه .

تُعدّ قواعد اللغة ذات التكافؤ الضعيف (LIGs) (وما يُكافئها بشكل ضعيف ) أقل تعبيرية (أي أنها تُولّد مجموعة فرعية فعلية) من اللغات التي تُولّدها عائلة أخرى من الصيغ المكافئة بشكل ضعيف، والتي تشمل: LCFRS و MCTAG و MCFG والقواعد النحوية البسيطة (MGs). ويمكن تحليل هذه العائلة الأخيرة (أيضًا) في وقت متعدد الحدود . ^{[ 20 ]}