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

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

الف) {A1={0n1n2n|n≥0


ب) {*{A2= {w w w | w ∈ {a,b


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




حل:

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


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


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

|y|<2p

بنابراین

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

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

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

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





آرش سرابی