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

من أرابيكا، الموسوعة الحرة

هذه هي النسخة الحالية من هذه الصفحة، وقام بتعديلها عبود السكاف (نقاش | مساهمات) في 08:39، 20 مارس 2023 (بوت: إصلاح أخطاء فحص أرابيكا من 1 إلى 104). العنوان الحالي (URL) هو وصلة دائمة لهذه النسخة.

(فرق) → نسخة أقدم | نسخة حالية (فرق) | نسخة أحدث ← (فرق)
اذهب إلى التنقل اذهب إلى البحث

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

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

تعريف

لتكن Σ ألفبائية وn عدد من N0، التي هي الأعداد الطبيعية التي تتضمن الصفر (N0={0,1,2,}). أي كلمة w بطول n هي سلسلة محدودة الطول (x1,x2,x3,,xn) حيث xiΣ لكل i{1,,n}.[1]

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

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

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

أمثلة

لتكن Σ1 الألفبائية اللاتينية، و Σ2={,,,}. من ثَم تكن w1=book و w2=xyzzy أمثلة لكلمات من الألفبائية Σ1، و w3= مثال لكلمة من Σ2. كما أن طول الكلمات هي |w1|=4 و |w2|=|w3|=5. يأتي رمز مرتين في كلمة w3، لذلك |w3|=2.

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

تسلسل

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

xy=xy:=(x1,x2,x3,,xn,y1,y2,y3,,yk)

وذلك عندما يكون تعريف الكلمتين هو x=(x1,x2,x3,,xn) و y=(y1,y2,y3,,yk) حيث n,kN0 و xi,yjΣ لكل i{1,,n} و j{1,,k}. في هذا الحال تكن كلمة x سابقة وتكن كلمة y لاحقة لكلمة xy.[8] طول الكلمة المتسلسلة هي مجموع طول الكلمتين، أي:

|xy|=|x|+|y|

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

|xy|s=|x|s+|y|s

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

wε=εw=w

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

haus=haus=haus=haus

انظر أيضًا

مراجع

  1. ^ أ ب ت ث Wiebke, Petersen (2006). "Introduction to the Theory of Formal Languages" (PDF) (بالإنجليزية). Riga. p. 3. Archived from the original (PDF) on 2021-01-25. Retrieved 2021-01-25.{{استشهاد ويب}}: صيانة الاستشهاد: لغة غير مدعومة (link)
  2. ^ Wiebke, Petersen (2006). "Introduction to the Theory of Formal Languages" (PDF) (بالإنجليزية). Riga. p. 7. Archived from the original (PDF) on 2021-01-25. Retrieved 2021-01-25.{{استشهاد ويب}}: صيانة الاستشهاد: لغة غير مدعومة (link)
  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) (بالإنجليزية). p. 8. Archived from the original (PDF) on 2016-07-17. Retrieved 2021-01-25.{{استشهاد ويب}}: صيانة الاستشهاد: لغة غير مدعومة (link)
  5. ^ Nayuki Minase (10 مايو 2011). "Countable sets and Kleene star". Project Nayuki. مؤرشف من الأصل في 2020-11-02. اطلع عليه بتاريخ 2021-01-25.
  6. ^ Sawa, Z (2020). "Introduction to Theoretical Computer Science" (PDF) (بالإنجليزية). p. 9. Archived from the original (PDF) on 2016-07-17. Retrieved 2021-01-25.{{استشهاد ويب}}: صيانة الاستشهاد: لغة غير مدعومة (link)
  7. ^ أ ب Wiebke, Petersen (2006). "Introduction to the Theory of Formal Languages" (PDF) (بالإنجليزية). Riga. p. 5. Archived from the original (PDF) on 2021-01-25. Retrieved 2021-01-25.{{استشهاد ويب}}: صيانة الاستشهاد: لغة غير مدعومة (link)
  8. ^ Sawa, Z (2020). "Introduction to Theoretical Computer Science" (PDF) (بالإنجليزية). p. 11. Archived from the original (PDF) on 2016-07-17. Retrieved 2021-01-25.{{استشهاد ويب}}: صيانة الاستشهاد: لغة غير مدعومة (link)
  9. ^ Sawa, Z (2020). "Introduction to Theoretical Computer Science" (PDF) (بالإنجليزية). p. 10. Archived from the original (PDF) on 2016-07-17. Retrieved 2021-01-25.{{استشهاد ويب}}: صيانة الاستشهاد: لغة غير مدعومة (link)