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

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

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

اسلاید 2: قضیه 1-11.................................................................فرض کنید S یک مجموعه نامتناهی شمارا باشد . مجموعه توانی آن ناشمارا است .اثبات : فرض کنید S={ ,…. } باشد . آنگاه هر عضو t از می توان به صورت رشته هایی از 0 و 1 نمایش داد. موقعیت i ، 1 است اگر و فقط اگر در t باشد. برای مثال مجموعه به صورت ...و1100100، و به صورت 10101... نمایش داده می شود .روشن است که هر عضوی از را می توان به صورت چنین رشته ای نمایش داد و هریک از این رشته ها یک عضو منحصر بفرد از را نمایش می دهد .

اسلاید 3: ادامهفرض کنید که شمارا باشد آنوقت عناصر آن باد به ترتیبی مانند باشد و همانند آنچه در شکل 11-2 نشان داده شده است می توانستیم آنها را در یک جدول وارد کنیم . در این جدول از عناصری که در قطر اصلی قرار دارند متمم گیری کنید یعنی اینکه 0ها را به 1 و 1ها را به 0 تبدیل کنید. درشکل 11-2 عنصر ...1100 را داریم در نتیجه تبدیل به ...0011می شود دنباله جدید، عنصری از مثلا نمایش میدهد.ولی نمی تواند باشد چون در عضو بودن عنصر با هم تفاوت دارند به همین دلیل نمی تواند یا هر دیگری باشد . بنابراین چاره ای نیست جز اینکه ناشمارا باشد .

اسلاید 4: قضیه 2-11...................................................................به ازای هر∑ غیر تهی زیانهایی هستند که بر شمارش بازگشتی نیستند .اثبات : یک زیان زیر مجموعه ای از است و هر زیر مجموعه یک زبان است . بنابراین مجموعه تمام زبان ها دقیقا است .چون نامتناهی است قضیه 1-11 به ما می گوید که مجموعه تمامی زبانهای روی ∑ ناشمارا است . اما مجموعه تمامی ماشین های تورینگ برشمارشی هستند . بنابراین مجموعه تمامی زبانهای برشمارش بازگشتی شماراست . بواسطه تمرین 16 در انتهای بخش می توان گفت که باید زبانهایی بر روی ∑ باشند که برشمارش بازگشتی نیستند .

اسلاید 5: قضیه 3-11..................................................................زبان برشمارش بازگشتی وجود دارد که متمم برشمارش بازگشتی نیست .اثبات : فرض کنید که {a}=∑ باشد . حال مجموعه تمامی ماشین های تورینگ بر روی این الفبای ورودی را در نظر بگیرید . براساس قضیه 3-10 این مجموعه شمارا است و بنابراین می توان ترتیب ... را برای عناصر آن در نظر گرفت .برای هر ماشین تورینگ زبان برشمارش بازگشتی مانند L( ) را داریم .برعکس برای هر زبان برشمارش بازگشتی بر روی ∑ یک ماشین تورینگ هست که آنرا می پذیرد .

اسلاید 6: ادامهحال ربان جدیدی مانند L را به صورت زیر در نظر می گیریم به ازای 1 ≤ i رشته در L است اگر وفقط اگر ( ) L باشد بنابراین زبان L خوش تعریف است چون ) ) L و در نتیحه L باید یا صحیح یا غلط باشد بعد متمم L را در نظر می گیریم . 1-11که آن هم خوش تعریف هست اما نشان خواهیم داد که برشمارش بازگشتی نیست . این را با برهان خلف نشان می دهیم . با فرض اینکه برشمارش بازگشتی است شروع می کنیم اگر چنین باشد باید ماشین تورینگی مانند باشد که 2-11

اسلاید 7: رشته را در نظر بگیرید آیا در L است یا در ؟ فرض کنید که باشد . با استفاده از 2-11 نتیجه می گیریم که اما با استفاده از 1-11 نتیحه می گیریم حال اگر فرض کنیم که در L هست آنوقت و از 2-11 نتیجه می گیریماما باز از 1-11 نتیجه می گیریم که

اسلاید 8: تناقض ، گریز ناپذیر است و باید نتیجه گیری کنیم که فرض ما که برشمارش بازگشتی است غلط است برای تکمیل اثبات باید نشان دهیم که L برشمارش بازگشتی است برای این منظور می توانیم از روال برشمردن شناخته شده برای ماشین های تورینگ استفاده کنیم . اگر را داشته باشیم ابتدا i را با شمارش تعداد a ها پیدا می کنیم . سپس با استفاده از روال برشمردن برای ماشین تورینگ را پیدا می کنیم .نهایتا توصیف آنرا همراه با به ماشین تورینگ جامع که اعمال M را روی شبیه سازی می کند می دهیم . اگر در L باشد محاسبات نهایتا پایان می یابد با ترکیب کردن این ماشین تورینگی بوجود می اید که هرL را می پذیرد در نتیجه با استفاده از تعریف 1-11 برشمارش بازگشتی می باشد .

اسلاید 9: قضیه 4-11................................................................اگر زبان L و متمم آن هر دو برشمارش بازگشتی باشند آنگاه هر دو زبان بازگشتی هستند اگر Lبازگشتی باشد آنوقت هم بازگشتی است و نتیجتاهر دو برشمارش بازگشتی هستند . اثبات : اگر L و هر دو برشمارش بازگشتی باشند آنوقت ماشین های تورینگ M و به ترتیب به عنوان روال های برشمردن Lو وجود دارند . اولی ... را در L و دومی ...., را در تولید می کند حال فرض می کنیم داده شده است ابتدا اجازه می دهیم که M رشته را تولید کرده و آن را با w مقایسه کند

اسلاید 10: ادامه اگر یکی نبودند اجازه می دهیم که توسط تولید شود و مجددا مقایسه را انجام می دهیم اگر نیاز به ادامه باشد اجازه می دهیم که M رشته و رشته را تولید کند و به همین نحو دامه می دهیم .هر توسط M و یا تولید می شود بنابراین در نهایت تطبیقی خواهیم داشت . اگر رشته مذک.ر توسط M تولید شود و w به L تعلق دارد و در غیر این صورت به . این فرایند یک الگوریتم عضویت برای هر دوی L و است و بنابراین هر دو بازگشتی هستند .

اسلاید 11: بالعکس فرض کنید که L بازگشتی باشد آنوقت الگوریتم عضویتی برای آن وجود دارد اما همین الگوریتم عضویتی برای می شود، اگر فقط نتیجه آن را عکس کنیم . بنابراین بازگشتی است . چون هر زبان بازگشتی ، برشمارش بازگشتی است اثبات کامل است .

اسلاید 12: قضیه 5-11...................................................................زبانی وجود دارد که برشمارش بازگشتی هست اما بازگشتی نیست به این معنا که خانواده زبانهای بازگشتی زیرمجموعه سره ای از خانواه زبانهای برشمارش بازگشتی است.اثبات : زبان L در قضیه 3-11 را در نظر بگیرید. این زبان برشمارش بازگشتی است اما متمم اش برشمارش بازگشتی نیست . بنابراین طبق قضیه 4-11 بازگشتی نیست . در نتیجه مثالی که دنبالش بودیم به ما می دهد .

اسلاید 13: قضیه 6-11..................................................................هر زبانی که توسط یک گرامر نامقید تولید شود برشمارش بازگشتی است .اثبات : گرامر مذکور روال برشمارشی را برای برشمردن همه رشته های زبان به طور سیستماتیک تعریف می کند .برای مثال می توانیم لیستی از همه رشته های w در L تهیه کنیم بطوریکهS→ w

اسلاید 14: ادامه به معنای اینکه w در یک قدم بدست می آید . چون مجموعه قوانین گرامر متناهی است تعداد متناهی از این رشته ها خاهد بود سپس لیستی از همه رشته ها ی w در L که دو قدم تولید می شوند تهیه کنیم .S→X→Wو به همین ترتیب ادامه می دهیم . این اشتقاق ها را می توانیم با یک ماشین تورینگ شبیه سازی کنیم و درنتیجه روال برشمارش برای زبان داریم و بنابراین برشمارش بازگشتی است .

اسلاید 15: قضیه 7-11...................................................................به ازای هر زبان برشمارش بازگشتی L ، گرامر نامقیدی مانند G وجود دارد به طوری که L=L(G) است اثبات : ساختار توضیح داده شده اطمینان می دهد که اگرX→Y آنگاه e(x)→e(y)که e(x) رمزنگاری رشته را براساس قرار داد داده شده نشان می دهد . با استفاده از استقراء بر روی تعداد قدم ها نشان می دهیم که e(qw)→e(y)

اسلاید 16: قضیه 9-11...................................................................به ازای هر زبان حساس به متن L بدون یک آتامای کراندار خطی مانند M هست به طوری که L=L(M) اثبات : اگر L مستقل از متن باشد. آنوقت گرامر حساس به متن برای L-{ } وجود دارد . نشان می دهیم که اشتقاق ها ی این گرامر می تواند بواسطه ی یک آتامای کراندار خطی شبیه سازی شود. این آتامای کراندار خطی دارای دو شیار خواهد بود یکی حاوی رشته ورودی w و دیگری حاوی شکل های جمله ای که از Gبدست می اید .

اسلاید 17: ادامه یک نکته کلیدی در این بحث این است که هیچ شکل جمله ای نمی تواند طولی بیش از IwI داشته باشد.نکته دیگری که باید توجه کنیم این است که آتامای کراندار خطی طبق تعزیف نامعین است . این نامعین بودن برای استدلال نیاز می باشد ، چون می توانیم ادعا کنیم قاعده درست همیشه قابل حدس زدن است مجبور به دنبال کردن قاعده جایگزین نمی باشیم . بنابراین محاسبات توضیح داده شده در قضیه 6-11 می تواند با استفاده از فضایی که در ابتدا توسط w اشغال شده انجام شود یعنی میتواند توسط یک آتامای کراندار خطی انجام شود .

اسلاید 18: قضیه 10-11................................................................هر زبان حساس به متن L بازگشتی است .اثبات : ساختار در این جا مشابه با آن چیزی است که در قضیه 7-11 داشتیم . تمام قوانین تولید شده در قضیه 7-11 به جز 13-11 غیر انقباضی هستند ، →اما این قانون را می توان حذف کرد . این قانون فقط موقعق لازم می شود که ماشین تورینگ از فضای ورودی اولیه خارج شود که در این جا مصداق ندارد . گرامر بدست آمده با ساختار بدون این قانون غیرضروری، غیرانقباضی است و اثبات کامل است.