الحاق (علوم رایانه)

در نظریهٔ محاسبات و مهندسی نرم‌افزار، عمل الحاق یا پیوند زنجیره‌ای (Concatenation) به عملی دوتایی گفته می‌شود که از دو رشتهٔ موجود رشتهٔ تازه‌ای می‌سازد، یا با الحاق دو زبان داده شده یک زبان جدید درست می‌کند.

نظریهٔ محاسبات

تعریف

الحاق زبان‌های $X$ و $Y$ با $XY$ نشان داده شده و به صورت زیر تعریف می‌گردد:

$XY=\{uv|u\in X\mathrm{a}\mathrm{n}\mathrm{d}v\in Y\}$

$n$ بار الحاق زبان $X$ با خودش را با $X^n$ نشان می‌دهیم، و $X^0$ به‌صورت $\{\lambda \}$ تعریف می‌شود.

مثال

دو زبان $X=\{a,b,c\}$ و $Y=\{bcc,cb\}$ را در نظر می‌گیریم . آنگاه داریم:

$XY=\{abcc,bbcc,cbcc,acb,bcb,ccb\}$

$X^0=\{\lambda \}$

$X^1=X=\{a,b,c\}$

$X^2=XX=\{aa,ab,ac,ba,bb,bc,ca,cb,cc\}$

$X^3=XXX=\{aaa,aab,aac,aba,abb,abc,aca,acb,acc,baa,bab,bac,bba,bbb,bbc,bca,bcb,bcc,caa,cab,cac,cba,cbb,cbc,cca,ccb,ccc\}$

ملاحظه: عمل دوتائی الحاق دو زبان $X$ و $Y$ در نظریه محاسبات، درست نظیر عمل دوتائی ضرب دکارتی دو مجموعه $X$ و $Y$ در نظریه مجموعه‌ها است، وقتی‌که، به جای عمل ضرب دو عنصر از مجموعه اول و مجموعه دوم، عمل الحاق دو رشته از زبان اول و زبان دوم را جایگزین نمائیم.

منابع

• Sudkamp, T. A., An Introduction to the Theory of Computer Science, Languages and Machines, 3rd ed., Pearson Education, Inc., 2006. الگو:ISBN [۱]