الگوریتمی که میشه برای تشخیص تعلق یا عدم تعلق ارائه داد؟ - نسخه‌ی قابل چاپ

الگوریتمی که میشه برای تشخیص تعلق یا عدم تعلق ارائه داد؟ - svk7 - 30 دى ۱۳۹۱ ۰۱:۱۹ ب.ظ اگه ماشینه این زبان، تورینگ استاندارد باشه ،بهترین الگوریتمی که میشه برای تشخیص تعلق یا عدم تعلق رشته w به زبان L ارائه داد از چه مرتبه ای است؟ { L={A^2n B^2n C^2n : n>=0 ۱)n ۲)n^2 ۳)n^2 log n ۴)n^3

الگوریتمی که میشه برای تشخیص تعلق یا عدم تعلق ارائه داد؟ - Jooybari - 02 بهمن ۱۳۹۱ ۰۳:۳۳ ب.ظ سلام. بنظرم میشه اول دو تا A رو به a تبدیل کرد و تا آخر رشته (یعنی یا نال و یا b) رفت. اگه با نال رسیدیم دوتا C رو به c و دوتا B رو به b تبدیل میکنیم و اگه به b رسیدیم هم فقط دوتا B رو به b تبدیل میکنیم. بعد به چپ میریم تا به a برسیم و به حالت اول بریم (تا تکرار بشه). شرط پایان هم وقتیه که از حالت اول به C یا b برسیم. (اگه به C رسیدیم باید فقط دوتا C داشته باشیم.) اگه منظور از مرتبه تعداد حرکات هد باشه داریم: [tex]f=2((2n 2) (2n-2) (2n-4) ... (2n-2n))=\theta(n^2)[/tex]