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

تمرین : با استفاده از لم تزریق نشان دهید که زبان های زیر منظم نیستند.

الف) {A₁={0ⁿ1ⁿ2ⁿ|n≥0

ب) {*{A₂= {w w w | w ∈ {a,b

ج) {A₃ = { a²ⁿ | n≥0 در اینجا a²ⁿ یعنی رشته ای از a به طول 2ⁿ می باشد.

---

حل:

الف)فرض میکنیم زبان A₁ منظم است. رشته ی s ما به صورت 0^p 1^p 2^p باشد چون s عضوی از A₁ است و s بزرگتر از p است پس بر طبق لم تزریق s میتواند به سه بخش تقسیم گردد،s = xyz که برای هر i≥0 رشته ی xyⁱz در A₁ است در صورت دارا بودن این دو شرط: 1-رشته ی y شامل 0 ها یا 1 ها یا 2 ها خواهد بود،در این صورت رشته ی xyyz تعداد مساوی از 0 ها یا 1 ها یا 2 ها نخواهد داشت.از این رو xyyz عضوی از A₁ نخواهد بود.-> یک تناقض 2-رشته ی y شامل بیش از یک نوع از نماد ها خواهد بود در این صورت xyyz تعداد 0ها و 1ها ویا 2های بیش از حد مجازی خواهد داشت بنابراین xyyz عضو A₁ نخواهد بود.با توجه به این تناقضات پیش آمده فرض ما باطل خواهد بود و این زبان منظم نخواهد بود.

ب) فرض میکنیم که زبان A₂ منظم باشد فرض میکنیم P طول تزریق داده شده توسط لم تزریق باشد. رشته ی S را بصورت a^p b a^bدر نظر میگیریم. چونSعضوA₂بوده وطول آن بزرگتر از Pمی باشد پس لم تزریق تضمین می کند کهSقابل تقسیم برS=xyz بوده و سه شرط لم تزریق برقرار می باشد نشان می دهیم که این کار غیر ممکن می باشد. در اینجا شرط سوم به کار می رود چون در غیر این صورت می توانxوz را تهی فرض کرده وSرا تزریق کرد شرط سوم الزام می کند کهy فقط شامل صفر باشد پس xyyz عضوA₂ نخواهد بود مشاهده می شود که برای نشان دادن منظم نبودنA₂ از رشته a^p b a^b استفاده می کنیم که کاملا نا منظم نبودنA₂ را نشان دهدولی رشته ای مانند a^p b^p نمی تواند نا منظم بودنA₂ را نشان دهد اگر چهa^p b^p عضو A₂ بوده ولی نمی تواند در هنگام تزریق به تناقض برسد

ج)فرض می کنیم زبان A₃ منظم است،s را رشته ی a^2p در نظر می گیریم.چون s عضو A₃ است و s بزگتر از p است پس لم تزریق تضمین می کند که s میتواند به سه بخش تقسیم گردد.شرط سوم به ما می گوید که xy|≤p| بعلاوه،P<2^p پس

|y|<2^p

بنابراین

|xyz|=|xyz|+|y|<2^p+2^p=2^P+1

شرط سوم نیازمند این است که

|y|>1 => 2^p<|xyz|<2^p+1

و طول xyyz نمیتواند توانی از 2 باشد پس xyyz عضوی از A₃ نخواهد بود=> A₃ منظم نیست.

آرش سرابی