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

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

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

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

${\displaystyle |x\circ y|=|x|+|y|}$

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

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

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

${\displaystyle w\circ \varepsilon =\varepsilon \circ w=w}$

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

${\displaystyle 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}$