حل تمرین نظریه محاسبات/فصل اول/حل تمرین1-39

حل تمرین 1-39

تمرین

ساختار بیان شده در قضیه 28-1 بیان می کند که هر GNFA معادل یک GNFA با دو حالت می باشد. می توان نشان داد که این مساله در مورد DFA صادق نیست. ثابت کنید که برای هر 1>K زبان *{0,1}Ak وجود دارد که با یک DFA با K حالت تشخیص داده شده ولی امکان تشخیص آن با 1-K حالت وجود ندارد.

حل

برای نمونه، سیگما را برابر {a} در نظر گرفته که در نتیجه داریم:

{Lk = {a^i | i >= k−1

که شامل کلمات دارای طول بزرگتر یا مساوی k-1 می باشد.

در اینجا k کلمه غیر برابر وجود دارد(که همان a^iها هستند به ازای 0=<K>i) در حالی که اگر i!=j باشد، (a^ia^(k−1−i عضو L می باشد در حالی که (a^ja^(k−1−i عضو L نیست.

در نتیجه هیچ DFAای با k-1 حالت یا کمتر از آن قابلیت تشخیص LK را ندارد.