۰
subtitle
ارسال: #۱
الگوریتمی که میشه برای تشخیص تعلق یا عدم تعلق ارائه داد؟
اگه ماشینه این زبان، تورینگ استاندارد باشه ،بهترین الگوریتمی که میشه برای تشخیص تعلق یا عدم تعلق رشته w به زبان L ارائه داد از چه مرتبه ای است؟
{ L={A^2n B^2n C^2n : n>=0
۱)n
۲)n^2
۳)n^2 log n
۴)n^3
{ 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]
[tex]f=2((2n 2) (2n-2) (2n-4) ... (2n-2n))=\theta(n^2)[/tex]
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close