تالار گفتمان مانشت

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

سلام. بنظرم میشه اول دو تا 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]