حل تمرین نظریه محاسبات/فصل اول/حل تمرین1-17

حل تمرین ۱-۱۷

تمرین

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

الف)

{A1 = {0 n 1n 2n | n>=0

ب )

{*{F= {w w | w € {a,b

حل

ب)

فرض میکنیم که Fمنظم باشد فرض میکنیم P طول تزریق داده شده توسط لم تزریق باشد. رشته S را بصورت A^P B A^Bدر نظر میگیریم .

چونSعضوFبوده وPطول آن بزرگتر از Pمی باشد پس لم تزریق تضمین می کند کهSقابل تقسیم برS=XYZ بوده و سه شرط لم تزریق برقرار می باشد نشان می دهیم که این کار غیر ممکن می باشد

در اینجا شرط سوم به کار می رود چون در غیر این صورت می توانXوZرا تهی فرض کرده وSرا تزریق کرد شرط سوم الزام می کند که Y فقط شامل صفر باشد پس XYYZ عضوF نخواهد بود

مشاهده می‌شود که برای نشان دادن منظم نبودنFاز رشته A^P B A^B استفاده می کنیم که کاملا نا منظم نبودنFرا نشان دهد ولی رشته‌ای مانند A^P B^P نمی‌تواند نا منظم بودن F را نشان دهد اگر چه A^P B^P عضو F بوده ولی نمی‌تواند در هنگام تزریق به تناقض برسد

حل ۱۷-۱ پ)

فرض می کنیم که A3 یک زبان منظم است. سپس به وسیله لم تزریق اثبات می کنیم که دارای طول p می باشد.
رشته زیر را ملاحظه کنید:

s = a2p
تا زمانی که 2p از p بزرگتر باشد برای هر p>=0 ، لم تزریق می گوید که s می تواند به صورت xyz برای بعضی از رشته های x, y, z با طول length(xy)<=p و length(y)>0 نوشته شود. ما ادعا می کنیم که رشته xyyz در زبان A3 قرار ندارد در نتیجه با لم تزریق به تناقض می رسیم پس A3 یک زبان منظم است.
برای اینکه ببینیم xyyz درون زبان A3 نیست، مشاهده می کنید که کوچکترین رشته در A3 که بزرگتر از s هست دارای طول 2p+1 است که با طول s متفاوت است و 2p طول این رشته است. به عبارت دیگر ما داریم :
length(xyyz) - length(s) = p < 2p
این نشان می دهد که طول xyyz توانی از 2 نیست و xyyz بنابراین درون زبان A3 نیست.