نجمة كليين

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث

في المنطق الرياضي وعلم الحاسوب، فان نجمة كليين (أو مشغل كليين أو الانغلاق كليين) عملية أحادية، إما على مجموعة من السلاسل أو على مجموعة من الرموز أو الحروف. يتم كتابة تطبيق النجمة كليين للمجموعة V على النحو V *. ويتم استخدامها على نطاق واسع لأشكال التعابير النمطية، وهو السياق الذي قدم من قبل كليين ستيفن لتوصيف نظرية التشغيل الذاتي بعينها، حيث تعني "صفر أو أكثر".

  1. إذا كانت V عبارة عن مجموعة من السلاسل إذا يتم تعريف V * باعتبارها أصغر مجموعة جزئية من V والتي تحتوي على λ (السلسلة الفارغة) وتغلق بموجب عمليات تسلسل السلسلة. هذا ويمكن أيضا وصف هذه المجموعة بأنها مجموع من السلاسل التي يمكن إجراؤها بواسطة سلسلة الصفر أو المزيد من سلاسل V.
  2. إذا كانت V عبارة عن مجموعة من الرموز أو الأحرف إذا V * هي مجموعة لكل السلاسل خلال رموز المجموعة V، بما في ذلك السلسلة الفارغة.

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

التعريف والتدوين[عدل]

المعطى

 V_0=\{\lambda\}\,

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

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

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

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

في بعض دراسات اللغة الشكلية، (مثل نظرية أفل) فان الاختلاف على عملية نجمة كليين سميت باسم كليين زائد وتم استخدامها بالفعل. وزائد كليين يحذف الحد V_0 في الاتحاد أعلاه. وبعبارة أخرى ، زائد كليين هي في المجموعة V V is  V^+=\bigcup_{i \in \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",...}.

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

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

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

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

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

تعميم[عدل]

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

انظر أيضا[عدل]

المراجع[عدل]

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