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

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

)

تمرین

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

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

نشان دهید که اگر A منظم باشد، A_$1/3-1/3$الزاما منظم نیست.

حل

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

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