حل تمرین نظریه محاسبات-ویرایش دوم/فصل اول/حل تمرین۱-۵۴
نشان دهید F نا منظم است .F={aibjck| I,j,k>=0and if i=1then j=k}
الف) فرض می کنیم F منظم باشد . فرض می کنیم P طول تزریق بدست امده توسط لم تزریق باشد . رشته S را به صورت a1bpcp انتخاب می کنیم . چون S عضو F بوده و طول S بزرگتر از P باشد پس طبق لم تزریق باید به سه جزs=xyz تقسیم شود و برای هر i>=0 باید xyiz عضو F باشد . سه مورد مختلف را مورد بررسی قرار می دهیم و نشان ی دهیم که این کار غیر ممکن است. 1- اگر رشته y فقط شامل صفر باشد . در این مورد xyyz دارای تعداد صفر بیش از تعداد یک خواهد بود ونمی تواند عضو F باشد، پس شرط اول لم تزریق نقض می شود . پس به تناقض می رسیم. 2- اگر رشته Y فقط شامل یک باشد ؛ این مورد نیز به تناقض میرسد. 3- اگر رشته Y شامل 0،1 هردو باشد .در این مورد xyyz دارای تعداد مساوی از صفر و یک می باشد ولی بعضی از یک ها قبل از صفر ظاهر می شوند.پس xyyz عضو F نبوده و به تناقض می رسیم. پس اگر فرض کنیم که F منظم است ؛ حتما به تناقض می رسیم ؛بنا براین F نامنظم است. چون می تواند تعداد نا متناهی وبرابری از J,K وجود داشته باشد و اتوماتای ما محدود است بنابراین نمی توانیم یک اتوماتای منظم برای F رسم کرد.
S=a1bpcp
این تناقض استa1bp-kcp
ب) در حالت اول شرط i=1 را در نظر می گیریم . که L1 می گیریم.در این حالت F نامنظم است. اگر شر ط i را در نظر نگیریم F زبان منظم است که L2 در نظر می گیریم بنابر این برای اثبات از اشتراک دو حالت استفاده می کنیم.
L1∩L3=L2
در این حالت نشان می دهد که L3 نیز نا منظم است.
حل بالا غلط است . در مورد قسمت الف میتوان نشان داد که این زبان ترکیب a و bncn است که میدانیم منظم نیست . ( به وسیله pumping lemma ) پس این زبان هم منظم نیست . در مورد قسمت ب این زبان در pumping lemma صدق میکند . ( مثلا p = 3 ) در مورد قسمت c باید گفت که اگر pumping lemma در مورد زبانی صدق نکند آنگاه میتوان گفت که آن زبان منظم نیست . اما اگر pumping lemma در مورد زبانی صدق کند در مورد منظم بودن یا نبودن آن نمیتوان اظهار نظر کرد . پس قسمت های ب و c pumping lemma را نقض نمیکنند .