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

تمرین۱-۳۰

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

---

حل:

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

x=0^r , 0≤r<p

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

z=0^t1^p , r+q+t=p

بنابراین

1-

∀ i ≥ 0 : xyⁱz = 0^r(0^q)ⁱ0^t1^p = 0^r+iq+t1^p ∈ L(0*1*)

2-

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

3-

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

تناقضی که در مثال 1-73 وجود دارد برای زبان {aⁿbⁿ | n ∈ N₀}. است ولی در اینجا زبان ما {aⁿb^m | n,m ∈ N₀} خواهد یود.

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