زمان کنونی: ۱۵ آبان ۱۴۰۳, ۰۱:۵۲ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

زبان ماشین تورینگ

ارسال:
  

automata01 پرسیده:

زبان ماشین تورینگ

با سلام
من در درس نظریه محاسبه خیلی ضعیفم و دلیلش هم این هست که استادم با اینکه خیلی با سواد هستند ولی قدرت تفهیم درس را به من و هم کلاسی هام ندارند.برای همین از شما کمک می خوام.لطفا اگر کسی این سوال را می دونه برام توضیح بده.
منبعی که به ما معرفی شده "مقدمه ای بر نظریه محاسبات" اثر سیپسر هست.
با تشکر
[تصویر:  405258_OfODP.png]
نقل قول این ارسال در یک پاسخ

۱
ارسال:
  

Pure Liveliness پاسخ داده:

RE: زبان ماشین تورینگ

(۰۷ خرداد ۱۳۹۵ ۱۱:۱۵ ب.ظ)automata01 نوشته شده توسط:  با سلام
من در درس نظریه محاسبه خیلی ضعیفم و دلیلش هم این هست که استادم با اینکه خیلی با سواد هستند ولی قدرت تفهیم درس را به من و هم کلاسی هام ندارند.برای همین از شما کمک می خوام.لطفا اگر کسی این سوال را می دونه برام توضیح بده.
منبعی که به ما معرفی شده "مقدمه ای بر نظریه محاسبات" اثر سیپسر هست.
با تشکر
[تصویر:  405258_OfODP.png]
سلام. توی این مدت زمان کم تا امتحان ترم نمیشه کتاب مرجع خوند. شاید بشه یه تیکه هایی ازش رو خوند. جزوه ی دکتر کارگهی توی مانشت هست. اون رو بخونید خیلی خوبه. تورینگ هم خوب توضیح دادن وویسشون هم هست.
چند تا رشته امتحان میکنیم. هر رشته روی نوار قرار داره، اطراف رشته بی نهایت فضای خالی یا Blank هست که با B نشون میدن، وسط رشته امکان نداره این فضای خالی وجود داشته باشه. مثلا روی نوار رشته ی ۰۰۰۱۱۰۱۰۰ به صورت …. BBBBBBBB000110100BBBBBB…. هست. حالا، با رسیدن به هر حرف از رشته، یه حرف دیگه مثلا ۰ یا ۱ یا x یا هر چی جاش قرار داده میشه. معمولا رشته ای که انتخاب میشه اول به صورت یه تعدادی ۱ بعد ۰ بعد یه تعدادی ۱ انتخاب میشه. چون خیلی وقتا اون چیزی که ماشین تورینگ بر میگردونه یعنی عملی که روی این رشته انجام میده مثلا ضرب یک های قسمت اول یعنی قبل از صفر در ۱ ها ی قسمت دوم هست. نه لزوماََ البته. هر تابعی ممکنه پیاده سازی بشه توسط ماشین تورینگ.
توی این مسئله گام به گام عملیات رو توضیح میدیم. R حرکت به راست. L حرکت به چپ. B فضای خالی هست بعد و قبل از رشته.
مثلا حرکت ۱ , R <- یک یعنی اگر روی نوار حرف اول از رشته که خوندیم برابر با ۱ بود، به جاش ۱ بذاره، بره راست.
مسئله : توی اولین state هستیم. اگه اول رشته ۰ مشاهده کنیم، جاش X میذاریم میریم راست. حالا رسیدیم به q2 اگه ۰ ببینیم، جاش ۰ میذاریم میریم راست. و به همین صورت ادامه میدیم تا رسیدن به حالت نهایی. و بعد میبینیم چه رشته ای حاصل شده، بعد حدس میزنیم این ماشین تورینگ چه بلایی سر رشته آورده و چی رو محاسبه کرده... ادامه دارد :|
نقل قول این ارسال در یک پاسخ

ارسال:
  

automata01 پاسخ داده:

RE: زبان ماشین تورینگ

(۰۸ خرداد ۱۳۹۵ ۰۱:۲۲ ق.ظ)pure liveliness نوشته شده توسط:  
(07 خرداد ۱۳۹۵ ۱۱:۱۵ ب.ظ)automata01 نوشته شده توسط:  با سلام
من در درس نظریه محاسبه خیلی ضعیفم و دلیلش هم این هست که استادم با اینکه خیلی با سواد هستند ولی قدرت تفهیم درس را به من و هم کلاسی هام ندارند.برای همین از شما کمک می خوام.لطفا اگر کسی این سوال را می دونه برام توضیح بده.
منبعی که به ما معرفی شده "مقدمه ای بر نظریه محاسبات" اثر سیپسر هست.
با تشکر
[تصویر:  405258_OfODP.png]
سلام. توی این مدت زمان کم تا امتحان ترم نمیشه کتاب مرجع خوند. شاید بشه یه تیکه هایی ازش رو خوند. جزوه ی دکتر کارگهی توی مانشت هست. اون رو بخونید خیلی خوبه. تورینگ هم خوب توضیح دادن وویسشون هم هست.
چند تا رشته امتحان میکنیم. هر رشته روی نوار قرار داره، اطراف رشته بی نهایت فضای خالی یا Blank هست که با B نشون میدن، وسط رشته امکان نداره این فضای خالی وجود داشته باشه. مثلا روی نوار رشته ی ۰۰۰۱۱۰۱۰۰ به صورت …. BBBBBBBB000110100BBBBBB…. هست. حالا، با رسیدن به هر حرف از رشته، یه حرف دیگه مثلا ۰ یا ۱ یا x یا هر چی جاش قرار داده میشه. معمولا رشته ای که انتخاب میشه اول به صورت یه تعدادی ۱ بعد ۰ بعد یه تعدادی ۱ انتخاب میشه. چون خیلی وقتا اون چیزی که ماشین تورینگ بر میگردونه یعنی عملی که روی این رشته انجام میده مثلا ضرب یک های قسمت اول یعنی قبل از صفر در ۱ ها ی قسمت دوم هست. نه لزوماََ البته. هر تابعی ممکنه پیاده سازی بشه توسط ماشین تورینگ.
توی این مسئله گام به گام عملیات رو توضیح میدیم. R حرکت به راست. L حرکت به چپ. B فضای خالی هست بعد و قبل از رشته.
مثلا حرکت ۱ , R <- یک یعنی اگر روی نوار حرف اول از رشته که خوندیم برابر با ۱ بود، به جاش ۱ بذاره، بره راست.
مسئله : توی اولین state هستیم. اگه اول رشته ۰ مشاهده کنیم، جاش X میذاریم میریم راست. حالا رسیدیم به q2 اگه ۰ ببینیم، جاش ۰ میذاریم میریم راست. و به همین صورت ادامه میدیم تا رسیدن به حالت نهایی. و بعد میبینیم چه رشته ای حاصل شده، بعد حدس میزنیم این ماشین تورینگ چه بلایی سر رشته آورده و چی رو محاسبه کرده... ادامه دارد :|

خیلی ممنونم Shy
بی صبرانه منتظر ادامه هستم Smile
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۲
ارسال:
  

Jooybari پاسخ داده:

RE: زبان ماشین تورینگ

سلام.
با تشکر از توضیحات خانم pure liveliness، منم نتونستم زبان خوبی برای این ماشین تعریف کنم. بهترین تعریف، بنظرم زبان شامل رشته‌هاییه که حداقل ۲ تا حرف ۱ دارن. روش کار ماشین به این شکله:
اگه حرف اول ۰ بود بجاش x قرار بده و به راست برو. تا زمانی که به B نرسیدی به راست برو. بجای اولین B حرف ۰ رو قرار بده و به چپ برو تا به اولین حرف x در سمت چپ برسی. (یعنی اگه اولین حرف رشته ۰ بود بجاش بنویس x و به آخر رشته ۰ اضافه کن و برگرد به اولین حرف بعد از x.)
اگه ۱ دیدی به راست برو و تا زمانی که ۰ دیدی به راست برو. اگه ۱ دیدی به راست برو و پایان. (یعنی فقط ۲ تا ۱ داشته باشه. فقط رشته رو تغییر میده.)
نقل قول این ارسال در یک پاسخ

ارسال:
  

Pure Liveliness پاسخ داده:

RE: زبان ماشین تورینگ

(۰۹ خرداد ۱۳۹۵ ۰۸:۵۶ ب.ظ)Jooybari نوشته شده توسط:  سلام.
با تشکر از توضیحات خانم pure liveliness، منم نتونستم زبان خوبی برای این ماشین تعریف کنم. بهترین تعریف، بنظرم زبان شامل رشته‌هاییه که حداقل ۲ تا حرف ۱ دارن. روش کار ماشین به این شکله:
اگه حرف اول ۰ بود بجاش x قرار بده و به راست برو. تا زمانی که به B نرسیدی به راست برو. بجای اولین B حرف ۰ رو قرار بده و به چپ برو تا به اولین حرف x در سمت چپ برسی. (یعنی اگه اولین حرف رشته ۰ بود بجاش بنویس x و به آخر رشته ۰ اضافه کن و برگرد به اولین حرف بعد از x.)
اگه ۱ دیدی به راست برو و تا زمانی که ۰ دیدی به راست برو. اگه ۱ دیدی به راست برو و پایان. (یعنی فقط ۲ تا ۱ داشته باشه. فقط رشته رو تغییر میده.)
من توی چند تا رشته به مشکل برخوردم. یه کم هم حالم خوش نبود نتونستم فک کنم. ممنون که جواب نصفه ی من رو کامل کردید دکتر.
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

automata01 پاسخ داده:

RE: زبان ماشین تورینگ

سلام
از ممنونم از همه
فقط یک سوال؟
مگه نباید جواب این سوال مثلا به سبک زیر باشه؟ چطور باید بهش برسیم.
۰+۱*(۱+۰)
اگه سوالم خیلی پیش پا افتادس مسخره ام نکنید
واقعا در نظریه افسیلنم.
نقل قول این ارسال در یک پاسخ

ارسال:
  

fatemeh69 پاسخ داده:

RE: زبان ماشین تورینگ

[
(۱۰ خرداد ۱۳۹۵ ۰۳:۱۵ ب.ظ)automata01 نوشته شده توسط:  سلام
از ممنونم از همه
فقط یک سوال؟
مگه نباید جواب این سوال مثلا به سبک زیر باشه؟ چطور باید بهش برسیم.
۰+۱*(۱+۰)
اگه سوالم خیلی پیش پا افتادس مسخره ام نکنید
واقعا در نظریه افسیلنم.

سلام
در واقع این موضوع به طور کلی صادق نیست که بخواهیم برای زبان هر ماشین تورینگی عبارت منظم بنویسیم
یعنی زبان هر ماشین تورینگی لزوما منظم نیست
اما می توان برای زبان های منظم هم ماشین تورینگ طراحی کرد
پس بعضی از ماشین های تورینگ رو میشه براش عبارت منظم داد (اما نه همشونو)
زبان این ماشین تورینگ در حقیقت همانی است که جناب جویباری فرمودند : رشته ایی که حداقل دوتا ۱ دارند
پس این زبان منظمه (چون براش می شه dfa کشید یا گرامر منظم داد یا عبارت منظم داد )
پس عبارت منظم دارد
و عبارت منظم آن به صورت زیر است:
[tex](0+1)^{\ast}1(0+1)^{\ast}1(0+1)^{\ast}[/tex]


دونکته (که ممکنه بدونید اما حس کردم باید بگم):
- در عبارت منظم علامت "+" به معنای or است
- و در ماشین تورینگ هم برای پذیرش یک رشته لزوما نباید تا انتهای رشته خوانده شود
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

automata01 پاسخ داده:

RE: زبان ماشین تورینگ

ممنون از شما
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  اصول ماشین های کنترل عددی و مطلبی ملینا ارشد ۱ ۲,۳۵۰ ۲۸ بهمن ۱۴۰۰ ۰۸:۰۹ ب.ظ
آخرین ارسال: vista2000
  بوک کلاب ماشین لرنینگ با حضور متخصص از شرکت های گوگل ، اساتید و دانشجویان دکترا و. Doctorwho ۰ ۱,۶۶۰ ۱۳ آبان ۱۴۰۰ ۱۲:۰۹ ب.ظ
آخرین ارسال: Doctorwho
  کدام زبان برای هوش مصنوعی بهتر است؟ فرق بین زبان های هوش مصنوعی چیست؟ azam2075 ۳ ۶,۰۱۲ ۱۴ مهر ۱۴۰۰ ۰۷:۲۱ ب.ظ
آخرین ارسال: علیصا
  سوال یادگیری ماشین isoa ۳ ۴,۳۱۴ ۰۸ مرداد ۱۳۹۹ ۰۶:۳۴ ق.ظ
آخرین ارسال: BBumir
  نحوه محاسبه دفیق لگاریتم بدون ماشین حساب mcse2010 ۲ ۸۲,۲۱۵ ۲۸ مهر ۱۳۹۸ ۰۹:۳۸ ق.ظ
آخرین ارسال: chemical_darton29
  لینک دانلود نسخه ازمایشی ترجمه کتاب یادگیری ماشین میشل انرژی مثبت ۲ ۱۳,۰۴۲ ۱۷ شهریور ۱۳۹۸ ۱۱:۱۶ ب.ظ
آخرین ارسال: forooghfp7078
  جزوه یا کتاب یادگیری ماشین پری ۲۷ ۴۵,۵۳۰ ۲۳ خرداد ۱۳۹۸ ۱۱:۰۴ ق.ظ
آخرین ارسال: dr.a_AI
  حل تشریحی ارشد نظریه زبان ها و ماشین ها ۹۴ تا ۹۷ Sanazzz ۰ ۳,۷۲۸ ۲۰ خرداد ۱۳۹۸ ۰۷:۵۳ ب.ظ
آخرین ارسال: Sanazzz
  دانلود حل المسائل شبکه های عصبی و ماشین های یادگیر نوشته سایمون هایکین ویرایش سوم jazana ۹ ۱۰,۰۸۲ ۱۲ اردیبهشت ۱۳۹۸ ۰۷:۲۹ ب.ظ
آخرین ارسال: Mahtabdel72
  بینایی ماشین F.N.44 ۰ ۲,۰۸۹ ۱۱ فروردین ۱۳۹۸ ۰۳:۴۵ ب.ظ
آخرین ارسال: F.N.44

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close