منظور از یک کلمه، یک دنبالهی متناهی از نویسههای a و b و c است. همچنین یک دنباله به طول صفر را نیز به عنوان یک کلمه در نظر میگیریم و با e نمایش میدهیم. برای مثال مجموعه کلمههای به طول یک، {a,b,c} است.
یک عبارت منظم، عبارتی استکه یک مجموعه از کلمهها را مشخص میکند و به این صورت تعریف میشود:
۱) e یک عبارت منظم است که مجموعهی {e} را مشخص میکند.
۲) a و b و c هر کدام یک عبارت منظم هستند که به ترتیب مجموعههای {a}، {b} و {c}را مشخص میکنند.
۳) اگر Rیک عبارت منظم باشد که مجموعهی S را مشخص میکند، آنگاه:
۴) اگر R1 و R2 دو عبارت منظم باشند که به ترتیب مجموعههای S1 و S2 را مشخص میکنند آنگاه:
برای مثال، عبارت منظم (a∗bc) مجموعهی{bc,abc,aabc,...} را مشخص میکند.
مجموعهی V از کلمهها را مجموعهای در نظر بگیرید که جمع تعداد a ها و تعداد b ها و دو برابر تعداد c ها در آن بر ۳ بخشپذیر باشد.
عبارت منظمی بنویسید که مجموعهی V را مشخص کند.