حل تمرین نظریه محاسبات-ویرایش دوم/فصل اول/حل تمرین۱-۳۳

سوال :

فرض کنید الفبای 2$\sum$ به صورت {${\begin{bmatrix}0\\0\end{bmatrix}},{\begin{bmatrix}0\\1\end{bmatrix}},{\begin{bmatrix}1\\1\end{bmatrix}},{\begin{bmatrix}1\\0\end{bmatrix}}$} = 2$\sum$ باشد. در این جا 2$\sum$ شامل تمام ستون های شامل صفر ویک با ارتفاع 2 می باشد. یک رشته روی الفبای 2$\sum$ دو ردیف از صفرها و یک ها دارد. فرض کنید هر ردیف یک عدد باینری بوده و زبان C به صورت زیر باشد :
{ردیف پایین در W ، سه برابر ردیف بالا می باشد. | $\sum _{2}^{*}$C={wє
به طور مثال ${\begin{bmatrix}0\\0\end{bmatrix}},{\begin{bmatrix}1\\0\end{bmatrix}},{\begin{bmatrix}0\\1\end{bmatrix}},{\begin{bmatrix}1\\1\end{bmatrix}}$ عضو C بوده ولی ${\begin{bmatrix}0\\1\end{bmatrix}},{\begin{bmatrix}1\\0\end{bmatrix}},{\begin{bmatrix}0\\1\end{bmatrix}}$ عضو C نیست. نشان دهید C منظم است.

جواب :

DFA شکل زیر زبان $C^{r}$ را می پذیرد.

با توجه به نتیجه ی سوال 1-31 زبان C منظم می باشد.