مجموعه منتظم

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

الفبای ${\displaystyle \Sigma \!}$

۱. پایه:

${\displaystyle \emptyset \!}$

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

مجموعه‌های منتظم ${\displaystyle X\!}$

حکم:

مجموعهٔ ${\displaystyle A=\{a,b\}^{*}\{bb\}\{a,b\}^{*}\!}$

برهان:

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

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

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