لغة خالية من النجوم

في علم الحاسوب النظري ونظرية اللغات الرسمية ، يُقال إن اللغة المنتظمة خالية من النجوم إذا أمكن وصفها بتعبير منتظم مُكوَّن من حروف الأبجدية ، والكلمة الفارغة ، ورمز المجموعة الفارغة ، وجميع عوامل التشغيل المنطقية - بما في ذلك المكمل - والتسلسل ، ولكن بدون نجمة كلين . ^{[ 1 ]} هذا الشرط يُكافئ أن يكون ارتفاع النجمة المعممة صفرًا.

على سبيل المثال، اللغة${\displaystyle \Sigma ^{*}}$من بين جميع الكلمات المحدودة على الأبجدية${\displaystyle \Sigma }$يمكن إثبات خلوها من النجوم عن طريق أخذ متممة المجموعة الفارغة.${\displaystyle \Sigma ^{*}={\bar {\emptyset }}}$ثم لغة الكلمات فوق الأبجدية${\displaystyle \{a,\,b\}}$يمكن تعريف الكلمات التي لا تحتوي على حرف "a" متتالي على النحو التالي:${\displaystyle {\overline {\Sigma ^{*}aa\Sigma ^{*}}}}$، أولاً بناء لغة الكلمات التي تتكون من${\displaystyle aa}$باستخدام بادئة ولاحقة عشوائيتين، ثم أخذ مكملها، والذي يجب أن يكون جميع الكلمات التي لا تحتوي على السلسلة الفرعية${\displaystyle aa}$.

مثال على لغة منتظمة لا تخلو من النجوم هو${\displaystyle (aa)^{*}}$[ ^{2 ]} أي لغة السلاسل المكونة من عدد زوجي من "a" ^.${\displaystyle (ab)^{*}}$أين${\displaystyle a\neq b}$يمكن تعريف اللغة على النحو التالي:${\displaystyle \Sigma ^{*}\setminus (b\Sigma ^{*}\cup \Sigma ^{*}a\cup \Sigma ^{*}aa\Sigma ^{*}\cup \Sigma ^{*}bb\Sigma ^{*})}$، بأخذ مجموعة جميع الكلمات وإزالة الكلمات التي تبدأ بـ${\displaystyle b}$، وتنتهي بـ${\displaystyle a}$أو تحتوي على${\displaystyle aa}$أو${\displaystyle bb}$لكن عندما${\displaystyle a=b}$هذا التعريف لا يُنشئ ${\displaystyle (aa)^{*}}$.

وصف مارسيل-بول شوتزنبرغر اللغات الخالية من النجوم بأنها تلك التي تحتوي على أحاديات نحوية غير دورية . ^{[ 3 ] [ 4 ]} ويمكن وصفها منطقيًا أيضًا بأنها لغات قابلة للتعريف في منطق الرتبة الأولى FO[<]، وهو منطق الرتبة الأولى على الأعداد الطبيعية مع علاقة أصغر من، ^{[ 5 ]} وبأنها لغات تقبلها بعض الآلات ذات الحالات المحدودة غير الدورية (المعروفة باسم اللغات الخالية من العدادات)، ^{[ 6 ]} وبأنها لغات قابلة للتعريف في منطق زمني خطي . ^{[ 7 ]}

جميع اللغات الخالية من النجوم تكون في AC ⁰ موحد .

يستغرق الأمر وقتًا غير بديهي لتحديد ما إذا كانت لغة خالية من النجوم تتكون من حرفين

تقول مشكلة الفراغ في لغة ستار فري:

• المدخلات: سلسلة نصية برموز${\displaystyle \{a,\,b\}}$، المجموعة الفارغة، والتسلسل، والاتحاد، والتقاطع، والمكمل.
• الناتج: ما إذا كانت هذه اللغة تحتوي على أي عنصر.

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

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

• لوسون، مارك ف. (2004). الأوتوماتا المحدودة . تشابمان آند هول/سي آر سي. رقم ISBN 1-58488-255-7. Zbl 1086.68074 . 
• ديكرت، فولكر؛ جاستين، بول (2008). "لغات قابلة للتعريف من الدرجة الأولى". في: يورغ فلوم؛ إريك غرادل؛ توماس ويلك (محررون). المنطق والأتمتة: التاريخ والآفاق (ملف PDF) . مطبعة جامعة أمستردام. ISBN 978-90-5356-576-6.