سلام.
خواستم ببینم آیا این جملات درست هستند یا خیر؟
۱-هر زیر مجموعه از [tex]\{0,1\}^{\ast}[/tex] می تواند دارای یک اتوماتون قطعی احتمالا نامتناهی باشد.
۲-اگر گرامر منظم G با k قاعده تولید مفروض باشد،"یک اتوماتون متناهی قطعی با حداکثر k+1 حالت وجود دارد که زبان آن با [tex]L(G)[/tex] برابر است".
سلام. وقت بخیر.
راستش خیلی وقته قوانین ماشین هارو مرور نکردم ولی تا اونجا که یادمه تو فرض ماشین متناهی داشتیم که طول ماشین محدوده. ولی مجموعه این محدودیت رو نداره. مثل مجموعه اعداد اول.
برای عبارت دومتون یه قاعده برای تبدیل ماشین متناهی به ماشین دو حالته داشتیم. اگه بشه روی هر یال ماشین یه عبارت منظم نوشت، ایسن عبارت درسته وگرنه زبان [tex]S\to aabaab[/tex] یه گرامر داره و با ذو حالت قابل پیاده سازی نیست.
(۱۶ اسفند ۱۳۹۴ ۰۳:۴۵ ق.ظ)Jooybari نوشته شده توسط: سلام. وقت بخیر.ممنون از اینکه وقت گذاشتین پاسخ دادین.
راستش خیلی وقته قوانین ماشین هارو مرور نکردم ولی تا اونجا که یادمه تو فرض ماشین متناهی داشتیم که طول ماشین محدوده. ولی مجموعه این محدودیت رو نداره. مثل مجموعه اعداد اول.
برای عبارت دومتون یه قاعده برای تبدیل ماشین متناهی به ماشین دو حالته داشتیم. اگه بشه روی هر یال ماشین یه عبارت منظم نوشت، ایسن عبارت درسته وگرنه زبان [tex]S\to aabaab[/tex] یه گرامر داره و با ذو حالت قابل پیاده سازی نیست.
راستش سنجش زده هر دو جمله درسته.ولی من به درست بودن هردو شک دارم.
هر زیر مجموعه،یک زبان محسوب میشه.و ممکنه یک زیر مجموعه از رشته ها،برابر زبانی غیر بازگشتی شمارش پذیر بشه!یعنی دیگه نمیشه واسش گرامر و یا اتوماتون کشید.
اونوقت دیگه نمیشه بگیم که هر زیر مجموعه از [tex]\{0,1\}^{\ast}[/tex] میتواند دارای یک اتوماتون باشد.
بنظرتون استدلالم درسته؟
در مورد پاسخ دومتونم،پس با این روال،با یکسری شرایط (ماشین ما،یک گراف انتقال تعمیم یافته(GTG) باشه) جواب میتونه درست باشه.
پس گزینه دومم با ماشین متناهی قطعی معمولی درست نیست.
ممنونم از پاسختون
(۱۶ اسفند ۱۳۹۴ ۰۴:۵۲ ق.ظ)IranianWizard نوشته شده توسط: هر زیر مجموعه،یک زبان محسوب میشه.و ممکنه یک زیر مجموعه از رشته ها،برابر زبانی غیر بازگشتی شمارش پذیر بشه!یعنی دیگه نمیشه واسش گرامر و یا اتوماتون کشید.
اونوقت دیگه نمیشه بگیم که هر زیر مجموعه از [tex]\{0,1\}^{\ast}[/tex] میتواند دارای یک اتوماتون باشد.
بنظرتون استدلالم درسته؟
راستش من تو همون تعداد حالات ماشین مشکل دارم. اگه قراره تعداد حالات نامحدود باشه که میتونیم درنظر بگیریم به تعداد ۲ به توان طول رشته هم حالت داریم. در این صورت انگار طول رشته رو محدود (در مقایسه با طول ماشین) فرض کردیم.