كلمة (علم الحاسوب النظري)

سلسلة رموز محدودة من ألفبائية في علم الحاسوب النظري

في علم الحاسوب النظري الكلمة هي سلسلة محدودة الطول مأخوذة من رموز ألفبائية.[1] على عكس الكلمة في اللغة الطبيعية التي دائمًا مرتبطة بمعنى، فإن الكلمة في علم الحاسوب النظري ليس لها معنى لغوي، بل هي مجرد مصطلح آخر لسلسلة من الرموز.

الكلمات هي عناصر اللغة الشكلية،[2] لذلك هي مهمة للنمذجة الرياضية، لنظرية لغات البرمجة، للنظرية الحاسوبية، ولغيرها من مجالات علم الحاسوب النظري.

تعريفعدل

لتكن   ألفبائية و  عدد من  ، التي هي الأعداد الطبيعية التي تتضمن الصفر ( ). أي كلمة   بطول   هي سلسلة محدودة الطول   حيث   لكل  .[1]

الطول (وهو عدد رموز الكلمة)   من أي كلمة   يُكتب  ،[1] وعدد المرات الذي يأتي فيه حرف   في كلمة   يُكتب  .[3][4]

كلمة مميزة هي الكلمة الفارغة التي تتكون من لا رمز (طولها 0) وعادة ما تُكتب بالحرف الإغريقي   (إبسيلون).[1] مجموعة كل الكلمات التي يمكن العثور عليها من ألفبائية   تسمى نجمة كلين.[5]

غالبًا تُكتب الكلمات بالطريقة المبسطة  .

أمثلةعدل

لتكن   الألفبائية اللاتينية، و  . من ثَم تكن   و   أمثلة لكلمات من الألفبائية  ، و   مثال لكلمة من  . كما أن طول الكلمات هي   و  . يأتي رمز   مرتين في كلمة  ، لذلك  .

العمليات على الكلماتعدل

تسلسلعدل

التَسَلسُل هو عملية ثنائية يربط كلمتين ليصبحوا كلمة واحدة،[6] عن طريق إضافة رموز الكلمة الثانية إلى نهاية الكلمة الأولى دون تغيير ترتيبهم. تسلسل الكلمتين   و   من ألفبائية   يُكتب   أو   وتعريفه هو:[7]

 

وذلك عندما يكون تعريف الكلمتين هو   و   حيث   و   لكل   و  . في هذا الحال تكن كلمة   سابقة وتكن كلمة   لاحقة لكلمة  .[8] طول الكلمة المتسلسلة هي مجموع طول الكلمتين، أي:

 

وعدد المرات الذي يأتي فيه رمز   هو:

 

العنصر المحايد للتسلسل هو الكلمة الفارغة، لأن دائمًا يكن لأي كلمة  :[7]

 

التسلسل لم يكن عملية تبديلية، أي ليس دائمًا يكن  .[9] على سبيل المثال:

 

انظر أيضًاعدل

مراجععدل

  1. أ ب ت ث Wiebke, Petersen (2006). "Introduction to the Theory of Formal Languages" (PDF) (باللغة الإنجليزية). Riga. صفحة 3. مؤرشف من الأصل (PDF) في 25 يناير 2021. اطلع عليه بتاريخ 25 يناير 2021. الوسيط |CitationClass= تم تجاهله (مساعدة)
  2. ^ Wiebke, Petersen (2006). "Introduction to the Theory of Formal Languages" (PDF) (باللغة الإنجليزية). Riga. صفحة 7. مؤرشف من الأصل (PDF) في 25 يناير 2021. اطلع عليه بتاريخ 25 يناير 2021. الوسيط |CitationClass= تم تجاهله (مساعدة)
  3. ^ Klaus Reinhardt: Prioritatszahlerautomaten und die Synchronisation von Halbspursprachen, Fakultät Informatik der Universität Stuttgart; Doktorarbeit 1994 (PDF; 509 KB) نسخة محفوظة 2018-01-17 على موقع واي باك مشين.
  4. ^ Sawa, Z (2020). "Introduction to Theoretical Computer Science" (PDF) (باللغة الإنجليزية). صفحة 8. مؤرشف من الأصل (PDF) في 17 يوليو 2016. اطلع عليه بتاريخ 25 يناير 2021. الوسيط |CitationClass= تم تجاهله (مساعدة)
  5. ^ Nayuki Minase (10 May 2011). "Countable sets and Kleene star". Project Nayuki. مؤرشف من الأصل في 2 نوفمبر 2020. اطلع عليه بتاريخ 25 يناير 2021. الوسيط |CitationClass= تم تجاهله (مساعدة)
  6. ^ Sawa, Z (2020). "Introduction to Theoretical Computer Science" (PDF) (باللغة الإنجليزية). صفحة 9. مؤرشف من الأصل (PDF) في 17 يوليو 2016. اطلع عليه بتاريخ 25 يناير 2021. الوسيط |CitationClass= تم تجاهله (مساعدة)
  7. أ ب Wiebke, Petersen (2006). "Introduction to the Theory of Formal Languages" (PDF) (باللغة الإنجليزية). Riga. صفحة 5. مؤرشف من الأصل (PDF) في 25 يناير 2021. اطلع عليه بتاريخ 25 يناير 2021. الوسيط |CitationClass= تم تجاهله (مساعدة)
  8. ^ Sawa, Z (2020). "Introduction to Theoretical Computer Science" (PDF) (باللغة الإنجليزية). صفحة 11. مؤرشف من الأصل (PDF) في 17 يوليو 2016. اطلع عليه بتاريخ 25 يناير 2021. الوسيط |CitationClass= تم تجاهله (مساعدة)
  9. ^ Sawa, Z (2020). "Introduction to Theoretical Computer Science" (PDF) (باللغة الإنجليزية). صفحة 10. مؤرشف من الأصل (PDF) في 17 يوليو 2016. اطلع عليه بتاريخ 25 يناير 2021. الوسيط |CitationClass= تم تجاهله (مساعدة)