عبارت منظم

منظور از یک کلمه، یک دنباله‌ی متناهی از نویسه‌های $a$ و $b$ و $c$ است. همچنین یک دنباله به طول صفر را نیز به عنوان یک کلمه در نظر می‌گیریم و با $e$ نمایش می‌دهیم. برای مثال مجموعه کلمه‌های به طول یک، $\{a,b,c\}$ است.

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

۱) $e$ یک عبارت منظم است که مجموعه‌ی $\{e\}$ را مشخص می‌کند.

۲) $a$‌ و $b$‌ و $c$ هر کدام یک عبارت منظم هستند که به ترتیب مجموعه‌های $\{a\}$، $\{b\}$ و $\{c\}$‌را مشخص می‌کنند.

۳) اگر $R$‌یک عبارت منظم باشد که مجموعه‌ی $S$‌ را مشخص می‌کند، آن‌گاه:

• $(R)$ نیز یک عبارت منظم است که مجموعه‌ی $S$ را مشخص می‌کند.
• $R$ نیز یک عبارت منظم است که مجموعه‌ی $\{w_1w_2...w_k|w_i \in S,\forall k \geq 0\}$ را مشخص می‌کند. توجه کنید که در تعریف فوق، $k$ می‌تواند صفر باشد، بنابراین همواره $e \in R$.

۴) اگر $R_1$ و $R_2$ دو عبارت منظم باشند که به ترتیب مجموعه‌های $S_1$ و $S_2$ را مشخص می‌کنند آن‌گاه:

• $R_1+R_2$ یک عبارت منظم است که مجموعه‌ی $S_1 \cup S_2$ را مشخص می‌کند.
• $R_1R_2$ یک عبارت منظم است که مجموعه‌ی $\{w_1w_2|w_1\in S_1,w_2 \in S_2\}$ رامشخص می‌کند.

برای مثال، عبارت منظم $(a*bc)$ مجموعه‌ی$\{bc,abc,aabc,...\}$ را مشخص می‌کند.

مجموعه‌ی $V$ از کلمه‌ها را مجموعه‌ای در نظر بگیرید که جمع تعداد $a$ ها و تعداد $b$ ها و دو برابر تعداد $c$‌ ها در آن بر ۳ بخش‌پذیر باشد.

عبارت منظمی بنویسید که مجموعه‌ی $V$ را مشخص کند.

• سوال بعد
• سوال قبل