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

{{عن|3=كلمة (توضيح)}}
في [[علم الحاسوب النظري]] '''الكلمة''' هي سلسلة محدودة الطول مأخوذة من [[محرف (حوسبة)|رموز]] [[ألفبائية (حوسبة)|ألفبائية]].<ref name="petersen3">{{استشهاد ويب | عنوان=Introduction to the Theory of Formal Languages | مسار= https://user.phil.hhu.de/~petersen/Riga/print_Folien_Riga_NLT.pdf |الأخير=Wiebke |الأول=Petersen | مكان=Riga | تاريخ الوصول=25 يناير 2021 |لغة=الإنجليزية| سنة=2006  | صفحة=3 | مسار أرشيف = https://web.archive.org/web/20210125035601/https://user.phil.hhu.de/~petersen/Riga/print_Folien_Riga_NLT.pdf | تاريخ أرشيف = 2021-01-25|حالة المسار = }}</ref> على عكس الكلمة في [[لغة طبيعية|اللغة الطبيعية]] التي دائمًا مرتبطة بمعنى، فإن الكلمة في علم الحاسوب النظري ليس لها معنى لغوي، بل هي مجرد مصطلح آخر [[سلسلة (علم الحاسوب)|لسلسلة من الرموز]].

الكلمات هي عناصر [[لغة شكلية|اللغة الشكلية]]،<ref>{{استشهاد ويب | عنوان=Introduction to the Theory of Formal Languages | مسار= https://user.phil.hhu.de/~petersen/Riga/print_Folien_Riga_NLT.pdf |الأخير=Wiebke |الأول=Petersen | مكان=Riga | تاريخ الوصول=25 يناير 2021 |لغة=الإنجليزية| سنة=2006  | صفحة=7 | مسار أرشيف = https://web.archive.org/web/20210125035601/https://user.phil.hhu.de/~petersen/Riga/print_Folien_Riga_NLT.pdf | تاريخ أرشيف = 2021-01-25|حالة المسار = }}</ref> لذلك هي مهمة [[نموذج رياضي|للنمذجة الرياضية]]، لنظرية [[لغة برمجة|لغات البرمجة]]، لل[[نظرية الحاسوبية]]، ولغيرها من مجالات علم الحاسوب النظري.

== تعريف ==
لتكن <math>\Sigma</math> ألفبائية و<math>n</math> عدد من <math>\mathbb{N}_{0}</math>، التي هي [[عدد طبيعي|الأعداد الطبيعية]] التي تتضمن الصفر (<math>\mathbb{N}_{0} = \{ 0, 1, 2, \ldots \}</math>). أي كلمة <math>w</math> بطول <math>n</math> هي سلسلة محدودة الطول <math>(x_{1}, x_{2}, x_{3}, \ldots, x_{n})</math> حيث <math>x_{i} \in \Sigma</math> لكل <math>i \in \{ 1, \ldots, n \}</math>.<ref name="petersen3"/>

الطول (وهو عدد رموز الكلمة) <math>n</math> من أي كلمة <math>w</math> يُكتب <math>|w|</math>،<ref name="petersen3"/> وعدد المرات الذي يأتي فيه حرف <math>x</math> في كلمة <math>w</math> يُكتب <math>|w|_x</math>.<ref name="KR1994">Klaus Reinhardt: [http://users.informatik.uni-halle.de/~ahyjb/dis.pdf ''Prioritatszahlerautomaten und die Synchronisation von Halbspursprachen''], Fakultät Informatik der Universität Stuttgart; Doktorarbeit 1994 (PDF; 509&nbsp;KB) {{Webarchive|url=https://web.archive.org/web/20180117143012/http://users.informatik.uni-halle.de/~ahyjb/dis.pdf|date=2018-01-17}}</ref><ref>{{استشهاد ويب | عنوان=Introduction to Theoretical Computer Science | مسار=http://www.cs.vsb.cz/sawa/uti/slides/uti-06-en.pdf |الأخير=Sawa |الأول=Z | تاريخ الوصول=25 يناير 2021 |لغة=الإنجليزية| سنة=2020  | صفحة=8 | مسار أرشيف = https://web.archive.org/web/20160717173752/http://www.cs.vsb.cz/sawa/uti/slides/uti-06-en.pdf| تاريخ أرشيف = 17 يوليو 2016|حالة المسار = }}</ref>

كلمة مميزة هي [[سلسلة فارغة|الكلمة الفارغة]] التي تتكون من لا رمز (طولها 0) وعادة ما تُكتب بالحرف الإغريقي <math>\varepsilon</math> (إبسيلون).<ref name="petersen3"/> مجموعة كل الكلمات التي يمكن العثور عليها من ألفبائية <math>\Sigma</math> تسمى [[نجمة كلين]].<ref>{{استشهاد ويب |مؤلف=Nayuki Minase |تاريخ=10 May 2011 |عنوان=Countable sets and Kleene star |عمل=Project Nayuki |مسار=http://www.nayuki.io/page/countable-sets-and-kleene-star |تاريخ الوصول=25 January 2021| مسار أرشيف = https://web.archive.org/web/20201102013200/https://www.nayuki.io/page/countable-sets-and-kleene-star | تاريخ أرشيف = 2 نوفمبر 2020 }}</ref>

غالبًا تُكتب الكلمات بالطريقة المبسطة <math>w=x_{1} x_{2} x_{3} \ldots x_{n}</math>.

== أمثلة ==
لتكن <math>\Sigma_{1}</math> ال[[ألفبائية]] اللاتينية، و <math>\Sigma_{2} = \lbrace \diamondsuit, \heartsuit, \spadesuit, \clubsuit \rbrace</math>. من ثَم تكن <math>w_{1}=book</math> و <math>w_{2} = xyzzy</math> أمثلة لكلمات من الألفبائية <math>\Sigma_{1}</math>، و <math>w_{3} = \heartsuit \clubsuit \clubsuit \heartsuit \spadesuit</math> مثال لكلمة من <math>\Sigma_{2}</math>. كما أن طول الكلمات هي <math>|w_{1}|=4</math> و <math>|w_{2}|=|w_{3}|=5</math>. يأتي رمز <math>\clubsuit</math> مرتين في كلمة <math>w_{3}</math>، لذلك <math>|w_{3}|_{\clubsuit}=2</math>.

== العمليات على الكلمات ==
=== تسلسل ===
التَسَلسُل هو [[عملية ثنائية]] يربط كلمتين ليصبحوا كلمة واحدة،<ref>{{استشهاد ويب | عنوان=Introduction to Theoretical Computer Science | مسار= http://www.cs.vsb.cz/sawa/uti/slides/uti-06-en.pdf |الأخير=Sawa |الأول=Z | تاريخ الوصول=25 يناير 2021 |لغة=الإنجليزية| سنة=2020  | صفحة=9 | مسار أرشيف = https://web.archive.org/web/20160717173752/http://www.cs.vsb.cz:80/sawa/uti/slides/uti-06-en.pdf | تاريخ أرشيف = 2016-07-17|حالة المسار = }}</ref> عن طريق إضافة رموز الكلمة الثانية إلى نهاية الكلمة الأولى دون تغيير ترتيبهم. تسلسل الكلمتين <math>x</math> و <math>y</math> من ألفبائية <math>\Sigma</math> يُكتب <math>xy</math> أو <math>x \circ y</math> وتعريفه هو:<ref name="petersen5">{{استشهاد ويب | عنوان=Introduction to the Theory of Formal Languages | مسار= https://user.phil.hhu.de/~petersen/Riga/print_Folien_Riga_NLT.pdf |الأخير=Wiebke |الأول=Petersen | مكان=Riga | تاريخ الوصول=25 يناير 2021 |لغة=الإنجليزية| سنة=2006  | صفحة=5 | مسار أرشيف = https://web.archive.org/web/20210125035601/https://user.phil.hhu.de/~petersen/Riga/print_Folien_Riga_NLT.pdf | تاريخ أرشيف = 2021-01-25|حالة المسار = }}</ref>

:<math>xy = x \circ y := (x_{1}, x_{2}, x_{3}, \ldots, x_{n}, y_{1}, y_{2}, y_{3}, \ldots, y_{k})</math>

وذلك عندما يكون تعريف الكلمتين هو <math>x=(x_{1}, x_{2}, x_{3}, \ldots, x_{n})</math> و <math>y=(y_{1}, y_{2}, y_{3}, \ldots, y_{k})</math> حيث <math>n,k \in \mathbb{N}_{0}</math> و <math>x_{i},y_{j} \in \Sigma</math> لكل <math>i \in \{ 1, \ldots, n \}</math> و <math>j \in \{ 1, \ldots, k \}</math>. في هذا الحال تكن كلمة <math>x</math> [[سابقة]] وتكن كلمة <math>y</math> [[لاحقة]] لكلمة <math>x \circ y</math>.<ref>{{استشهاد ويب | عنوان=Introduction to Theoretical Computer Science | مسار= http://www.cs.vsb.cz/sawa/uti/slides/uti-06-en.pdf |الأخير=Sawa |الأول=Z | تاريخ الوصول=25 يناير 2021 |لغة=الإنجليزية| سنة=2020  | صفحة=11 | مسار أرشيف = https://web.archive.org/web/20160717173752/http://www.cs.vsb.cz:80/sawa/uti/slides/uti-06-en.pdf | تاريخ أرشيف = 2016-07-17|حالة المسار = }}</ref> طول الكلمة المتسلسلة هي مجموع طول الكلمتين، أي:

:<math>|x \circ y| = |x| + |y|</math>

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

:<math>|x\circ y|_s = |x|_s + |y|_s</math>

[[عنصر محايد|العنصر المحايد]] للتسلسل هو الكلمة الفارغة، لأن دائمًا يكن لأي كلمة <math>w</math>:<ref name="petersen5"/>

:<math>w \circ \varepsilon = \varepsilon \circ w = w</math>

التسلسل لم يكن [[عملية تبديلية]]، أي ليس دائمًا يكن <math> u \circ v = v \circ u</math>.<ref>{{استشهاد ويب | عنوان=Introduction to Theoretical Computer Science | مسار= http://www.cs.vsb.cz/sawa/uti/slides/uti-06-en.pdf |الأخير=Sawa |الأول=Z | تاريخ الوصول=25 يناير 2021 |لغة=الإنجليزية| سنة=2020  | صفحة=10 | مسار أرشيف = https://web.archive.org/web/20160717173752/http://www.cs.vsb.cz:80/sawa/uti/slides/uti-06-en.pdf | تاريخ أرشيف = 2016-07-17|حالة المسار = }}</ref> على سبيل المثال:

:<math>haus \circ \heartsuit \clubsuit \clubsuit \heartsuit \spadesuit = haus \heartsuit \clubsuit \clubsuit \heartsuit \spadesuit \not= \heartsuit \clubsuit \clubsuit \heartsuit \spadesuit haus = \heartsuit \clubsuit \clubsuit \heartsuit \spadesuit \circ haus</math>

== انظر أيضًا ==
* [[حوسبة]]

== مراجع ==
{{مراجع}}

{{معلوماتية}}
{{شريط بوابات|تقنية المعلومات|رياضيات|علم الحاسوب}}

[[تصنيف:رياضيات متقطعة]]
[[تصنيف:لغات شكلية]]
[[تصنيف:معلوماتية نظرية]]