صفحه‌ها: ۱ ۲
با عرض سلام خدمت تمام دوستان مانشتی
همونطور که می دونیم حل تمرین های کتاب لینز از اهمیت زیادی برای یادگیری مطالب درس نظریه زبان ها و ماشین ها برخورداره.از اونجایی که حل تمرین های این کتاب بصورت یکجا و با زبان شیرین فارسی توی نت وجود نداشت(منکه چیزی نیافتم به غیر از جزوات دستنویس دوستانی که در کلاس های کنکور شرکت می کنند) بر آن شدم که حل تمرین ها ی هر بخش رو بصورت جدا هر کدام در یک تاپیک قرار بدم.
البته قاعدتا به تنهایی از عهده حل تمامی تمارین بر نخواهم آمد.اما نظرم این بوده که با کمک دوستان این سری تاپیک ها رو کامل کنیم.
*توضیح در مورد راه حل ها*
۱- سوالاتی که باید در اون اثبات صورت بگیره فعلا در دستور کار قرار نداره
۲-اگر جوابی احیاناً اشتباه بود با پیام خصوصی لطف کنید اطلاع بدید تا در سریع ترین زمان ممکن اصلاح نمایم.
۳-اینکه در انتهای تاپیک چند ارسال بصورت شماره سوال بعلاوه چند ستاره گذاشته ام(۱۵-***) بخاطر اینه که بعد از ارسال یک پاسخ فوراً نمیشه ارسال جدیدی انجام داد و ارسال های جدید در داخل ارسال قبلی قرار میگیرند.بخاطر همین ارسال ها رو موقتا ایجاد کرده ام.
۴-شاید این مورد خیلی بدیهی باشه ولی خوب شاید هم بکار بیاد چون دوستان به اون اشاره کردند:برای مشاهده جواب بر روی تصویر پیوست شده کلیک کنید تا با کیفیت کامل در صفحه ای جدید نمایش داده بشه.
۵-دوستان لطف کنند جهت تشکر از دکمه مربوطه استفاده کنند تا جواب ها بصورت متوالی بوسیله هر ارسال نمایش داده شود.(جهت پرسیدن سوال و یا انتقاد و پیشنهاد از پیام خصوصی استفاده شود. پیام هایی که احتمال استفاده شون بره در تاپیک قرار داده خواهد شد)
سوالات
۱- با تمام جزئیات، ادعای عنوان شده در بخش قبلی را ثابت کنید که اگر در یک گراف انتقال راهی با برچسب w وجود داشته باشد، آنگاه باید راهی با برچسب w با طول نابیشتر از[tex]\Lambda \left ( 1 \Lambda \right )\left | w \right |[/tex] موجود باشد.
***حل نشده***
۲- یک پذیرنده متناهی قطعی بیابید که زبان تعریف شده بوسیله پذیرنده متناهی غیر قطعی در شکل ۲-۸ را بپذیرد.
شکل ۲-۸
[attachment=8288]
جواب
[attachment=8289]
۳- یک پذیرنده متناهی قطعی بیابید که مکمل زبان تعریف شده بوسیله پذیرنده متناهی غیر قطعی در شکل ۲-۸ را بپذیرد.
شکل ۲-۸
[attachment=8247]
جواب
[attachment=8412]
۴ -در شکل ۲-۹ توابع [tex]\delta ^{*}\left ( q_{0},1011 \right )[/tex] و [tex]\delta ^{*}\left ( q_{1},01 \right )[/tex] را بیابید.
شکل ۲-۹
[attachment=8248]
جواب الف
[attachment=8249]
جواب ب
[attachment=8250]
۵-در شکل ۲-۱۰، [tex]\delta ^{*}\left ( q_{0},a \right )[/tex] و [tex]\delta ^{*}\left ( q_{1},\lambda \right )[/tex] را بیابید.
[attachment=8290]
[attachment=8413]
[attachment=8414]
۶-برای پذیرنده متناهی غیرقطعی در شکل ۲-۹، [tex]\delta ^{*}\left ( q_{0},1010 \right )[/tex] و [tex]\delta ^{*}\left ( q_{1},00 \right )[/tex] را بیابید.
الف)
[attachment=8415]
ب) [tex]\delta ^{*}(q_{0},00)=\varnothing[/tex]
۷- یک پذیرنده متناهی غیرقطعی با حداکثر پنج حالت برای مجموعه [tex]\left \{ abab^{n}:n\geqslant 0 \right \}\cup \left \{ aba^{n}:n\geqslant 0 \right \}[/tex] طراحی کنید.
[attachment=8416]
۸-یک پذیرنده متناهی غیرقطعی با سه حالت بسازید که زبان [tex]\left \{ ab,abc \right \}^{*}[/tex] را بپذیرد.
[attachment=8417]
۹- آیا فکر میکنید تمرین ۸ میتواند با کمتر از ۳ حالت حل شود؟
خیر. از آنجایی که الفبای ما شامل ۳ عضو است، جهت تولید این زبان حداقل به ۳ حالت متمایز نیاز است.
(۰۶ آذر ۱۳۹۱ ۰۳:۵۴ ب.ظ)hp1361 نوشته شده توسط: ۱۰-یک پذیرنده متناهی غیرقطعی با چهارحالت برای [tex]L=\left \{ a^{n}:n\geq 0 \right \}\cup \left \{ b^{n}a:n\geq 1 \right \}[/tex] بیابید.دوست عزیزم ممنون که وقت میزاری و این تصاویر با کیفیت رو میزاری برا بچه ها
۱۱-****
من فایرفاکسم خطا میداد اکسپشن و نشون نمیداد تصاویر رو
تنظیمش کردم الان نشون میده ممنون پیام دادین همینطور ممنونم از eternal عزیز که ایشون هم نکته شما رو گفتن مرسی عالی بودند تصاویر
۱۰-الف)یک پذیرنده متناهی غیرقطعی با سه حالت بیابید که زبان [tex]L= \left \{ a^{n}:n\geq 1 \right \}\cup \left \{ b^{m}a^{k}:m\geq 0,k\geq0 \right \}[/tex] را بپذیرد.
[attachment=8418]
ب)آیا فکر میکنید که زبان بخش الف می تواند بوسیله یک پذیرنده متناهی غیرقطعی با کمتر از سه حالت پذیرفته شود؟
پاسخ: بله. زبان [tex]\left \{ a^{n}:n\geq 1 \right \}[/tex] درون زبان [tex]\left \{ b^{m}a^{k}:m,k\geq 0 \right \}[/tex] وجود دارد.
[attachment=8419]
۱۱-یک پذیرنده متناهی غیرقطعی با چهارحالت برای [tex]L=\left \{ a^{n}:n\geq 0 \right \}\cup \left \{ b^{n}a:n\geq 1 \right \}[/tex] بیابید.
[attachment=8420]
۱۲ -کدامیک از رشته های ۰۰، ۰۱۰۰۱، ۱۰۰۱۰، ۰۰۰، ۰۰۰۰ بوسیله پذیرنده متناهی قطعی زیر پذیرفته می شود؟
[attachment=8421]
سوال : زبان پذیرفته شده توسط این ماشین چیست؟
۱۳ - مکمل زبان پذیرفته شده بوسیله پذیرنده متناهی غیر قطعی در شکل ۲-۱۰ چیست ؟
[attachment=8422]
۱۴ - فرض کنید [tex]L[/tex] زبان پذیرفته شده بوسیله پذیرنده متناهی غیر قطعی در شکل ۲-۸ باشد. یک پذیرنده متناهی غیر قطعی بیابید که [tex]L \cup \left \{ a^{5} \right \}[/tex] را بپذیرد.
[attachment=8425]
سوال : پذیرنده متناهی قطعی این زبان را رسم کنید.