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

سوال :

فرض کنید الفبای 2 به صورت {} = 2 باشد. در این جا 2 شامل تمام ستون های شامل صفر ویک با ارتفاع 2 می باشد. یک رشته روی الفبای 2 دو ردیف از صفرها و یک ها دارد. فرض کنید هر ردیف یک عدد باینری بوده و زبان C به صورت زیر باشد :
{ردیف پایین در W ، سه برابر ردیف بالا می باشد. | C={wє
به طور مثال عضو C بوده ولی عضو C نیست. نشان دهید C منظم است.

جواب :

DFA شکل زیر زبان را می پذیرد.


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