مجموعه منتظم

در تئوری محاسبات، مجموعه‌های منتظم (Regular sets) به مجموعه‌هایی از رشته‌ها^[۱] گفته می‌شود که که ایجاد آن‌ها الگوی^[۲] مشخصی را دنبال می‌کند.

کاربردها

مجموعه‌های منتظم (پدیدآمده برطبق تعریف زیر) خانواده‌ای از زبان‌های نسبتاً ساده را در بر می‌گیرد. این‌گونه زبان‌ها نقش‌های پراهمیتی را در شاخه‌های مختلف علوم نظری کامپیوتر هم‌چون زبان‌های صوری، تشخیص الگوها^[۳] و تئوری ماشین‌های حالات متناهی^[۴] بر عهده می‌گیرد.^[۵]

الفبای $\Sigma \!$ را در نظر می‌گیریم. مجموعه‌های منتظم^[۶] بر روی $\Sigma \!$ را از طریق بازگشتی به صورت زیر تعریف می‌نمائیم:

۱. پایه:

$\emptyset \!$ ، $\{\lambda \}\!$ و $\{a\}\!$ ، به ازاء هر $a\in \Sigma \!$ مجموعه‌های منتظم بر روی $\Sigma \!$ هستند.

۲. گام بازگشتی:

مجموعه‌های منتظم $X\!$ و $Y\!$ را بر روی $\Sigma \!$ در نظر می‌گیریم. آنگاه، مجموعه‌های زیر هم منتظم بر روی $\Sigma \!$ است.

$X\cup Y\!$

$XY\!$

$X^{*}\!$

حکم:

مجموعهٔ $A=\{a,b\}^{*}\{bb\}\{a,b\}^{*}\!$ مجموعه‌ای است منتظم بر روی الفبای $\Sigma =\{a,b\}\!$ .

برهان:

زبان‌هایی را منتظم می‌نامیم، که به‌وسیلهٔ مجموعه‌های منتظم تعریف شده‌اند.

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 [۱]