با سلام
میخواستم کسی میتونه ایده کلی طراحی ماشین تورینگ برای زبان ww روی الفبای [tex]\{a, b\}[/tex] و همچنین زبان www دوباره روی همون الفبا.
و یه سوال دیگه اینکه اگه ما این دو زبان رو با ماشین تورینگ استاندادر طراحی کنیم کارایی اون (مرتبه اجراش) چی میشه؟
سلام. برای ww باید بعد از خوندن اولین a یا b بجاش c یا d قرار بدید و تمام a,b ها و x,y هارو رد کنید و به ازای a یا b اول، x یا y قرار بدید. رشته را تا رسیدن به اولین c یا d رد کنید و ...
برای www میتونید بعد از نوشتن اولین x یا y یه a یا b از انتهای رشته بخونید و e یا f قرار بدید و ...
(۰۷ دى ۱۳۹۲ ۰۴:۵۹ ب.ظ)farham_heidari نوشته شده توسط: ماشین تورینگ این دو زبان غیر قطعی هست و روش همان که دوستمون گفت
اما مرتبه اجرایی این ماشین براساس طول w اگر n باشد
O(n میشود چون همه حرکات تو حدود ۳n میشود البته با فرض عمل به صورت غیر قطعی
ولی توی کتاب لینز گفته با ماشین استاندارد واسه ww میشه [tex]O(n^2)[/tex]! و با ماشین دو نواره میشه از مرتبه [tex]O(n)[/tex].
من گیرم واسه ماشین www هستش!
(۰۸ دى ۱۳۹۲ ۰۵:۲۰ ب.ظ)Riemann نوشته شده توسط:(07 دى ۱۳۹۲ ۰۴:۵۹ ب.ظ)farham_heidari نوشته شده توسط: ماشین تورینگ این دو زبان غیر قطعی هست و روش همان که دوستمون گفت
اما مرتبه اجرایی این ماشین براساس طول w اگر n باشد
O(n میشود چون همه حرکات تو حدود ۳n میشود البته با فرض عمل به صورت غیر قطعی
ولی توی کتاب لینز گفته با ماشین استاندارد واسه ww میشه [tex]O(n^2)[/tex]! و با ماشین دو نواره میشه از مرتبه [tex]O(n)[/tex].
من گیرم واسه ماشین www هستش!
پیچیدگیش برای هردو زبان N^2 میشه. چون N تا حرف رو باید بخونه و به ازای هر حرف باید یه مضربی از N جابجا بشه.