سلام. وقت بخیر.
راستش خیلی وقته قوانین ماشین هارو مرور نکردم ولی تا اونجا که یادمه تو فرض ماشین متناهی داشتیم که طول ماشین محدوده. ولی مجموعه این محدودیت رو نداره. مثل مجموعه اعداد اول.

برای عبارت دومتون یه قاعده برای تبدیل ماشین متناهی به ماشین دو حالته داشتیم. اگه بشه روی هر یال ماشین یه عبارت منظم نوشت، ایسن عبارت درسته وگرنه زبان [tex]S\to aabaab[/tex] یه گرامر داره و با ذو حالت قابل پیاده سازی نیست.

(۱۶ اسفند ۱۳۹۴ ۰۳:۴۵ ق.ظ)Jooybari نوشته شده توسط:  سلام. وقت بخیر.
راستش خیلی وقته قوانین ماشین هارو مرور نکردم ولی تا اونجا که یادمه تو فرض ماشین متناهی داشتیم که طول ماشین محدوده. ولی مجموعه این محدودیت رو نداره. مثل مجموعه اعداد اول.

برای عبارت دومتون یه قاعده برای تبدیل ماشین متناهی به ماشین دو حالته داشتیم. اگه بشه روی هر یال ماشین یه عبارت منظم نوشت، ایسن عبارت درسته وگرنه زبان [tex]S\to aabaab[/tex] یه گرامر داره و با ذو حالت قابل پیاده سازی نیست.

ممنون از اینکه وقت گذاشتین پاسخ دادین.
راستش سنجش زده هر دو جمله درسته.ولی من به درست بودن هردو شک دارم.
هر زیر مجموعه،یک زبان محسوب میشه.و ممکنه یک زیر مجموعه از رشته ها،برابر زبانی غیر بازگشتی شمارش پذیر بشه!یعنی دیگه نمیشه واسش گرامر و یا اتوماتون کشید.
اونوقت دیگه نمیشه بگیم که هر زیر مجموعه از [tex]\{0,1\}^{\ast}[/tex] میتواند دارای یک اتوماتون باشد.
بنظرتون استدلالم درسته؟

در مورد پاسخ دومتونم،پس با این روال،با یکسری شرایط (ماشین ما،یک گراف انتقال تعمیم یافته(GTG) باشه) جواب میتونه درست باشه.
پس گزینه دومم با ماشین متناهی قطعی معمولی درست نیست.

ممنونم از پاسختون

(۱۶ اسفند ۱۳۹۴ ۰۴:۵۲ ق.ظ)IranianWizard نوشته شده توسط:  هر زیر مجموعه،یک زبان محسوب میشه.و ممکنه یک زیر مجموعه از رشته ها،برابر زبانی غیر بازگشتی شمارش پذیر بشه!یعنی دیگه نمیشه واسش گرامر و یا اتوماتون کشید.
اونوقت دیگه نمیشه بگیم که هر زیر مجموعه از [tex]\{0,1\}^{\ast}[/tex] میتواند دارای یک اتوماتون باشد.
بنظرتون استدلالم درسته؟

راستش من تو همون تعداد حالات ماشین مشکل دارم. اگه قراره تعداد حالات نامحدود باشه که میتونیم درنظر بگیریم به تعداد ۲ به توان طول رشته هم حالت داریم. در این صورت انگار طول رشته رو محدود (در مقایسه با طول ماشین) فرض کردیم.