كلين ستار

في نظرية اللغة الرسمية ، يشير نجم كلين (أو عامل كلين أو إغلاق كلين ) إلى عمليتين أحاديتين مرتبطتين ، يمكن تطبيقهما إما على أبجدية من الرموز أو على لغة رسمية ، وهي مجموعة من السلاسل (تسلسلات محدودة من الرموز).

يُنشئ مُؤثر نجمة كلين على أبجدية V المجموعة V* التي تضم جميع السلاسل ذات الطول المحدود على V ، ^{[ ملاحظة 1 ]} أي المتتاليات المحدودة التي تنتمي عناصرها إلى V ؛ وفي الرياضيات، يُعرف هذا المؤثر باسم بناء المونويد الحر . كما يُنشئ مُؤثر نجمة كلين على لغة L لغة أخرى L* ، وهي مجموعة جميع السلاسل التي يُمكن الحصول عليها من خلال دمج صفر أو أكثر من عناصر L. وفي كلتا الحالتين، يُسمح بالتكرار.

سميت عوامل النجمة Kleene على اسم عالم الرياضيات الأمريكي ستيفن كول كلين ، الذي قدمها لأول مرة واستخدمها على نطاق واسع لتوصيف الأوتوماتا للتعبيرات النمطية .

بفرض وجود أبجدية${\displaystyle V}$، يُعرِّف

${\displaystyle V^{0}=\{\varepsilon \}}$(تتكون المجموعة من السلسلة الفارغة فقط)،

${\displaystyle V^{1}=V,}$

وحدد المجموعة بشكل متكرر

${\displaystyle V^{i+1}=\{wv:w\in V^{i}{\text{ and }}v\in V\}}$لكل${\displaystyle i>0,}$

أين${\displaystyle wv}$يشير إلى السلسلة التي تم الحصول عليها عن طريق إضافة حرف واحد${\displaystyle v}$حتى نهاية${\displaystyle w}$. هنا،${\displaystyle V^{i}}$يمكن فهمها على أنها مجموعة جميع السلاسل ذات الطول المحدد${\displaystyle i}$، مع شخصيات من${\displaystyle V}$.

تعريف نجمة كلين على${\displaystyle V}$هو ^{[ 1 ]}

${\displaystyle V^{*}=\bigcup _{i\geq 0}V^{i}=V^{0}\cup V^{1}\cup V^{2}\cup V^{3}\cup V^{4}\cup \cdots .}$

بافتراض لغة${\displaystyle L}$(أي مجموعة محدودة أو غير محدودة من السلاسل)، عرّف

${\displaystyle L^{0}=\{\varepsilon \}}$(اللغة التي تتكون فقط من السلسلة الفارغة)،

${\displaystyle L^{1}=L,}$

وحدد المجموعة بشكل متكرر

${\displaystyle L^{i+1}=\{wv:w\in L^{i}{\text{ and }}v\in L\}}$لكل${\displaystyle i>0,}$

أين${\displaystyle wv}$يشير إلى السلسلة التي تم الحصول عليها عن طريق دمج${\displaystyle w}$و${\displaystyle v}$. هنا،${\displaystyle L^{i}}$يمكن فهمها على أنها مجموعة جميع السلاسل التي يمكن الحصول عليها عن طريق دمجها بدقة${\displaystyle i}$سلاسل من${\displaystyle L}$، مما يسمح بالتكرار.

تعريف نجمة كلين على${\displaystyle L}$هو ^{[ 2 ]}

${\displaystyle L^{*}=\bigcup _{i\geq 0}L^{i}=L^{0}\cup L^{1}\cup L^{2}\cup L^{3}\cup L^{4}\cup \cdots .}$

في بعض الدراسات اللغوية الرسمية (مثل نظرية AFL )، يُستخدم شكلٌ مُعدَّل من عملية نجمة كلين يُسمى كلين بلس . يُحذف كلين بلس${\displaystyle V^{0}}$أو${\displaystyle L^{0}}$المصطلح في الاتحادات المذكورة أعلاه. بعبارة أخرى، كلين بلس على${\displaystyle V}$يكون

${\displaystyle V^{+}=\bigcup _{i\geq 1}V^{i}=V^{1}\cup V^{2}\cup V^{3}\cup \cdots ,}$

أو

${\displaystyle V^{+}=V^{*}V.}$^{[ ملاحظة 2 ]}

مثال على تطبيق نجمة كلين على مجموعة من الخيوط:

{"ab"،"c"} ^* = { ε، "ab"، "c"، "abab"، "abc"، "cab"، "cc"، "ababab"، "ababc"، "abcab"، "abcc"، "cabab"، "cabc"، "ccab"، "ccc"، ...}.

مثال على تطبيق علامة النجمة Kleene على مجموعة من السلاسل النصية بدون خاصية البادئة :

{"a","ab","b"} ^* = { ε, "a", "ab", "b", "aa", "aab", "aba", "abab", "abb", "ba", "bab", "bb", ...}; في هذا المثال، يمكن الحصول على السلسلة "aab" بطريقتين مختلفتين. يمكن استخدام خوارزمية سارديناس-باترسون للتحقق، بالنسبة لمجموعة بيانات V معينة، مما إذا كان من الممكن الحصول على أي عنصر من عناصر V ^* بأكثر من طريقة.

مثال على تطبيق Kleene و Kleene plus على مجموعة من الأحرف (وفقًا لاتفاقية لغة البرمجة C حيث يتم الإشارة إلى الحرف بعلامات اقتباس مفردة ويتم الإشارة إلى السلسلة بعلامات اقتباس مزدوجة):

{'a'، 'b'، 'c'} ^* = { ε، "a"، "b"، "c"، "aa"، "ab"، "ac"، "ba"، "bb"، "bc"، "ca"، "cb"، "cc"، "aaa"، "aab"، ...}.

{'a', 'b', 'c'} ⁺ = { "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc", "aaa", "aab", ...}.

• لو${\displaystyle V}$إذا كانت أي مجموعة من الأحرف محدودة أو غير محدودة قابلة للعد، فإن${\displaystyle V^{*}}$هي مجموعة غير منتهية قابلة للعد. ^{[ 1 ]} ونتيجة لذلك، فإن كل لغة رسمية على أبجدية منتهية أو غير منتهية قابلة للعد${\displaystyle \Sigma }$هي مجموعة قابلة للعد، لأنها مجموعة جزئية من المجموعة اللانهائية القابلة للعد${\displaystyle \Sigma ^{*}}$.
• ${\displaystyle (L^{*})^{*}=L^{*}}$وهذا يعني أن عامل النجمة كلين هو عامل أحادي متساوي القوة ، كما${\displaystyle (L^{*})^{i}=L^{*}}$لكل${\displaystyle i\geq 1}$.
• ${\displaystyle V^{*}=\{\varepsilon \}}$، لو${\displaystyle V}$المجموعة الفارغة ∅. بالنسبة لنسخة عامل النجمة كلين على اللغات،${\displaystyle L^{*}=\{\varepsilon \}}$متى${\displaystyle L}$إما أن تكون المجموعة فارغة ∅ أو مجموعة العناصر المفردة${\displaystyle \{\varepsilon \}}$.

تُشكّل السلاسل أحاديةً، حيث تُمثّل عملية الربط العملية الثنائية، وε العنصر المحايد. إضافةً إلى السلاسل، يُعرَّف نجم كلين لأي أحادية. بتعبير أدق، ليكن ( M , ⋅) أحادية، و S ⊆ M. عندئذٍ ، S ^* هي أصغر أحادية جزئية من M تحتوي على S ؛ أي أن S ^* تحتوي على العنصر المحايد في M ، وهو المجموعة S ، بحيث إذا كان x , y ∈ S ^* ، فإن x ⋅ y ∈ S ^* .

علاوة على ذلك، يتم تعميم نجمة كلين من خلال تضمين عملية * (واتحادها) في البنية الجبرية نفسها عن طريق مفهوم شبه الحلقة النجمية الكاملة . ^{[ 3 ]}

• حرف بديل
• غلوب (برمجة)

• هوبكروفت، جون إي .؛ أولمان، جيفري دي. (1979). مقدمة في نظرية الأوتوماتا واللغات والحوسبة (  الطبعة الأولى). أديسون-ويسلي .