زبان [tex]L=\{www:w\in\{a,b\}\}[/tex] ماشین تورینگ استاندارد معین در حالت پذیرنده چطوریه ؟ ( اگر تعداد W زوج باشه که راحت میشه با پیدا کردن وسط رشته نوشت )
سلام. روشی که به ذهنم رسید به این شکله: فرض کنید الفبا بصورت ۰ و ۱ باشه. درنظر میگیریم بجای ۰ حروف بزرگ و بجای ۱ حروف کوچیک قرار میدیم.
حرف اول رو با توجه به ۰ یا ۱ بودن حرف a یا A قرار میدیم. حرف دوم رو b یا B و حرف سوم رو c یا C.
در هر مرحله بعد اولین b رو به a و اولین و دومین c رو به b و اولین و دومین و سومین رقم رو به c تغییر میدیم.
این کار رو تا زمیان انجام میدیم که رقم ها تموم بشن. بعد یه رشته از a و یه رشته از b و یه رشته از c داریم که باید طولشون برابر باشه و ترتیب حروف بزرگ و کوچیکشون یکی باشه. به عنوان مثال از نحوه عملکرد:
رشته اولیه: ۱۱۰۱۱۰۱۱۰
مرحله اول: ABc110110
مرحله دوم: AAbBCc110
مرحله سوم: AAaBBbCCc
حالا رشته ها امکان مقایسه رو دارن.
(۲۹ مهر ۱۳۹۳ ۰۱:۱۶ ب.ظ)Jooybari نوشته شده توسط: سلام. روشی که به ذهنم رسید به این شکله: فرض کنید الفبا بصورت ۰ و ۱ باشه. درنظر میگیریم بجای ۰ حروف بزرگ و بجای ۱ حروف کوچیک قرار میدیم.سلام
حرف اول رو با توجه به ۰ یا ۱ بودن حرف a یا A قرار میدیم. حرف دوم رو b یا B و حرف سوم رو c یا C.
در هر مرحله بعد اولین b رو به a و اولین و دومین c رو به b و اولین و دومین و سومین رقم رو به c تغییر میدیم.
این کار رو تا زمیان انجام میدیم که رقم ها تموم بشن. بعد یه رشته از a و یه رشته از b و یه رشته از c داریم که باید طولشون برابر باشه و ترتیب حروف بزرگ و کوچیکشون یکی باشه. به عنوان مثال از نحوه عملکرد:
رشته اولیه: ۱۱۰۱۱۰۱۱۰
مرحله اول: ABc110110
مرحله دوم: AAbBCc110
مرحله سوم: AAaBBbCCc
حالا رشته ها امکان مقایسه رو دارن.
در مرحله سوم از کجا فهمید که این B رو نباید با Aیاa جایگزین کنه ؟
اگر میشه دقیق تر توضیح بدید
باتشکر
(۳۰ مهر ۱۳۹۳ ۱۲:۲۷ ق.ظ)Pakniat نوشته شده توسط:(29 مهر ۱۳۹۳ ۰۱:۱۶ ب.ظ)Jooybari نوشته شده توسط: سلام. روشی که به ذهنم رسید به این شکله: فرض کنید الفبا بصورت ۰ و ۱ باشه. درنظر میگیریم بجای ۰ حروف بزرگ و بجای ۱ حروف کوچیک قرار میدیم.سلام
حرف اول رو با توجه به ۰ یا ۱ بودن حرف a یا A قرار میدیم. حرف دوم رو b یا B و حرف سوم رو c یا C.
در هر مرحله بعد اولین b رو به a و اولین و دومین c رو به b و اولین و دومین و سومین رقم رو به c تغییر میدیم.
این کار رو تا زمیان انجام میدیم که رقم ها تموم بشن. بعد یه رشته از a و یه رشته از b و یه رشته از c داریم که باید طولشون برابر باشه و ترتیب حروف بزرگ و کوچیکشون یکی باشه. به عنوان مثال از نحوه عملکرد:
رشته اولیه: ۱۱۰۱۱۰۱۱۰
مرحله اول: ABc110110
مرحله دوم: AAbBCc110
مرحله سوم: AAaBBbCCc
حالا رشته ها امکان مقایسه رو دارن.
در مرحله سوم از کجا فهمید که این B رو نباید با Aیاa جایگزین کنه ؟
اگر میشه دقیق تر توضیح بدید
باتشکر
هر جا حرف بزرگ دیدیم حرف بزرگ جایگزین میکنیم. اگه قراره بجای یه b یه a بنویسیم، اگه b بود مینویسیم a و اگه B بود مینویسیم A. برای تبدیل c به b هم همینطور. ۰ رو به c و ۱ رو به C تبدیل میکنیم.
روالی که به ذهنم رسید اینطوریه ؛ قبلش از جناب جویباری تشکر می کنم :
خصوصیت این زبان در تعداد w که ضریب ۳ هست اینطوری میشه تورینگ معین براش نوشت :
[attachment=17045]
Component 3 دیگر که فکر کنید میشه براش تورینگ معادل پیدا کرد!