مجموعه منتظم

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

 کاربردها 
مجموعه‌های منتظم (پدیدآمده برطبق تعریف زیر) خانواده‌ای از زبان‌های نسبتاً ساده را در بر می‌گیرد. این‌گونه زبان‌ها نقش‌های پراهمیتی را در شاخه‌های مختلف علوم نظری کامپیوتر هم‌چون زبان‌های صوری، تشخیص الگوهاPattern recognition و تئوری ماشین‌های حالات متناهیTheory of finite-state machines بر عهده می‌گیرد.An Introduction to the Theory of Computer Science, p. ۴۹

 تعریف 
الفبای  را در نظر می‌گیریم. مجموعه‌های منتظمRegular sets بر روی  را از طریق بازگشتی به صورت زیر تعریف می‌نمائیم:

۱. پایه:

 ، و ، به ازاء هر  مجموعه‌های منتظم بر روی  هستند.

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

مجموعه‌های منتظم  و  را بر روی  در نظر می‌گیریم. آنگاه، مجموعه‌های زیر هم منتظم بر روی  است.

 مثال‌ها 
حکم:

مجموعهٔ  مجموعه‌ای است منتظم بر روی الفبای .

برهان:
 با توجه به قسمت پایهٔ تعریف:  و  منتظم است
 با استفاده از عمل اتحاد مجموعه‌ها:  منتظم است
 با استفاده از عمل ستاره کلین:  منتظم است
 با استفاده از عمل الحاق:  منتظم است
 و سرانجام، با اعمال دو الحاق دیگر حکم به اثبات می‌رسد.An Introduction to the Theory of Computer Science, pp. 49 - 50

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

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

 پانوشته‌ها 

 منابع 

 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 

رده:کنش‌های گروهی (ریاضیات)
رده:گروه‌های توپولوژیکی
رده:نظریه محاسبات