حل تمرین نظریه محاسبات/فصل اول/حل تمرین1-28
حل تمرین 1-28
تمرین
ویرایشالفبای {[ 0 1] [ 1 0] [ 1 1] [ 0 0]}=2 ∑ را در نظر بگیرید.فرض کنید هر سطر رشته ای از صفر و یک بوده و زبان E به صورت زیر باشد:
{سطر پایین w معکوس سطر بالایی w است | *2∑ € E = {w
نشان دهید که E منظم نیست.
حل
ویرایشدر صورتی که در صورت سوال منظور از معکوس بودن سطر بالا و پایین همان not بودن باشد در اینصورت به علت یافتن 1 عبارت منظم این زبان منظم است.
زیرا برای not شدن فقط دو علامت زیر باید وجود داشته باشد بنابراین:
- E = ([1 0] + [0 1])
اما اگر منظور از معکوس بودن آیینه بودن سطر بالا و پایین باشد، در این صورت از تمام الفبای بالا میتوان استفاده کرد.
در صورتی که از لم تزریق استفاده شود طبق تعریف اگر Y را در عبارت XYZ حذف و یا به میزان دلخواه افزایش دهیم نباید زبان از حالت منظم بودن خارج شود اما در اینجا در صورتی که Y را حذف کنیم، آنگاه زبان دیگر منظم نخواهد بود زیر به عنوان مثال ممکن است یک صفر از سطر بالا حذف شده اما در سطر پایین همچنان موجود و نیز یک 1 از سطر پایین حذف میشود که در سطر بالا همچنان موجودمی باشد، پس دیگر از حالت آیینه بودن یا همان معکوس بودن خارج میشود.
قابل ذکر است که در لم تزریق از برهان خلف استفاده میشود و ما در اینجا با فرض منظم بودن آغاز کردیم ولی خلاف آن اثبات شد.