دسته‌بندی زیانهای صوری و آتاماتا

صفحه 1:
دسته بندی زب صورى بو آتاماتا 

صفحه 2:
فرض کنید 9 یک مجموعه نامتناهی شمارا باشد . مجموعه توانی آن *2 ناشمارا است . ‎a‏ اثبات : فرض کنید 2۵( . وکیوگ,رگ...) باشد . آنگاه هر عضو ازگ2 می توان به صورت رشته هایی از 0) و ) نمایش داد. موقعیت ‏ ۰ ؛ است اگر و فقط اگر زک در و باشد. برای مثال مجموعه (ع5رو5,وع] به صورت ...و 0000و 5 ,وکروع] به صورت 100000)... نمایش داده می شود .روشن است که هر عضویّراز را می تولن به صورت چنین رشته ای نمایش داد و هریک از اين رشته ها یک عضو منحصر بفرد از 25 را نمایش می دهد . 

صفحه 3:
ادامه 5 فرض كنيد كه 5 شمارا باشد آنوقت عناصر آن باد به ترتیبی مانند 562 باشد و همانند آنچه در شکل 0-10 نشان داده شده است می توانستیم آنها را در یک جدول وارد کنیم . در اين جدول از عناصری که در قطر اصلی قرار دارند متمم گیری کنید یعنی اینکه (ها را به ) و 4ها را به 0) تبدیل کنید. درشکل 0-00 عنصر ...000000 را داریم در نتیجه تبدیل به ...0000)می شود دنباله جدید» ‎MLE GPE pete‏ نمایش میدهد. ولی نمی تواند 4* باشد چون در عضو بودن عنصرو5 با هم تفاوت دارند به همین دلیل نمی تواند ‎athe Se fay tot‏ بنابراین چاره ای نیست جز لینکه*2 ناشمارا باشد . 

صفحه 4:
به ازای هر غیر تهی زیانهایی هستند که بر شمارش بازگشتی نیستند . تا اثبات : یک زیان زیر مجموعه ای از 2 است و هر زیر مجموعه یک زیان استا: بنابراین مجموعه تمام زبان ها دقی! "22 است ,چون .2 نامتناهی است قضیه 40-4 به ما می گوید که مجموعه تمامی زبانهای روی ۶ ناشمارا است . اما مجموعه تمامی ماشین های تورینگ برشمارشی هستند . بنابراين مجموعه تمامی زبانهای برشمارش بازگشتی شماراست . بواسطه تمرین 16 در انتهای بخش می توان كفت که باید زبانهایی بر روی ۶ باشند که برشمارش بازگشتی نیستند . 

صفحه 5:
قضيه ©-00. زبان برشمارش بازكشتى وجود دارد كه متمم برشمارش بازكشتى نيست . | اثبات : فرض کنید که [م)-2 باشد . حال مجموعه تمامى ماشين هاى تورينك بر روى اين الفباى ورودى را در نظر بكيريد . براساس قضيه 00-6 اين مجموعه شمارا است و بنابراین می توان ترتئیب .2 را برای عناصر آن در نظر گرفت . برای هر ماشین تورینگ 7/۶ زبان برشمارش بازگشتی مانند 14 ) را داریم . برعکس برای هر زبان برشمارش بازگشتی بر روی ۶ یک ماشین تورینگ هست که آنرا مى پذیرد . 

صفحه 6:
"" ادامه حال ربان جدیدی مانند را را به صورت زير در نظر می گیریم به ازای 4 < ‎١‏ رشته *ه در را است اگر وفقط اگر ( :16 ) را >*0 باشد بنابراین زبان را خوش تعریف است چون ):/1) را *۵ و در نتيحه را ©© بايد يا صحيح یا غلط باشد بعد متمم را را در نظر می گیریم . T= {asa gL} aad كه آن هم خوش تعریف هست اما نشان خواهیم داد که برشمارش بازگشتی نیست . اين را با برهان خلف نشان می دهیم . با فرض ‎Las‏ برشمارش بازگشتی است شروع می کنیم اگر چنین باشد باید ماشین تورینگی مانند :16 باشد که 940 لباب 

صفحه 7:
‎eb 0‏ تاره روف ‎Le as,‏ نظر بگیرید آیا در را است یا در ؟ فرض کنید که ۴۳ ** باشد . با استفاده از -) نتیجه می گیریم که ‎a* € L(M,)‏ ‏اما با استفاده از 00-0 نقیحه می گيريم _ ‎ak ely‏ حال اگر فرض کنیم که *۵ در را هست آنوقت بط © “© و از ©-00 نتيجه مى كيريم ‏214 و ‏اما باز از 00-0 نتيجه می گیریم که مآع *ه ‎ 

صفحه 8:
بازگشتی است غلط است برای تکمیل اثبات باید نشان دهیم که را برشمارش بازگشتی است برای این منظور می توانیم از روال برشمردن شناخته شده برای ماش استفاده کنیم . اگر*ه را داشته باشیم ابتدا , را با شمارش تعداد ب ها بيدا مى كنيم . ن های تورینگ سپس با استفاده از روال برشمردن برای ماشین تورینگ:/1 را پیدا می کنیم .نهایتا توصیف آنرا همراه باه به ماشین تورینگ جامع :1 که اعمال 0 را روی *# شبیه سازی می کند می دهیم . اگر *۵ در را باشد محاسبات ۸4 نهایتاپایان می يابد با تركيب كردن اين ماشين تورينكى بوجود مى ايد كه هرا © را مى يذير: ادر نتيجه با استفاده از تعریف 00-0 برشمارش بازگشتی می باشد . 

صفحه 9:
قضیه 404. اگر زبان راو متعم آن 7 هر دو برشمارش بازگشتی باشند آنگاه هر دو زبان بازگشتی هستند اگر رابازگشتی باشد آنوقت 7 هم بازگشتی است و نتیجتاهر دو برشمارش بازگشتی هستند . 2 اثبات : اگر راو هر دو برشمارش بازگشتی باشند آنوقت ماشین های تورینگ () و 26 به ترتيب به عنوان روال های برشمردن راو 7 وجود دارند . اولی ... ۱::۱۷۶ 6 را در تولید می کند حال فرض می کنیم 7 ما داده شده است ابتدا اجازه می دهیم که () رشته ۱۳۶ را تولید کرده و آن را با مر را در راو دومی .. مقايسه کند 

صفحه 10:
"" ادامه اگر یکی نبودند اجازه می دهیم که ۷ توبسط ۸40 تولید شود و مجددا مقایسه را انجام می دهیم اگر نیاز به ادامه باشد اجازه مى دهیم ‎(AS‏ رشته ۶" و رشتية” را تولید کند و به همین نحو دامه می دهیم . هر 2 6« توسط 0 و یا 1 تولید می شود بنابراین در نهایت تطبیقی خواهیم داشت . اگر رشته مذک.ر توسط () تولید شود و ررربه را تعلق دارد و در غير این صورت به . اين فرايند يك الكوريتم عضويت براى هر دوى باو لست و بنابراين هر دو بازكشتى هستند . 

صفحه 11:
بالعکس فرض کنید که را بازگشتی باشد آنوقت الگوریتم عضویتی برای آن وجود دارد اما همین الگوریتم عضویتی برای ‏ می شودء اكر فقط نتيجه آن را عكس كنيم . بنابزاين 2 بازكشتى است . جون هر زبان بازگشتی » بزشمارش بازكشتى است اثبات كامل است . 

صفحه 12:
زبانی وجود دارد که برشمارش بازگشتی هست اما بازگشتی نیست به اين معنا که خانواده زبانهای بازگشتی زیرمجموعه سره ای از خانواه زبانهای برشمارش بازگشتی 1 اثبات : زبان رادر قضیه 40-0 را در نظر اين زبان برشمارش بازگشتی است لما متمم اش برشمارش بازگشتی نیست . بنابراین طبق قضیه 10-۳ بازگشتی نیست . در نتیجه مثالی که دنبالش بو به ما می دهد . 

صفحه 13:
که توسط یک گرامر نامقید تولید شود برشمارش بازگشتی است . ‎a‏ اثبات : گرامر مذکور روال برشمارشی را برای برشمردن همه رشته های زبان به طور سیستمالیک تعریف می کند . برای مثال می توانیم لیستی از همه رشته های رمر در را تهیه کنیم بطوریکه Gow 

صفحه 14:
* ادامه به معنای اينکه ررر در یک قدم بدست می آید . چون مجموعه قوانین گرامر متناهی است تعداد متناهی از این رشته ها خاهد بود سپس لیستی از همه رشته ها ی ری در را که دو قدم توليد مى شوند تهيه كنيم . 6X0 و به همین ترتیب ادامه می دهیم . این اشتقاق ها را می توانیم با یک ماشین تو شبیه سازی کنیم و درنتیجه روال برشمارش برای زبان داریم و بنابراین برشمارش بازگشتی است . 

صفحه 15:
به ازای هر زبان برشمارش بازگشتی را ۰ گرلمر نامقیدی مانند 68 وجود دارد به طوری که (0)راعرا است 3 اثبات : ساختار توضیح داده شده اطمینان می دهد که اگر مد آنكاه )سح( ‎(xe) AS‏ رمزنكارى رشته را برلساس قرار داد داده شده نشان مى دهد . با استفاده از استقراء بر روى تعداد قدم ها نشان مى دهيم كه e(qw)e(v) 

صفحه 16:
به ازای هر زبان حساس به متن را بدون 2 یک آتامای کراندار خطی مانند () هست به طوری که (0)) رارا اثبات : اكر را مستقل از متن باشد. آنوقت كرامر حساس به متن برای ,1 ) وجود دارد . نشان می دهیم که اشتقاق ها ی این گرامر می تواند بواسطه ی یک آتامای کراندار خطی سازی شود. این آتامای کراندار خطی دارای دو شیار خواهد بود یکی حاوی رشته ورودی رب و دیگری حاوی شکل های جمله ای که از ([)بدست مى ايد . 

صفحه 17:
ادامه یک نکته کلیدی در این بحث اين است که هیچ شکل جمله ای نمی تواند طولی بیش از ارماك داشته باشد. نکته دیگری که باید توجه كنيم اين است که آتامای کراندار خطی طبق تعزیف نامعین است . این نامعین بودن برای استدلال نیاز می باشد ؛ چون می توانیم ادعا کنیم قاعده درست هميشه قابل حدس زدن است مجبور به دنبال کردن قاعده جایگزین نمی باشیم . بنابراین محاسبات توضیح داده شده در قضیه 1-0 می تواند با استفاده لز فضایی که در ابتدا توسط رم اشغال شده انجام شود یعنی میتواند توسط یک آتامای کراندار خطی انجام شود . 

صفحه 18:
قضیه 40-40 هر زبان حساس به متن را بازگشتی است . 3 اثبات : ساختار در این جا مشابه با آن چیزی است که در قضیه 072) داشتیم . تمام قوانین تولید شده در قضیه 0-2 به جز 0-02 غير انقباضى هستند » o ‏بت‎ اما این قانون را می توان حذف کرد . اين قانون فقط موقعق لازم می شود که ماشین د . گرامر بدست آمده با ساختار بدون اين قانون غیرضروری, غیرانقباضی است و اثبات کامل است. تورینگ از فضای ورودی اولیه خارج شود که در اين جا مصداق ندا 

فصل 11 دسته بندی زیانهای صوری و آتاماتا قضیه ................................................................. 11-1 فرض کنید Sیک مجموعه نامتناهی شمارا باشد .مجموعه توانی آن ‏ اثبات :فرض کنید {=S } .…, ناشمارا است . باشد .آنگاه هر عضو tاز می توان به صورت رشته هایی از 0و 1نمایش داد .موقعیت i ، 1است اگر و فقط اگر در tباشد. برای مثال مجموعه به صورت ...و ،1100100و به صورت ...10101نمایش داده می شود .روشن است که هر عضوی از را می توا7ن به صورت چنین رشته ای نمایش داد و هریک از این رشته ها یک عضو منحصر بفرد از را 7نمایش می دهد .  ادامه فرض کنید که شمارا باشد آنوقت عناصر آن باد به ترتیبی مانند باشد و همانند آنچه در شکل 2-11نشان داده شده است می توانستیم آنها را در یک جدول وارد کنیم .در این جدول از عناصری که در قطر اصلی قرار دارند متمم گیری کنید یعنی اینکه 0ها را به 1و 1ها را به 0تبدیل کنید. درشکل 2-11 7عنصر 1100...را داریم در نتیجه تبدیل به 0011...می شود دنباله جدید ،عنصری از ولی نمی تواند مثال نمایش میدهد. باشد چون در عضو بودن عنصر نمی تواند ناشمارا باشد . یا هر با هم تفاوت دارند به همین دلیل دیگری باشد .بنابراین چاره ای نیست جز ا7ینکه قضیه -2 ................................................................... 11 به ازای هر∑ غیر تهی زیانهایی هستند که بر شمارش بازگشتی نیستند . ‏ اثبات :یک زیان زیر مجموعه ای از بنابراین مجموعه تمام زبان ها دقیقا است و هر زیر مجموعه یک زبان است . است .چون نامتناهی است قضیه 11-1 به ما می گوید که مجموعه تمامی زبانهای روی ∑ ناشمارا است .اما مجموعه تمامی ماشین های تورینگ برشمارشی هستند .بنابراین مجموعه تمامی زبانهای برشمارش بازگشتی شماراست .بواسطه تمرین 16در انتهای بخش می توان گفت که باید زبانهایی بر روی ∑ باشند که برشمارش بازگشتی نیستند . قضیه .................................................................. 11-3 زبان برشمارش بازگشتی وجود دارد که متمم برشمارش بازگشتی نیست . ‏ اثبات :فرض کنید که { ∑=}aباشد .حال مجموعه تمامی ماشین های تورینگ بر روی این الفبای ورودی را در نظر بگیرید . براساس قضیه 10-3این مجموعه شمارا است و بنابراین می توان ترتیب ... را برای عناصر آن در نظر گرفت . برای هر ماشین تورینگ زبان برشمارش بازگشتی مانند (L ) را داریم . برعکس برای هر زبان برشمارش بازگشتی بر روی ∑ یک ماشین تورینگ هست که آنرا می پذیرد .  ادامه حال ربان جدیدی مانند Lرا به صورت زیر در نظر می گیریم به ازای i ≤ 1رشته در Lاست اگر وفقط اگر ( است چون ) )L )L و در نتیحه L باشد بنابراین زبان Lخوش تعریف باید یا صحیح یا غلط باشد بعد متمم Lرا در نظر می گیریم . 1-11 که آن هم خوش تعریف هست اما نشان خواهیم داد که برشمارش بازگشتی نیست .این را با برهان خلف نشان می دهیم .با فرض اینکه برشمارش بازگشتی است شروع می کنیم اگر چنین باشد باید ماشین تورینگی مانند 2-11 باشد که رشته را در نظر بگیرید آیا در Lاست یا در ؟ فرض کنید که باشد .با استفاده از 11-2نتیجه می گیریم که اما با استفاده از 11-1نتیحه می گیریم حال اگر فرض کنیم که در Lهست آنوقت اما باز از 11-1نتیجه می گیریم که و از 11-2نتیجه می گیریم تناقض ،گریز ناپذیر است و باید نتیجه گیری کنیم که فرض ما که برشمارش بازگشتی است غلط است برای تکمیل اثبات باید نشان دهیم که Lبرشمارش بازگشتی است برای این منظور می توانیم از روال برشمردن شناخته شده برای ماشین های تورینگ استفاده کنیم .اگر را داشته باشیم ابتدا iرا با شمارش تعداد aها پیدا می کنیم . سپس با استفاده از روال برشمردن برای ماشین تورینگ توصیف آنرا همراه با به ماشین تورینگ جامع شبیه سازی می کند می دهیم .اگر را پیدا می کنیم .نهایتا که اعمال Mرا روی در Lباشد محاسبات نهایتا پایان می یابد با ترکیب کردن این ماشین تورینگی بوجود می اید که هرL در نتیجه با استفاده از تعریف 11-1برشمارش بازگشتی می باشد . را می پذیرد قضیه ................................................................ 11-4 هر دو برشمارش بازگشتی باشند آنگاه هر دو زبان بازگشتی اگر زبان Lو متمم آن هستند اگر Lبازگشتی باشد آنوقت هم بازگشتی است و نتیجتاهر دو برشمارش بازگشتی هستند . ‏ اثبات :اگر Lو و هر دو برشمارش بازگشتی باشند آنوقت ماشین های تورینگ M به ترتیب به عنوان روال های برشمردن Lو را در Lو دومی ,.... را در تولید می کند حال فرض می کنیم داده شده است ابتدا اجازه می دهیم که Mرشته مقایسه کند وجود دارند .اولی ... را تولید کرده و آن را با w  ادامه اگر یکی نبودند اجازه می دهیم که توسط تولید شود و مجددا مقایسه را انجام می دهیم اگر نیاز به ادامه باشد اجازه می دهیم که Mرشته و رشته را تولید کند و به همین نحو دامه می دهیم . هر توسط Mو یا تولید می شود بنابراین در نهایت تطبیقی خواهیم داشت .اگر رشته مذک.7ر توسط Mتولید شود و wبه Lتعلق دارد و در غیر این صورت به .این فرایند یک الگوریتم عضویت برای هر دوی Lو و بنابراین هر دو بازگشتی هستند . ا7ست بال7عکس فرض کنید که Lبازگشتی باشد آنوقت ال7گوریتم عضویتی برای آن وجود دارد اما همین الگوریتم عضویتی برای بنابراین می شود ،اگر فقط نتیجه آن را عکس کنیم . بازگشتی است .چون هر زبان بازگشتی ،برشمارش بازگشتی است اثبات کامل است . قضیه -5 ................................................................... 11 زبانی وجود دارد که برشمارش بازگشتی هست اما بازگشتی نیست به این معنا که خانواده زبانهای بازگشتی زیرمجموعه سره ای از خانواه زبانهای برشمارش بازگشتی است. ‏ اثبات :زبان Lدر قضیه 11-3را در نظر بگیرید. این زبان برشمارش بازگشتی است ا7ما متمم اش برشمارش بازگشتی نیست .بنابراین طبق قضیه 11-4بازگشتی نیست .در نتیجه مثالی که دنبالش بودیم به ما می دهد . قضیه .................................................................. 11-6 هر زبانی که توسط یک گرامر نامقید تولید شود برشمارش بازگشتی است . ‏ اثبات :گرامر مذکور روال برشمارشی را برای برشمردن همه رشته های زبان به طور سیستماتیک تعریف می کند . برای مثال می توانیم لیستی از همه رشته های wدر Lتهیه کنیم بطوریکه ‏S→ w  ادامه به معنای اینکه wدر یک قدم بدست می آید .چون مجموعه قوانین گرامر متناهی است تعداد متناهی از این رشته ها خاهد بود سپس لیستی از همه رشته ها ی wدر L که دو قدم تولید می شوند تهیه کنیم . ‏S→X→W و به همین ترتیب ادامه می دهیم .این اشتقاق ها را می توانیم با یک ماشین تورینگ شبیه سازی کنیم و درنتیجه روال برشمارش برای زبان داریم و بنابراین برشمارش بازگشتی است . قضیه -7 ................................................................... 11 به ازای هر زبان برشمارش بازگشتی ، Lگرا7مر نامقیدی مانند Gوجود دارد به طوری که ) L=L(Gاست ‏ اثبات :ساختار توضیح داده شده اطمینان می دهد که اگر ‏X→Y آنگاه )e(x)→e(y که ) e(xرمزنگاری رشته را برا7ساس قرار داد داده شده نشان می دهد .با استفاده از استقراء بر روی تعداد قدم ها نشان می دهیم که )e(qw)→e(y قضیه -9 ................................................................... 11 به ازای هر زبان حساس به متن Lبدون یک آتامای کراندار خطی مانند Mهست به طوری که )L=L(M ‏ اثبات :اگر Lمستقل از متن باشد .آنوقت گرامر حساس به متن برای } {-L وجود دارد .نشان می دهیم که اشتقاق ها ی این گرامر می تواند بواسطه ی یک آتامای کراندار خطی شبیه سازی شود. این آتامای کراندار خطی دارای دو شیار خواهد بود یکی حاوی رشته ورودی wو دیگری حاوی شکل های جمله ای که از Gبدست می اید .  ادامه یک نکته کلیدی در این بحث این است که هیچ شکل جمله ای نمی تواند طولی بیش از IwIداشته باشد. نکته دیگری که باید توجه کنیم این است که آتامای کراندار خطی طبق تعزیف نامعین است .این نامعین بودن برای استدالل نیاز می باشد ،چون می توانیم ادعا کنیم قاعده درست همیشه قابل حدس زدن است مجبور به دنبال کردن قاعده جایگزین نمی باشیم .بنابراین محاسبات توضیح داده شده در قضیه 11-6می تواند با استفاده ا7ز فضایی که در ابتدا توسط wاشغال شده انجام شود یعنی میتواند توسط یک آتامای کراندار خطی انجام شود . قضیه ................................................................ 11-10 هر زبان حساس به متن Lبازگشتی است . ‏ اثبات :ساختار در این جا مشابه با آن چیزی است که در قضیه 11-7داشتیم . تمام قوانین تولید شده در قضیه 11-7به جز 11-13غیر انقباضی هستند ، → اما این قانون را می توان حذف کرد .این قانون فقط موقعق الزم می شود که ماشین تورینگ از فضای ورودی اولیه خارج شود که در این جا مصداق ندارد .گرامر بدست آمده با ساختار بدون این قانون غیرضروری ،غیرانقباضی است و اثبات کامل 7است.