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

سوال :

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

جواب :

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

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