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

تمرین۱-۳۰

خطایی را که در اثبات زیر برای نشان دادن اینکه زبان *1*0 منظم نیست وجود دارد را مشخص کنید.(بدیهی است که حتما خطایی وجود دارد چون *1*0 منظم است) اثبات با برهان خلف است.فرض می کنیم *1*0 منظم است،پس بر اساس لم تزریق عددی مثل p برای تزریق زبان *1*0 وجود دارد.رشته ی s را به صورت 0p1p انتخاب میکنیم ولی در مثال 1-73 نشام دادیم که رشته ی s قابلیت تزریق ندارد.پس به تناقض می رسیم.پس این زبان منظم نیست.



حل:

هیچ گونه تناقضی وجود ندارد و رشته s=0p1p می تواند تزریق شود.s را یه این صورت تقسیم میکنیم:


x=0r , 0≤r<p

y=0q , q>0,r+q<=p

z=0t1p , r+q+t=p

بنابراین

1-

∀ i ≥ 0 : xyiz = 0r(0q)i0t1p = 0r+iq+t1p ∈ L(0*1*)

2-

|y| = |0q| = q > 0

3-

|xy| = |0r+q| = r + q ≤p

تناقضی که در مثال 1-73 وجود دارد برای زبان {anbn | n ∈ N0}. است ولی در اینجا زبان ما {anbm | n,m ∈ N0} خواهد یود.






آرش سرابی ‏۱۶ آوریل ۲۰۱۰، ساعت ۱۷:۵۹ (UTC)