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

صفحه 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 ‏بت‎ اما این قانون را می توان حذف کرد . اين قانون فقط موقعق لازم می شود که ماشین د . گرامر بدست آمده با ساختار بدون اين قانون غیرضروری, غیرانقباضی است و اثبات کامل است. تورینگ از فضای ورودی اولیه خارج شود که در اين جا مصداق ندا