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

حل تمرین1-40* (سوال ستاره دار)

تمرین

اگر A مجموعه اعداد طبیعی بوده وK یک عدد طبیعی بزرگتر از یک باشد، مجموعه(Bk(A را به صورت زیر درنظر بگیرید

{نمایش یک عدد از مجموعهA در پایه K می‌باشد. |Bk(A)={w

در نمایش اعداد اجازه نداریم که در سمت چپ اعداد صفر داشته باشیم . بطورمثال

B2({3,5}) = {11,101}

و

B3({3,5}) = {10,12}

یک مجموعه A مثال بزنید که برای آن مجموعه (B2(A منظم و (B3(A نامنظم باشد.

ثابت کنید که مثالی که می‌آورید صحیح است.

حل

مجموعه A را به صورت روبه رو تعریف می کنیم:{1-A={ 2^n

مجموعه (B2(A را مثال میزنیم : 1 و 3و 7و15 و31 و 63و.. که اگر این اعداد به مبنای 2 برده شوند ، چون میتوان برای آنها یک عبارت منظم به فرم *11 نوشت پس مثال بیان شده برای (B2(A منظم است.

مجموعه (B3(A به صورت مقابل میشود : ۱ و ۱۰ و ۲۱ و ۱۲۰ و ۱۰۱۱ و ۲۱۰۰ و .. باید نشان دهیم نامنظم است. فرض میکنیم (B3(A منظم باشد ، طبق ویژگی لم تزریق رشته ای مانند S داریم که عضو این زبان است .طول تزریق را به طور مثال p میگیریم .طبق ویژگی لم تزریق تمام رشته‌های موجود در یک زبان، اگر دارای طول بزرگتر از طول تزریق باشند را می‌توان تزریق کرد. یعنی آن رشته شامل قسمتی است که آن قسمت از رشته را می‌توان هر تعداد بارتکرار کرد و رشته هایی که تولید میشوند عضو زبان خواهند بود.

در این مثال kای وجود دارد که اگررشته وسط y باشدو آنرا ا k بار تکرار کنیم دیگر رشته حاصل عضو این زبان نیست.پس این مثال منظم نیست.