مجموعه منتظم

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

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

۱. پایه:

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

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

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

حکم:

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

برهان:

• با توجه به قسمت پایهٔ تعریف: ${\displaystyle \{a\}\!}$ و ${\displaystyle \{b\}\!}$ منتظم است
• با استفاده از عمل اتحاد مجموعه‌ها: ${\displaystyle \{a\}\cup \{b\}=\{a,b\}\!}$ منتظم است
• با استفاده از عمل ستاره کلین: ${\displaystyle \{a,b\}^{*}\!}$ منتظم است
• با استفاده از عمل الحاق: ${\displaystyle \{b\}\{b\}=\{bb\}\!}$ منتظم است
• و سرانجام، با اعمال دو الحاق دیگر حکم به اثبات می‌رسد.[7]

مقالهٔ اصلی: زبان‌های منتظم

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