سلام
[img]
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
[/img]ممنون میشم این سوال را حل کنید.
(۰۸ خرداد ۱۳۹۵ ۱۲:۲۸ ق.ظ)automata01 نوشته شده توسط: سلام
[img]
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
[/img]ممنون میشم این سوال را حل کنید.
سوای بحث ارتباط تصمیم‌پذیری یک زبان به ماشین تورینگ و ...، هر زبانی که بتوان الگوریتمی یا روشی برای تعیین اینکه ورودی داده شده به آن زبان تعلق دارد یا خیر، تصمیم‌پذیر هست.
این مثالی که شما آوردید کمی مبهم به نظر میرسه ولی خیلی ساده هست چون به راحتی میتوان گفت (الگوریتم یا روش تعیین کرد) که رشته‌ی ورودی به L تعلق دارد یا خیر.
پی‌نوشت: حتی اگر نمره‌ی درس مبانی کامپیوتر در حال حاضر نامعلوم باشد، بالاخره پس از مدتی مشخص می‌شود؛ پس L تصمیم‌پذیر است.
اگر الگوریتمی که تعیین می‌کنیم "بالاخره" به جواب برسد (تعیین کند که ورودی عضو L هست یا خیر) پس زبان تصمیم‌پذیر هست، این منتظر نمره‌ی درس مبانی کامپیوتر موندن (در صورتی که الان نامعلوم باشد) معادل همان "بالاخره" هست.