۱
subtitle
ارسال: #۱
حل تمرین کتاب لینز-بخش ۲-۳
با عرض سلام خدمت تمام دوستان مانشتی
همونطور که می دونیم حل تمرین های کتاب لینز از اهمیت زیادی برای یادگیری مطالب درس نظریه زبان ها و ماشین ها برخورداره.از اونجایی که حل تمرین های این کتاب بصورت یکجا و با زبان شیرین فارسی توی نت وجود نداشت(منکه چیزی نیافتم به غیر از جزوات دستنویس دوستانی که در کلاس های کنکور شرکت می کنند) بر آن شدم که حل تمرین ها ی هر بخش رو بصورت جدا هر کدام در یک تاپیک قرار بدم.
البته قاعدتا به تنهایی از عهده حل تمامی تمارین بر نخواهم آمد.اما نظرم این بوده که با کمک دوستان این سری تاپیک ها رو کامل کنیم.
*توضیح در مورد راه حل ها*
۱- سوالاتی که باید در اون اثبات صورت بگیره فعلا در دستور کار قرار نداره
۲-اگر جوابی احیاناً اشتباه بود با پیام خصوصی لطف کنید اطلاع بدید تا در سریع ترین زمان ممکن اصلاح نمایم.
۳-اینکه در انتهای تاپیک چند ارسال بصورت شماره سوال بعلاوه چند ستاره گذاشته ام(۱۵-***) بخاطر اینه که بعد از ارسال یک پاسخ فوراً نمیشه ارسال جدیدی انجام داد و ارسال های جدید در داخل ارسال قبلی قرار میگیرند.بخاطر همین ارسال ها رو موقتا ایجاد کرده ام.
۴-شاید این مورد خیلی بدیهی باشه ولی خوب شاید هم بکار بیاد چون دوستان به اون اشاره کردند:برای مشاهده جواب بر روی تصویر پیوست شده کلیک کنید تا با کیفیت کامل در صفحه ای جدید نمایش داده بشه.
۵-دوستان لطف کنند جهت تشکر از دکمه مربوطه استفاده کنند تا جواب ها بصورت متوالی بوسیله هر ارسال نمایش داده شود.(جهت پرسیدن سوال و یا انتقاد و پیشنهاد از پیام خصوصی استفاده شود. پیام هایی که احتمال استفاده شون بره در تاپیک قرار داده خواهد شد)
همونطور که می دونیم حل تمرین های کتاب لینز از اهمیت زیادی برای یادگیری مطالب درس نظریه زبان ها و ماشین ها برخورداره.از اونجایی که حل تمرین های این کتاب بصورت یکجا و با زبان شیرین فارسی توی نت وجود نداشت(منکه چیزی نیافتم به غیر از جزوات دستنویس دوستانی که در کلاس های کنکور شرکت می کنند) بر آن شدم که حل تمرین ها ی هر بخش رو بصورت جدا هر کدام در یک تاپیک قرار بدم.
البته قاعدتا به تنهایی از عهده حل تمامی تمارین بر نخواهم آمد.اما نظرم این بوده که با کمک دوستان این سری تاپیک ها رو کامل کنیم.
*توضیح در مورد راه حل ها*
۱- سوالاتی که باید در اون اثبات صورت بگیره فعلا در دستور کار قرار نداره
۲-اگر جوابی احیاناً اشتباه بود با پیام خصوصی لطف کنید اطلاع بدید تا در سریع ترین زمان ممکن اصلاح نمایم.
۳-اینکه در انتهای تاپیک چند ارسال بصورت شماره سوال بعلاوه چند ستاره گذاشته ام(۱۵-***) بخاطر اینه که بعد از ارسال یک پاسخ فوراً نمیشه ارسال جدیدی انجام داد و ارسال های جدید در داخل ارسال قبلی قرار میگیرند.بخاطر همین ارسال ها رو موقتا ایجاد کرده ام.
۴-شاید این مورد خیلی بدیهی باشه ولی خوب شاید هم بکار بیاد چون دوستان به اون اشاره کردند:برای مشاهده جواب بر روی تصویر پیوست شده کلیک کنید تا با کیفیت کامل در صفحه ای جدید نمایش داده بشه.
۵-دوستان لطف کنند جهت تشکر از دکمه مربوطه استفاده کنند تا جواب ها بصورت متوالی بوسیله هر ارسال نمایش داده شود.(جهت پرسیدن سوال و یا انتقاد و پیشنهاد از پیام خصوصی استفاده شود. پیام هایی که احتمال استفاده شون بره در تاپیک قرار داده خواهد شد)
۱
ارسال: #۲
حل تمرین کتاب لینز-بخش ۲-۳
۷-ثابت کنید برای هر nfa مفروض با تعداد وضعیت نهایی دلخواه، یک nfa با تنها یک وضعیت نهایی وجود دارد که برابر هم هستند. آیا این ادعا برای dfa نیز قابل اثبات است؟
جواب قسمت اول: برای nfa کافیست یک وضعیت جدید نهایی ایجاد کرده و سپس هر یک از وضعیت های نهایی را توسط یک رشته تهی([tex]\lambda[/tex]) به وضعیت جدید اتصال دهیم و همچنین آنها را از وضعیت نهایی خارج نمائیم.
جواب قسمت ب: خیر. چرا که برای اینکار به [tex]\lambda[/tex] نیازمندیم که در dfa وجود ندارد.
۸-*****
جواب قسمت اول: برای nfa کافیست یک وضعیت جدید نهایی ایجاد کرده و سپس هر یک از وضعیت های نهایی را توسط یک رشته تهی([tex]\lambda[/tex]) به وضعیت جدید اتصال دهیم و همچنین آنها را از وضعیت نهایی خارج نمائیم.
جواب قسمت ب: خیر. چرا که برای اینکار به [tex]\lambda[/tex] نیازمندیم که در dfa وجود ندارد.
۸-*****
۰
ارسال: #۳
حل تمرین کتاب لینز-بخش ۲-۳
۲-شکل مربوط به nfa تمرین شماره ۱۲ بخش ۲-۲ را به dfa تبدیل کنید.
۰
۰
ارسال: #۵
حل تمرین کتاب لینز-بخش ۲-۳
۴-استدلال مربوط به قضیه ۲-۲ را با دقت بخوانید. به همراه جزئیات نشان دهید که اگر برچسب [tex]\delta_{D} ^{*}\left ( q_{0},w \right )[/tex] شامل [tex]q_{f}[/tex] باشد، آنگاه [tex]\delta _{N}^{*}\left ( q_{0},w \right )[/tex] نیز شامل [tex]q_{f}[/tex] است.
به صورت ریاضی نمی تونم ثابت کنم اما بصورت نظری چیزی که میفهمم رو میگم:
برچسب [tex]\delta ^{*}_{D}\left ( q_{0},w \right )[/tex] شامل [tex]q_{f}[/tex] باشد بدین معنی است که رشته تولید شده در زبان مورد نظر شامل [tex]q_{f}[/tex] باشد. یعنی رشته تولیدی در ماشین متناهی از وضعیت [tex]q_{f}[/tex] عبور میکند. از طرفی میدونیم که تمام وضعیت های ماشین متناهی از روی وضعیت های ماشین نامتناهی ساخته شده لذا حتما رشته ای وجود دارد که از وضعیت [tex]q_{f}[/tex] عبور میکنه.
به صورت ریاضی نمی تونم ثابت کنم اما بصورت نظری چیزی که میفهمم رو میگم:
برچسب [tex]\delta ^{*}_{D}\left ( q_{0},w \right )[/tex] شامل [tex]q_{f}[/tex] باشد بدین معنی است که رشته تولید شده در زبان مورد نظر شامل [tex]q_{f}[/tex] باشد. یعنی رشته تولیدی در ماشین متناهی از وضعیت [tex]q_{f}[/tex] عبور میکند. از طرفی میدونیم که تمام وضعیت های ماشین متناهی از روی وضعیت های ماشین نامتناهی ساخته شده لذا حتما رشته ای وجود دارد که از وضعیت [tex]q_{f}[/tex] عبور میکنه.
-۱
ارسال: #۶
حل تمرین کتاب لینز-بخش ۲-۳
۱-با استفاده از رویه قضیه ۲-۲، nfa مربوط به شکل ۲-۱۰ را به dfa تبدیل کنید.آیا جواب ساده تری نیز میتوانید مستقیماً پیدا کنید؟
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close