با سلام
من در درس نظریه محاسبه خیلی ضعیفم و دلیلش هم این هست که استادم با اینکه خیلی با سواد هستند ولی قدرت تفهیم درس را به من و هم کلاسی هام ندارند.برای همین از شما کمک می خوام.لطفا اگر کسی این سوال را می دونه برام توضیح بده.
منبعی که به ما معرفی شده "مقدمه ای بر نظریه محاسبات" اثر سیپسر هست.
با تشکر
![[تصویر: 405258_OfODP.png]](https://img.manesht.ir/405258_OfODP.png)
(۰۷ خرداد ۱۳۹۵ ۱۱:۴۵ ب.ظ)behnam5670 نوشته شده توسط: سلام
عکس درست ضمیمه نشده. اگر با آپلود تصویر مشکل دارید در سایت‌های آپلود تصویر مثل ۸pic.ir آپلود کنید و لینک تصویر رو اینجا بذارید.
فایل رو الصاق کنید به ارسال. از هیچ سایت سومی استفاده نکنید.
(۰۷ خرداد ۱۳۹۵ ۱۱:۴۵ ب.ظ)behnam5670 نوشته شده توسط: سلام
عکس درست ضمیمه نشده. اگر با آپلود تصویر مشکل دارید در سایت‌های آپلود تصویر مثل ۸pic.ir آپلود کنید و لینک تصویر رو اینجا بذارید.
مشکل برطرف شد.
(۰۷ خرداد ۱۳۹۵ ۱۱:۵۰ ب.ظ)admin نوشته شده توسط:(07 خرداد ۱۳۹۵ ۱۱:۴۵ ب.ظ)behnam5670 نوشته شده توسط: سلام
عکس درست ضمیمه نشده. اگر با آپلود تصویر مشکل دارید در سایت‌های آپلود تصویر مثل ۸pic.ir آپلود کنید و لینک تصویر رو اینجا بذارید.
فایل رو الصاق کنید به ارسال. از هیچ سایت سومی استفاده نکنید.
ابتدا می خواستم همین کار را انجام بدم ولی خطای نوع فایل را می داد.
(۰۷ خرداد ۱۳۹۵ ۱۱:۱۵ ب.ظ)automata01 نوشته شده توسط: با سلامسلام. توی این مدت زمان کم تا امتحان ترم نمیشه کتاب مرجع خوند. شاید بشه یه تیکه هایی ازش رو خوند. جزوه ی دکتر کارگهی توی مانشت هست. اون رو بخونید خیلی خوبه. تورینگ هم خوب توضیح دادن وویسشون هم هست.
من در درس نظریه محاسبه خیلی ضعیفم و دلیلش هم این هست که استادم با اینکه خیلی با سواد هستند ولی قدرت تفهیم درس را به من و هم کلاسی هام ندارند.برای همین از شما کمک می خوام.لطفا اگر کسی این سوال را می دونه برام توضیح بده.
منبعی که به ما معرفی شده "مقدمه ای بر نظریه محاسبات" اثر سیپسر هست.
با تشکر
چند تا رشته امتحان میکنیم. هر رشته روی نوار قرار داره، اطراف رشته بی نهایت فضای خالی یا Blank هست که با B نشون میدن، وسط رشته امکان نداره این فضای خالی وجود داشته باشه. مثلا روی نوار رشته ی ۰۰۰۱۱۰۱۰۰ به صورت …. BBBBBBBB000110100BBBBBB…. هست. حالا، با رسیدن به هر حرف از رشته، یه حرف دیگه مثلا ۰ یا ۱ یا x یا هر چی جاش قرار داده میشه. معمولا رشته ای که انتخاب میشه اول به صورت یه تعدادی ۱ بعد ۰ بعد یه تعدادی ۱ انتخاب میشه. چون خیلی وقتا اون چیزی که ماشین تورینگ بر میگردونه یعنی عملی که روی این رشته انجام میده مثلا ضرب یک های قسمت اول یعنی قبل از صفر در ۱ ها ی قسمت دوم هست. نه لزوماََ البته. هر تابعی ممکنه پیاده سازی بشه توسط ماشین تورینگ.
توی این مسئله گام به گام عملیات رو توضیح میدیم. R حرکت به راست. L حرکت به چپ. B فضای خالی هست بعد و قبل از رشته.
مثلا حرکت ۱ , R <- یک یعنی اگر روی نوار حرف اول از رشته که خوندیم برابر با ۱ بود، به جاش ۱ بذاره، بره راست.
مسئله : توی اولین state هستیم. اگه اول رشته ۰ مشاهده کنیم، جاش X میذاریم میریم راست. حالا رسیدیم به q2 اگه ۰ ببینیم، جاش ۰ میذاریم میریم راست. و به همین صورت ادامه میدیم تا رسیدن به حالت نهایی. و بعد میبینیم چه رشته ای حاصل شده، بعد حدس میزنیم این ماشین تورینگ چه بلایی سر رشته آورده و چی رو محاسبه کرده... ادامه دارد :|
(۰۸ خرداد ۱۳۹۵ ۰۱:۲۲ ق.ظ)pure liveliness نوشته شده توسط:(07 خرداد ۱۳۹۵ ۱۱:۱۵ ب.ظ)automata01 نوشته شده توسط: با سلامسلام. توی این مدت زمان کم تا امتحان ترم نمیشه کتاب مرجع خوند. شاید بشه یه تیکه هایی ازش رو خوند. جزوه ی دکتر کارگهی توی مانشت هست. اون رو بخونید خیلی خوبه. تورینگ هم خوب توضیح دادن وویسشون هم هست.
من در درس نظریه محاسبه خیلی ضعیفم و دلیلش هم این هست که استادم با اینکه خیلی با سواد هستند ولی قدرت تفهیم درس را به من و هم کلاسی هام ندارند.برای همین از شما کمک می خوام.لطفا اگر کسی این سوال را می دونه برام توضیح بده.
منبعی که به ما معرفی شده "مقدمه ای بر نظریه محاسبات" اثر سیپسر هست.
با تشکر
چند تا رشته امتحان میکنیم. هر رشته روی نوار قرار داره، اطراف رشته بی نهایت فضای خالی یا Blank هست که با B نشون میدن، وسط رشته امکان نداره این فضای خالی وجود داشته باشه. مثلا روی نوار رشته ی ۰۰۰۱۱۰۱۰۰ به صورت …. BBBBBBBB000110100BBBBBB…. هست. حالا، با رسیدن به هر حرف از رشته، یه حرف دیگه مثلا ۰ یا ۱ یا x یا هر چی جاش قرار داده میشه. معمولا رشته ای که انتخاب میشه اول به صورت یه تعدادی ۱ بعد ۰ بعد یه تعدادی ۱ انتخاب میشه. چون خیلی وقتا اون چیزی که ماشین تورینگ بر میگردونه یعنی عملی که روی این رشته انجام میده مثلا ضرب یک های قسمت اول یعنی قبل از صفر در ۱ ها ی قسمت دوم هست. نه لزوماََ البته. هر تابعی ممکنه پیاده سازی بشه توسط ماشین تورینگ.
توی این مسئله گام به گام عملیات رو توضیح میدیم. R حرکت به راست. L حرکت به چپ. B فضای خالی هست بعد و قبل از رشته.
مثلا حرکت ۱ , R <- یک یعنی اگر روی نوار حرف اول از رشته که خوندیم برابر با ۱ بود، به جاش ۱ بذاره، بره راست.
مسئله : توی اولین state هستیم. اگه اول رشته ۰ مشاهده کنیم، جاش X میذاریم میریم راست. حالا رسیدیم به q2 اگه ۰ ببینیم، جاش ۰ میذاریم میریم راست. و به همین صورت ادامه میدیم تا رسیدن به حالت نهایی. و بعد میبینیم چه رشته ای حاصل شده، بعد حدس میزنیم این ماشین تورینگ چه بلایی سر رشته آورده و چی رو محاسبه کرده... ادامه دارد :|
خیلی ممنونم
بی صبرانه منتظر ادامه هستم
سلام.
با تشکر از توضیحات خانم pure liveliness، منم نتونستم زبان خوبی برای این ماشین تعریف کنم. بهترین تعریف، بنظرم زبان شامل رشته‌هاییه که حداقل ۲ تا حرف ۱ دارن. روش کار ماشین به این شکله:
اگه حرف اول ۰ بود بجاش x قرار بده و به راست برو. تا زمانی که به B نرسیدی به راست برو. بجای اولین B حرف ۰ رو قرار بده و به چپ برو تا به اولین حرف x در سمت چپ برسی. (یعنی اگه اولین حرف رشته ۰ بود بجاش بنویس x و به آخر رشته ۰ اضافه کن و برگرد به اولین حرف بعد از x.)
اگه ۱ دیدی به راست برو و تا زمانی که ۰ دیدی به راست برو. اگه ۱ دیدی به راست برو و پایان. (یعنی فقط ۲ تا ۱ داشته باشه. فقط رشته رو تغییر میده.)
(۰۹ خرداد ۱۳۹۵ ۰۸:۵۶ ب.ظ)Jooybari نوشته شده توسط: سلام.من توی چند تا رشته به مشکل برخوردم. یه کم هم حالم خوش نبود نتونستم فک کنم. ممنون که جواب نصفه ی من رو کامل کردید دکتر.
با تشکر از توضیحات خانم pure liveliness، منم نتونستم زبان خوبی برای این ماشین تعریف کنم. بهترین تعریف، بنظرم زبان شامل رشته‌هاییه که حداقل ۲ تا حرف ۱ دارن. روش کار ماشین به این شکله:
اگه حرف اول ۰ بود بجاش x قرار بده و به راست برو. تا زمانی که به B نرسیدی به راست برو. بجای اولین B حرف ۰ رو قرار بده و به چپ برو تا به اولین حرف x در سمت چپ برسی. (یعنی اگه اولین حرف رشته ۰ بود بجاش بنویس x و به آخر رشته ۰ اضافه کن و برگرد به اولین حرف بعد از x.)
اگه ۱ دیدی به راست برو و تا زمانی که ۰ دیدی به راست برو. اگه ۱ دیدی به راست برو و پایان. (یعنی فقط ۲ تا ۱ داشته باشه. فقط رشته رو تغییر میده.)
سلام
از ممنونم از همه
فقط یک سوال؟
مگه نباید جواب این سوال مثلا به سبک زیر باشه؟ چطور باید بهش برسیم.
۰+۱*(۱+۰)
اگه سوالم خیلی پیش پا افتادس مسخره ام نکنید
واقعا در نظریه افسیلنم.
[
(۱۰ خرداد ۱۳۹۵ ۰۳:۱۵ ب.ظ)automata01 نوشته شده توسط: سلام
از ممنونم از همه
فقط یک سوال؟
مگه نباید جواب این سوال مثلا به سبک زیر باشه؟ چطور باید بهش برسیم.
۰+۱*(۱+۰)
اگه سوالم خیلی پیش پا افتادس مسخره ام نکنید
واقعا در نظریه افسیلنم.
سلام
در واقع این موضوع به طور کلی صادق نیست که بخواهیم برای زبان هر ماشین تورینگی عبارت منظم بنویسیم
یعنی زبان هر ماشین تورینگی لزوما منظم نیست
اما می توان برای زبان های منظم هم ماشین تورینگ طراحی کرد
پس بعضی از ماشین های تورینگ رو میشه براش عبارت منظم داد (اما نه همشونو)
زبان این ماشین تورینگ در حقیقت همانی است که جناب جویباری فرمودند : رشته ایی که حداقل دوتا ۱ دارند
پس این زبان منظمه (چون براش می شه dfa کشید یا گرامر منظم داد یا عبارت منظم داد )
پس عبارت منظم دارد
و عبارت منظم آن به صورت زیر است:
[tex](0+1)^{\ast}1(0+1)^{\ast}1(0+1)^{\ast}[/tex]
دونکته (که ممکنه بدونید اما حس کردم باید بگم):
- در عبارت منظم علامت "+" به معنای or است
- و در ماشین تورینگ هم برای پذیرش یک رشته لزوما نباید تا انتهای رشته خوانده شود
ممنون از شما