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

  لمعانٍ أخرى، طالع كلمة (توضيح).

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

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

تعريف

لتكن $\Sigma$ ألفبائية و$n$ عدد من $\mathbb {N} _{0}$، التي هي الأعداد الطبيعية التي تتضمن الصفر ($\mathbb {N} _{0}=\{0,1,2,\ldots \}$). أي كلمة $w$ بطول $n$ هي سلسلة محدودة الطول $(x_{1},x_{2},x_{3},\ldots ,x_{n})$ حيث $x_{i}\in \Sigma$ لكل $i\in \{1,\ldots ,n\}$.

الطول (وهو عدد رموز الكلمة) $n$ من أي كلمة $w$ يُكتب $|w|$، وعدد المرات الذي يأتي فيه حرف $x$ في كلمة $w$ يُكتب $|w|_{x}$.

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

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

أمثلة

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

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

تسلسل

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

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

وذلك عندما يكون تعريف الكلمتين هو $x=(x_{1},x_{2},x_{3},\ldots ,x_{n})$ و $y=(y_{1},y_{2},y_{3},\ldots ,y_{k})$ حيث $n,k\in \mathbb {N} _{0}$ و $x_{i},y_{j}\in \Sigma$ لكل $i\in \{1,\ldots ,n\}$ و $j\in \{1,\ldots ,k\}$. في هذا الحال تكن كلمة $x$ سابقة وتكن كلمة $y$ لاحقة لكلمة $x\circ y$. طول الكلمة المتسلسلة هي مجموع طول الكلمتين، أي:

$|x\circ y|=|x|+|y|$

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

$|x\circ y|_{s}=|x|_{s}+|y|_{s}$

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

$w\circ \varepsilon =\varepsilon \circ w=w$

التسلسل لم يكن عملية تبديلية، أي ليس دائمًا يكن $u\circ v=v\circ u$. على سبيل المثال:

$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$

انظر أيضًا

• حوسبة