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

1 – 39. ساختار بیان شده در قضیه 1.54 بیان می کند که هر GNFA معادل یک GNFA با دو حالت می باشد. می توان نشان داد که این مسأله در مورد DFA صادق نیست. ثابت کنید که برای هر k > 1 زبان *{Ak ⊆ {0,1 وجود دارد که با یک DFA با k حالت تشخیص داده شده ولی امکان تشخیص آن با k-1 حالت وجود ندارد.

پاسخ: در هر DFA در حالت های معمولی در هر انتقال فقط یک نماد می تواند اضافه شود.مثلا اگر بتوان از حالت A1 با نماد 1 به حالت A2 و از حالت A2 با نماد 0 به حالت A3 منقل شد، این را نمی توان به این صورت نشان داد که با حذف حالت A2 از حالت A1 با 10 به حالت A3 منتقل شد. حذف حالت های شروع و پایان و تله هم باعث می شود که اصلا زبان مورد نظر ناقص شود؛ و امکان حذف آن ها وجود ندارد. همچنین در DFA انتقال تهی وجود ندارد و از آن نمی توان استفاده کرد.
به عنوان مثال نقض، اگر زبان Ak را به این صورت تعریف کنیم که رشته های شامل 0 و1 ، دقیقا شامل k تا صفر باشند، باید برای هر ورودی 0، یک حالت داشته باشیم و بنابر این باید k حالت داشته باشیم. و با حذف یکی از حالات میانی (و نه شروع و پایان؛ چون در این صورت به طور کلی زبان ناقص می شود) زبان مورد نظر به زبانی تبدیل می شود که دقیقا k-1 صفر دارد، و این غلط است.