نجمة كلين

المعطى

${\displaystyle V_{0}=\{\lambda \}\,}$

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

${\displaystyle V_{i+1}=\{wv\mid w\in V_{i}{\mbox{ and }}v\in V\}\,}$ حيث ${\displaystyle i\geq 0\,}$.

إذا كانت ${\displaystyle V}$ لغة رسمية، إذا ${\displaystyle V_{i}}$ والتي هي القوة (الاس) الذي يرمز له ب i-th من المجموعة ${\displaystyle V}$ ، يعتبر اختصار لتسلسل المجموعة ${\displaystyle V}$ مع نفسها i من مرات. ولذا ${\displaystyle V_{i}}$ يمكن أن يتم فهمه على انه مجموعة لجميع الكلمات التي يمكن أن تتمثل على نحو تسلسل للكلمة i في المجموعة ${\displaystyle V}$. تعريف النجمة كلين هو ${\displaystyle V^{*}=\bigcup _{i\in \mathbb {N} }V_{i}=\left\{\lambda \right\}\cup V_{1}\cup V_{2}\cup V_{3}\cup \ldots .}$

ولذا هذا هو تجميع لكافة السلاسل محدودة الطول المحتملة المتولدة من الرموز في ${\displaystyle V}$.

في بعض دراسات اللغة الشكلية، (مثل نظرية أفل) فان الاختلاف على عملية نجمة كلين سميت باسم كلين زائد وتم استخدامها بالفعل. وزائد كلين يحذف الحد ${\displaystyle V_{0}}$ في الاتحاد أعلاه. وبعبارة أخرى، زائد كلين هي في المجموعة ${\displaystyle V}$ ${\displaystyle V}$ is ${\displaystyle V^{+}=\bigcup _{i\in \mathbb {N} \setminus \{0\}}\!\!\!\!V_{i}=V_{1}\cup V_{2}\cup V_{3}\cup \ldots .}$

بالإضافة إلى ذلك، يتم استخدام نجمة كلين في النظرية المثالية.

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

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

امثلة على تطبيق نجمة كلين على مجموعة من الأحرف:

{'a', 'b', 'c'}* = {λ, "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc",...}.

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

${\displaystyle \varnothing ^{*}=\{\lambda \}.}$

امثلة على تطبيق زائد كلين على المجموعة الفارغة:

${\displaystyle \varnothing ^{+}=\varnothing \varnothing ^{*}=\{\}=\varnothing .}$

لاحظ انه لكل مجموعة L, ${\displaystyle L^{+}}$تساوي التسلسل في L مع${\displaystyle L^{*}}$. للمقارنة ${\displaystyle L^{*}}$ يمكن كتابتها مثل ${\displaystyle \{\lambda \}\cup L^{+}}$. العمليات ${\displaystyle L^{+}}$ and ${\displaystyle L^{*}}$ يمكن ان تصف المجموعة ذاتها فقط وفقط إذا كانت المجموعة L قيد البحث تتضمن العبارة الفارغة.

السلاسل التي تشكل البنية الجبرية مونويد مع تسلسل كما في العملية الثنائية وλ العنصر المحايد. يتم تعريف نجمة كلين لأي مونويد وليس فقط للسلاسل. بالتحديد، فلتكن ${\displaystyle (M,\cdot )}$ مونويد${\displaystyle S\subseteq M}$. ثم ${\displaystyle S^{*}}$ هي أصغر مونويد فرعية ل ${\displaystyle M}$ تحتوي على ${\displaystyle S}$، ولهذا ، ${\displaystyle S^{*}}$ تتضمن العنصر المحايد من ${\displaystyle (M,\cdot )}$، وهو مجموعة ${\displaystyle (M,\cdot )}$ ، وبحيث لو ${\displaystyle x,y\in S^{*}}$ إذا ${\displaystyle x\cdot y\in S^{*}}$.

• خوارزمية البحث بأولوية الأفضل
• النظرية المثالية
• كاشف التسلسل

تم العثور على تعريف نجمة كلين في تقريبا كل في كتاب عن نظرية كاشف التسلسل. المرجع النوذجي ما يلي:

• جون هوبكروفت and جيفري أولمان. Introduction to Automata Theory Languages and Computation. 1st edition. Addison-Wesley Publishing Company, 1979.

• بوابة علم الحاسوب
• بوابة منطق