ارتفاع النجوم

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

بصورة أكثر رسمية، يتم تعريف ارتفاع النجمة للتعبير النمطي E على أبجدية محدودة A استقرائياً على النحو التالي:

• ${\displaystyle \textstyle h\left(\emptyset \right)\,=\,0}$،${\displaystyle \textstyle h\left(\varepsilon \right)\,=\,0}$، و${\displaystyle \textstyle h\left(a\right)\,=\,0}$لجميع رموز الأبجدية a في A.
• ${\displaystyle \textstyle h\left(EF\right)\,=\,h\left(E\,\mid \,F\right)\,=\,\max \left(\,h(E),h(F)\,\right)}$
• ${\displaystyle \textstyle h\left(E^{*}\right)\,=\,h(E)+1.}$

هنا،${\displaystyle \scriptstyle \emptyset }$ε هو التعبير النمطي الخاص الذي يدل على المجموعة الفارغة و ε هو التعبير النمطي الخاص الذي يدل على الكلمة الفارغة ؛ E و F تعبيرات نمطية اختيارية.

يُعرَّف ارتفاع النجمة h ( L ) للغة منتظمة L بأنه أدنى ارتفاع للنجمة بين جميع التعبيرات المنتظمة التي تمثل L. والفكرة هنا هي أنه إذا كانت اللغة L ذات ارتفاع نجمي كبير، فإنها تكون معقدة بطبيعتها إلى حد ما، لأنه لا يمكن وصفها باستخدام تعبير منتظم "بسيط" ذي ارتفاع نجمي منخفض.

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

${\displaystyle \textstyle \left(b\,\mid \,aa^{*}b\right)^{*}aa^{*}}$

يبلغ ارتفاع النجمة على الأبجدية A = {a,b} 2. ومع ذلك، فإن اللغة الموصوفة هي مجرد مجموعة جميع الكلمات التي تنتهي بالحرف a ؛ وبالتالي يمكن وصف اللغة أيضًا بالتعبير

${\displaystyle \textstyle (a\,\mid \,b)^{*}a}$

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

يمكن حساب ارتفاع النجمة للغة المجموعة : على سبيل المثال، ارتفاع النجمة للغة على { a , b } التي يكون فيها عدد مرات ظهور a و b متطابقًا بتردد 2 ⁿ هو n . ^{[ 1 ]}

في دراسته الرائدة حول ارتفاع النجوم في اللغات المنتظمة، أرسى إيغان (1963) علاقة بين نظريات التعبيرات المنتظمة، والآلات المحدودة، والرسوم البيانية الموجهة . وفي السنوات اللاحقة، عُرفت هذه العلاقة باسم نظرية إيغان ، انظر ساكاروفيتش (2009) . نستذكر هنا بعض المفاهيم من نظرية الرسوم البيانية ونظرية الآلات .

في نظرية الرسم البياني، يتم تعريف رتبة الدورة r ( G ) للرسم البياني الموجه (digraph) G  =  ( V , E ) استقرائيًا على النحو التالي: 

• إذا كانت G غير دورية ، فإن r ( G )  =  0. وينطبق هذا بشكل خاص إذا كانت G فارغة.
• إذا كانت G متصلة بقوة و E غير فارغة، فإن

${\displaystyle r(G)=1+\min _{v\in V}r(Gv),\,}$ أين​${\displaystyle Gv}$⁠ هو الرسم البياني الموجه الناتج عن حذف الرأس v وجميع الحواف التي تبدأ أو تنتهي عند v .

• إذا لم تكن G متصلة بقوة، فإن r ( G ) يساوي الحد الأقصى لرتبة الدورة بين جميع المكونات المتصلة بقوة لـ G.

في نظرية الأوتوماتا، تُعرَّف الأوتوماتا المحدودة غير الحتمية ذات الانتقالات ε (ε-NFA) على أنها مجموعة خماسية ، ( Q ، Σ، δ ، q0 ، _F ) ، تتكون من

• مجموعة محدودة من الحالات Q
• مجموعة محدودة من رموز الإدخال Σ
• مجموعة من الحواف المصنفة δ ، يشار إليها باسم علاقة الانتقال : Q × (Σ ∪{ε}) × Q. هنا ε تشير إلى الكلمة الفارغة .
• حالة ابتدائية q ₀ ∈ Q​
• مجموعة من الحالات F تميز بأنها حالات قبول F ⊆ Q.

تُقبل الكلمة w ∈ Σ ^{* بواسطة آلة الحالة المحدودة غير القطعية ε-NFA إذا وُجد} مسار مُوجَّه من الحالة الابتدائية q ₀ إلى حالة نهائية ما في F باستخدام حواف من δ ، بحيث يُنتج تجميع جميع العلامات التي تمت زيارتها على طول المسار الكلمة w . مجموعة جميع الكلمات على Σ * ^التي تقبلها الآلة هي اللغة التي تقبلها الآلة A.

عند الحديث عن خصائص الرسم البياني الموجه لآلة حالة محدودة غير حتمية A ذات مجموعة حالات Q ، فإننا نتناول بشكل طبيعي الرسم البياني الموجه ذي مجموعة الرؤوس Q المستحثة بواسطة علاقة الانتقال الخاصة به. والآن، تُصاغ النظرية على النحو التالي.

نظرية إيجان : ارتفاع النجمة للغة منتظمة L يساوي الحد الأدنى لرتبة الدورة بين جميع الآلات المحدودة غير الحتمية ذات الانتقالات ε التي تقبل L.

تم تقديم البراهين لهذه النظرية بواسطة إيجان (1963) ، ومؤخراً بواسطة ساكاروفيتش (2009) .

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

${\displaystyle \textstyle h\left(E^{c}\right)\,=\,h(E)}$

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

لاحظ أنه بينما من البديهي أن لغة ذات ارتفاع نجمي (عادي) يساوي صفرًا لا يمكن أن تحتوي إلا على عدد محدود من الكلمات، توجد لغات لا نهائية ذات ارتفاع نجمي معمّم يساوي صفرًا. على سبيل المثال، التعبير النمطي

${\displaystyle \textstyle (a\,\mid \,b)^{*}a,}$

والتي رأيناها في المثال أعلاه، يمكن وصفها بشكل مكافئ بواسطة التعبير النمطي المعمم

${\displaystyle \textstyle \emptyset ^{c}a}$،

بما أن متممة المجموعة الفارغة هي بالضبط مجموعة جميع الكلمات على الأبجدية A ، فإن مجموعة جميع الكلمات على الأبجدية A التي تنتهي بالحرف a لها ارتفاع نجمي يساوي واحدًا، بينما ارتفاعها النجمي المعمم يساوي صفرًا.

تُسمى اللغات ذات الارتفاع النجمي المعمم الصفري أيضًا باللغات الخالية من النجوم . ويمكن إثبات أن اللغة L خالية من النجوم إذا وفقط إذا كانت أحاديتها النحوية غير دورية ( شوتزنبرغر (1965) ).

• مشكلة ارتفاع النجوم
• مشكلة ارتفاع النجوم المعممة

• بيرستل، جان؛ رويتناور، كريستوف (2011)، المتسلسلات الكسرية غير التبادلية مع تطبيقاتها ، موسوعة الرياضيات وتطبيقاتها، المجلد  137، كامبريدج: مطبعة جامعة كامبريدج ، ISBN 978-0-521-19022-0Zbl 1250.68007​ 
• كوهين، رينا س. (1971)، "تقنيات لتحديد ارتفاع النجوم للمجموعات المنتظمة"، نظرية أنظمة الحوسبة ، 5 (2): 97-114 ، doi : 10.1007/BF01702866 ، ISSN 1432-4350 ، S2CID 1970902 ، Zbl 0218.94028   
• كوهين، رينا س.؛ برزوزوفسكي، جيه إيه (1970)، "الخصائص العامة لارتفاع النجوم للأحداث المنتظمة"، مجلة علوم الحاسوب والأنظمة ، 4 (3): 260-280 ، doi : 10.1016/S0022-0000(70)80024-1 ، ISSN 0022-0000 ، Zbl 0245.94038  
• إيغان، لورانس سي. (1963)، "مخططات الانتقال وارتفاع النجمة للأحداث المنتظمة"، مجلة ميشيغان الرياضية ، 10 (4): 385-397 ، doi : 10.1307/mmj/1028998975 ، Zbl 0173.01504 
• ساكاروفيتش، جاك (2009)، عناصر نظرية الأوتوماتا ، ترجمة روبن توماس من الفرنسية، كامبريدج: مطبعة جامعة كامبريدج ، رقم ISBN 978-0-521-84425-3، Zbl 1188.68177 
• سالوما، أرتو (1981)، جواهر نظرية اللغة الرسمية ، روكفيل، ماريلاند: مطبعة علوم الحاسوب، رقم ISBN 978-0-914894-69-8، Zbl 0487.68064 
• شوتزنبرغر، إم بي (1965)، "حول الزمر الجزئية المنتهية التي تحتوي على زمر جزئية تافهة فقط"، المعلومات والتحكم ، 8 (2): 190-194 ، doi : 10.1016/S0019-9958(65)90108-7 ، ISSN 0019-9958 ، Zbl 0131.02001