عبد العزيز: بوت:إضافة بوابة (بوابة:رياضيات)

2023-05-11T04:35:52Z

بوت:إضافة بوابة (بوابة:رياضيات)

صفحة جديدة

{{لا مصدر|تاريخ=يناير 2022}}
{{بطاقة عامة}}
في [[منطق رياضي|المنطق الرياضي]] و[[علم الحاسوب]]، فان '''نجمة كلين''' (أو '''مشغل كلين''' أو '''الانغلاق كلين''') [[عملية أحادية]]، إما على [[مجموعة (رياضيات)|مجموعة]] من [[كلمة (علم الحاسوب النظري)|الكلمات]] أو على مجموعة من الرموز أو الحروف. يتم كتابة تطبيق النجمة كلين للمجموعة ''V'' على النحو ''V'' *. ويتم استخدامها على نطاق واسع لأشكال [[تعبير نمطي|التعابير النمطية]]، وهو السياق الذي قدم من قبل [[كلين ستيفن]] لتوصيف [[نظرية التشغيل الذاتي]] بعينها، حيث تعني «صفر أو أكثر».
# إذا كانت ''V'' عبارة عن مجموعة من السلاسل إذا يتم تعريف ''V'' * باعتبارها أصغر [[مجموعة جزئية]] من ''V'' والتي تحتوي على [[سلسلة فارغة|الكلمة الفارغة]] و[[تغلق]] بموجب [[كلمة_(علم_الحاسوب_النظري)#تسلسل|عمليات تسلسل الكلمات]]. هذا ويمكن أيضا وصف هذه المجموعة بأنها مجموع من السلاسل التي يمكن إجراؤها بواسطة سلسلة الصفر أو المزيد من سلاسل ''V''.
# إذا كانت ''V'' عبارة عن مجموعة من الرموز أو الأحرف إذا ''V'' * هي مجموعة لكل السلاسل خلال رموز المجموعة ''V''، بما في ذلك الكلمة الفارغة.

يتم استخدام العمليات في [[إعادة كتابة القواعد]] [[للقواعد المحدثة]].

== التعريف والتدوين ==
المعطى
:<math> V_0=\{\lambda\}\,</math>
يحدد بشكل تكراري المجموعة
:<math> V_{i+1}=\{wv \mid w\in V_i \mbox{ and } v \in V\}\,</math> حيث <math>i \ge 0\,</math>.

إذا كانت <math>V</math> لغة رسمية، إذا <math> V_i</math> والتي هي القوة (الاس) الذي يرمز له ب ''i''-th من المجموعة <math>V</math> ، يعتبر اختصار [[كلمة_(علم_الحاسوب_النظري)#تسلسل|لتسلسل]]
المجموعة <math>V</math> مع نفسها i من مرات. ولذا <math> V_i</math> يمكن أن يتم فهمه على انه مجموعة لجميع [[كلمة (علم الحاسوب النظري)|الكلمات]] التي يمكن أن تتمثل على نحو تسلسل للكلمة ''i'' في المجموعة <math>V</math>.
تعريف النجمة كلين هو <math> V^*=\bigcup_{i \in \N}V_i = \left \{\lambda \right\} \cup V_1 \cup V_2 \cup V_3 \cup \ldots.</math>

ولذا هذا هو تجميع لكافة السلاسل محدودة الطول المحتملة المتولدة من الرموز في <math>V</math>.

في بعض دراسات [[لغة شكلية|اللغة الشكلية]]، (مثل [[نظرية أفل]]) فان الاختلاف على عملية نجمة كلين سميت باسم ''كلين زائد'' وتم استخدامها بالفعل. وزائد كلين يحذف الحد <math>V_0</math> في الاتحاد أعلاه. وبعبارة أخرى، زائد كلين هي في المجموعة <math>V</math> <math>V</math> is
<math> V^+=\bigcup_{i \in \N \setminus \{0\}}\!\!\!\! V_i = V_1 \cup V_2 \cup V_3 \cup \ldots.</math>

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

== أمثلة ==
امثلة على تطبيق نجمة كلين على مجموعة من السلاسل:
: {"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",...}.

امثلة على تطبيق نجمة كلين على المجموعة الفارغة:
:<math>\varnothing ^* =\{\lambda\}.</math>

امثلة على تطبيق زائد كلين على المجموعة الفارغة:
:<math>\varnothing ^+ = \varnothing \varnothing ^* =\{\}= \varnothing. </math>

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

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

== انظر أيضا ==
* [[خوارزمية البحث بأولوية الأفضل]]
* [[النظرية المثالية]]
* [[كاشف التسلسل]]
== مراجع ==
{{مراجع}}
تم العثور على تعريف نجمة كلين في تقريبا كل في كتاب عن نظرية كاشف التسلسل. المرجع النوذجي ما يلي:
* [[جون هوبكروفت]] and [[جيفري أولمان]]. Introduction to Automata Theory Languages and Computation. 1st edition. Addison-Wesley Publishing Company, 1979.
{{شريط بوابات|رياضيات|علم الحاسوب|منطق}}

[[تصنيف:قواعد اللغة]]
[[تصنيف:لغات شكلية]]
[[تصنيف:معالجة اللغات الطبيعية]]

نجمة كلين - تاريخ المراجعة

عبد العزيز: بوت:إضافة بوابة (بوابة:رياضيات)