فرض کنید $L_1, L_2$ دو زبان منظم با الفبای $\Sigma = \{0, 1\}$ باشند.

آ) زبان $L = L_1 \oplus L_2$ به این شکل ساخته می‌شود که به ازای هر دو رشته‌ی هم‌طول $s_1 \in L_1, s_2 \in L_2$، رشته‌ی $s_1 \oplus s_2$ در $L$ می‌آید. نشان دهید $L$ منظم است.

ب) زبان $L = L_1 + L_2$ به این شکل ساخته می‌شود که به ازای هر دو رشته‌ی هم‌طول $s_1 \in L_1, s_2 \in L_2$، رشته‌ی $s_1+s_2$ (جمع دودویی دو رشته) در $L$ می‌آید. توجه کنید اگر سمت چپ رشته‌های $s_1$ و $s_2$ رقم ۰ وجود داشته باشد و جمع آن‌ها نیز چنین باشد، رقم‌های صفر سمت چپ را نمی‌اندازیم؛ امّا نمی‌توانیم به طور دل‌خواه صفر به سمت چپ رشته اضافه کنیم. بنابراین طول $s_1+s_2$ یا با طول $s_1, s_2$ برابر است یا یکی بیش‌تر است. نشان دهید $L$ منظم است.

• سوال قبل