سلام کسی حل المسائل فارسی سیپسر را نداره؟
من فقط سوال ۱۴ و ۱۵ فصل ۳ را می خوام.
(۲۲ خرداد ۱۳۹۵ ۰۶:۲۳ ب.ظ)automata01 نوشته شده توسط: سلام کسی حل المسائل فارسی سیپسر را نداره؟ببینید جوابی که ضمیمه کردم با ویرایش کتابتون همخونی داره یا نه. ویرایش کتاب رو ذکر کنید.
من فقط سوال ۱۴ و ۱۵ فصل ۳ را می خوام.
[attachment=20047]
ورژن کامل حل‌المسائل رو هم ضمیمه کردم. در حل‌المسائل فارسی، سؤالات مد نظر شما رو حل نکرده‌اند.
[attachment=20048]
بله همین ویرایش هست.
ممنون ولی من حل المسائل فارسی اش را خواستم.
زبان اصلی را دارم.
چون فردا صبح امتحان دارم فرصت ترجمه ندارم.
(۲۲ خرداد ۱۳۹۵ ۰۷:۰۹ ب.ظ)automata01 نوشته شده توسط: بله همین ویرایش هست.
ممنون ولی من حل المسائل فارسی اش را خواستم.
زبان اصلی را دارم.
چون فردا صبح امتحان دارم فرصت ترجمه ندارم.
والا انگلیسی‌ای که نوشته خیلی basic هست و نیازی به ترجمه نیست. فرصت شد ترجمه‌ی این دو جواب رو میذارم.
۱۵ الف.
برای دو زبان قابل تشخیص (تشخیص‌پذیر) L1 و L2 دو ماشین تورینگ M1 و M2 رو در نظر میگیریم که هر کدوم زبان متناظرش رو تشخیص میده.
ماشین [tex]M'[/tex] رو میسازیم که اجتماع L1 و L2 رو تشخیص بده، به این ترتیب که برای هر رشته‌ی ورودی w:
M1 و M2 رو روی w مرحله به مرحله اجرا میکنیم (یعنی یک مرحله از M1، بعد M2، بعد یک مرحله‌ی دیگر از M1 و ... )
اگر یکی از اون‌ها رشته رو پذیرفت، پس رشته رو میپذیریم. اگر هر دوی M1 و M2 ریجکت کردند یا در لوپ افتادند، [tex]M'[/tex] هم به ترتیب ریجکت میکنه یا در لوپ میفته.
۱۵ ب.
برای دو زبان قابل تشخیص (تشخیص‌پذیر) L1 و L2 دو ماشین تورینگ M1 و M2 رو در نظر میگیریم که هر کدوم زبان متناظرش رو تشخیص میده.
ماشین تصمیم‌ناپذیر [tex]M'[/tex] رو میسازیم که الحاق L1 و L2 رو تشخیص میده، به این گونه که:
رشته‌ی ورودی w رو به دو بخش w=w1w2 تقسیم میکنیم و M1 رو روی w1 و M2 رو روی w2 اجرا میکنیم. اگر M1 رشته‌ی w1 رو ریجکت کرده که ماشین [tex]M'[/tex] هم ریجکت میکنه، اگه اکسپت کرد، M2 رو روی w2 اجرا میکنیم و اگه اینم اکسپت شد، رشته رو اکسپت میکنیم.
اگه بشه رشته‌ی ورودی رو به دو قسمت w1 و w2 تقسیم کرد که در نهایت اکسپت بشه، w جزو الحاق L1 و L2 هست، در غیر این صورت، خیر (یعنی تمامی حالات برش w به w1 و w2 رو امتحان میکنیم).
۱۵ ج.
M ماشینی هست که زبان قابل تشخیص L1 رو تشخیص میده.
برای تشخیص *L، ماشین تصمیم‌ناپذیر [tex]M'[/tex] رو میسازیم به قسمی که رشته‌ی ورودی w رو به صورت w1w2...wn برش میده و روی هر کدوم از زیررشته‌ها M رو اجرا میکنه، اگه M تمامی اونا رو پذیرفت، رشته‌ی ورودی پذیرفته میشه. اگه روی یکی ریجکت کرد، رشته‌ی ورودی ریجکت میشه.
اگه بشه w رو به یه جور w1w2...wn برش داد که توسط [tex]M'[/tex] پذیرفته بشه، w رو در نهایت میپذیریم.
۱۵ د.
برای دو زبان قابل تشخیص (تشخیص‌پذیر) L1 و L2 دو ماشین تورینگ M1 و M2 رو در نظر میگیریم که هر کدوم زبان متناظرش رو تشخیص میده.
ماشین [tex]M'[/tex] رو میسازیم که اشتراک L1 و L2 رو تشخیص بده، به این ترتیب که برای هر رشته‌ی ورودی w:
M1 رو روی w اجرا میکنیم اگه ریجکت کرد که رشته ریجکت میشه، اگه پذیرفت، بعد M2 رو هم اجرا میکنیم. اگه اینم پذیرفت که در نهاین میپذیریم. اگه ریجکت کرد، در نهایت ریجکت میکنیم.
۱۴ الف.
برای دو زبان تصمیم‌پذیر L1 و L2 دو ماشین تورینگ M1 و M2 رو در نظر میگیریم که هر کدوم قادر هست روی زبان متناظرش تصمیم بگیره.
ماشین تصمیم‌پذیر [tex]M'[/tex] رو میسازیم که اجتماع L1 و L2 رو تصمیم بگیره، به این ترتیب که برای هر رشته‌ی ورودی w:
M1 رو روی w اجرا میکنیم، اگه پذیرفت که میپذیریم رشته رو. در غیر این صورت (اگه نپذیرفت) M2 رو اجرا میکنیم که اگه پذیرفت اکسپت میکنیم. اگه اینم نه، که ریجکت در نهایت.
فرقش با ۱۵ الف در این هست که اونجا تصمیم‌پذیر نبود و ممکن بود در حلقه بیفته. برای همین مرحله به مرحله یکی از M1 اجرا میکردیم یکی از M2 ولی اینجا مطمئن هستیم که در نهایت M1 تموم میشه (چه پذیرش چه عدم پذیرش).
۱۴ ب.
برای دو زبان تصمیم‌پذیر L1 و L2 دو ماشین تورینگ M1 و M2 رو در نظر میگیریم که هر کدوم قادر هست روی زبان متناظرش تصمیم بگیره.
ماشین تصمیم‌پذیر [tex]M'[/tex] رو میسازیم که الحاق L1 و L2 رو تصمیم بگیره، به این ترتیب که برای هر رشته‌ی ورودی w:
w رو به w1w2 برش میدهیم. M1 را روی w1 و M2 رو روی w2 اجرا میکنیم. اگر هر دو پذیرفتند، رشته‌ی w رو میپذیریم. ذر غیر این صورت به w1 و w2 جدید برش میدهیم و فرایند فوق رو تکرار میکنیم. چنانچه تمامی برش‌های ممکن بدون موفقیت پایان یافتند، ریجکت میکنیم. اگر برشی با موفقیت روبرو شد (هر دو ماشین پذیرفتند)، میپذیریم.
فرقش با قسمت مشابه سوال ۱۵ در این هست که یک رشته رو به یک برش تبدیل میکنیم و ماشین‌ها رو اجرا میکنیم اما در ۱۵، به خاطر تصمیم‌پذیر نبودن (امکان ایجاد loop) مجبور هستیم همزمان تمامی برش‌ها رو امتحان کنیم.
۱۴ ج.
برای زبان تصمیم‌پذیر L1 ماشین تورینگ M1 رو در نظر میگیریم که قادر هست روی زبان این زبان تصمیم بگیره.
ماشین تصمیم‌پذیر [tex]M'[/tex] رو میسازیم که *L رو تصمیم بگیره، به این ترتیب که برای هر رشته‌ی ورودی w:
w رو به w1w2...wn برش میدهیم. M1 رو روی تمامی wi ها اجرا میکنیم. اگر هر تمامی wi ها رو پذیرفت، رشته پذیرفته میشه. در غیر این صورت، رشته ریجکت میشه.
اگر حالتی از w1w2...wn پیدا بشه که اجرای M1 رو تمامی‌شون پذیرفته بشه، w رو میپذیریم.
۱۴ د.
برای زبان تصمیم‌پذیر L1 ماشین تورینگ M1 رو در نظر میگیریم که قادر هست روی زبان این زبان تصمیم بگیره.
ماشین تصمیم‌پذیر [tex]M'[/tex] رو میسازیم که مکمل L رو تصمیم بگیره، به این ترتیب که برای هر رشته‌ی ورودی w:
M1 رو روی L1 اجرا میکنیم، اگر پذیرفت، رشته‌ی w رو ریجکت میکنیم. اگر نپذیرفت، w پذیرفته میشه. چون M1 تصمیم‌پذیر هست، پس [tex]M'[/tex]هم همینطور چون هر وقت M1 متوقف شود، [tex]M'[/tex] هم می‌شود.
۱۴ هـ.
برای دو زبان تصمیم‌پذیر L1 و L2 دو ماشین تورینگ M1 و M2 رو در نظر میگیریم که هر کدوم قادر هست روی زبان متناظرش تصمیم بگیره.
ماشین تصمیم‌پذیر [tex]M'[/tex] رو میسازیم که اشتراک L1 و L2 رو تصمیم بگیره، به این ترتیب که برای هر رشته‌ی ورودی w:
اول M1 رو روی w اجرا میکنیم، اگر ریجکت کرد، w ریجکت میشه.
در غیر این صورت، سپس M2 رو اجرا میکنیم، اگه M2 هم پذیرفت، رشته‌ی ورودی پذیرفته میشه. در غیر این صورت ریجکت میشه.
فرقش با قسمت مشابه سوال ۱۵ در این هست که اونجا ممکن هست مثلاً M1 هیچوقت متوقف نشه چون تصمیم‌پذیر نیست و فقط تشخیص‌پذیر هست، در نتیجه [tex]M'[/tex] هم تصمیم‌پذیر نخواهد بود و ممکن هست به loop بیفته.
خیلی متشکرم