الحاق (علوم کامپیوتر)

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

نظریهٔ محاسبات[ویرایش]

نوشتار اصلی: نظریه محاسبات


تعریف[ویرایش]

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

X Y = \{ uv | u \in X\;\mathrm{and}\;v \in Y \} \!

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

مثال[ویرایش]

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

X Y = \{abcc, bbcc, cbcc, acb, bcb, ccb\} \!

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

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

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

X^{3} = X X X = \{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 \! در نظریه مجموعه‌ها است، وقتی‌که، به جای عمل ضرب دو عنصر از مجموعه اول و مجموعه دوم، عمل الحاق دو رشته از زبان اول و زبان دوم را جایگزین نمائیم.

پانویس[ویرایش]

  1. String
  2. An Introduction to the Theory of Computer Science, p. ۴۷

منابع[ویرایش]

  • Sudkamp, T. A., An Introduction to the Theory of Computer Science, Languages and Machines, 3rd ed., Pearson Education, Inc., 2006. ISBN 0-321-32221-5 [۱]
عملیات دوتایی
عددی تابعی مجموعه‌ای ساختاری
مقدماتی

+ جمع
تفریق
× ضرب
÷ تقسیم
^ توان

حسابی

div خارج قسمت اقلیدسی
mod باقیمانده اقلیدسی
بزرگترین مقسوم علیه مشترک
کوچکترین مضرب مشترک

ترکیباتی

( ) ضریب بینم
A جایگشت

ترکیب
کانولوشن
جبر مجموعه‌ها

اجتماع
\ مجموعه مکمل
اشتراک
Δ تفاضل متقارن

ترتیب کلی

min کمینه
max بیشینه

توری‌ها

کرانه تحتانی
کرانه فوقانی

مجموعه‌ها

× ضرب دکارتی
اجتماع منفصل
^ توان مجموعه‌ای

گروه‌ها

حاصل‌جمع مستقیم
حاصل ضرب آزاد
produit en couronne

مدول‌ها

ضرب تانسوری
Hom هومومورفیزم
Tor پیچش
Ext extensions

درخت‌ها

enracinement

واریته‌های متصل

# جمع متصل

فضاهای نقطه‌دار

bouquet
smash produit
joint

برداری
(.) ضرب اسکالر
ضرب برداری
جبری
[,] کروشه لی
{,} کروشه پواسون
ضرب خارجی
هومولوژی
cup-produit
حاصل ضرب اشتراک
ترتیبی
+ الحاق
منطق بولی
عطف منطقی فصل منطقی یای انحصاری استلزام منطقی اگر و فقط اگر