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

ویکی‎کتاب، کتابخانهٔ آزاد
پرش به ناوبری پرش به جستجو

حل تمرین۱-۴۳ ( این مسئله در کلاس توضیح داده شده است . می توانید پس از مطالعه از لینک زیر حل آن را به صورت فارسی و با توضیحات اضافه تر( یعنی i و j و دلیل ارتباط آنها ) که معلوم کند حل را به طور کامل متوجه شده اید در این سایت بنوسیسد . متشکرم . http://www.cs.rice.edu/~nakhleh/COMP481/hw4.pdf http://www.cs.rice.edu/~nakhleh/COMP481/sol4.pdf

)

تمرین[ویرایش]

اگر A یک زبان باشد، A مجموعه رشته هایی از A می باشد که یک سوم میانی آنها حذف شده باشد و به صورت زیر تعریف می شود:

A={xz|xyz Є A , |x|=|y|=|z| موجود باشد بطوریکه yرشته}


نشان دهید که اگر A منظم باشد، Aالزاما منظم نیست.

حل[ویرایش]

این سوال ستاره دار بوده و حل آن دشوار می باشد. با جستجو در اینترنت به جواب زیر می رسید:

Sipser-1.43.GIF

http://www.cs.rice.edu/~nakhleh/COMP481/sol4.pdf