نجمة كلين: الفرق بين النسختين
| [مراجعة غير مفحوصة] | [نسخة منشورة] |
تم حذف المحتوى تمت إضافة المحتوى
ط بوتة: تصحيح إملائي اعتمادا على هذه القائمة |
تنسيق |
||
سطر 1:
في [[المنطق الرياضي]] و[[علم الحاسوب]]، فان '''نجمة
# إذا كانت ''V'' عبارة عن مجموعة من السلاسل إذا يتم تعريف ''V'' * باعتبارها أصغر [[مجموعة جزئية]] من ''V'' والتي تحتوي على λ (السلسلة الفارغة) و[[تغلق]] بموجب [[عمليات تسلسل السلسلة]]. هذا ويمكن أيضا وصف هذه المجموعة بأنها مجموع من السلاسل التي يمكن إجراؤها بواسطة سلسلة الصفر أو المزيد من سلاسل ''V''.
سطر 7:
== التعريف والتدوين ==
المعطى
:<math> V_0=\{\lambda\}\,</math>
يحدد بشكل تكراري المجموعة
:<math> V_{i+1}=\{wv \mid w\in V_i \mbox{ and }
إذا كانت <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 \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>.
== انظر أيضا ==
* [[خوارزمية البحث بأولوية الأفضل]]
* [[جبر
* [[نموذج باكوس - ناور الموسع]]
* [[ضخ ليما]]
السطر 57 ⟵ 54:
* [[قاعدة أردن]]
==
تم العثور على تعريف نجمة
* [[John Hopcroft|John E. Hopcroft]] and [[Jeffrey Ullman|Jeffrey D. Ullman]]. Introduction to Automata Theory Languages and Computation. 1st edition. Addison-Wesley Publishing Company, 1979.
| |||