صفحه‌ها: ۱ ۲
۱۵ - توصیف ساده ای از زبان تمرین ۱۳ ارائه دهید.
زبان این پذیرنده [tex]L=\left \{ \lambda \right \}[/tex] می باشد. یعنی فقط رشته به طول صفر پذیرفته و در همان وضعیت ابتدایی قرار می گیرد که وضعیت نهایی است.
۱۶ - یک پذیرنده متناهی غیر قطعی بیابید که [tex]\left \{ a \right \}^{*}[/tex] را بپذیرد بطوریکه اگر در گراف انتقال آن یک یال تنها حذف شود (بدون هیچگونه تغییر دیگری)، ماشین بدست آمده [tex]\left \{ a \right \}[/tex] را بپذیرد.
[attachment=8426]
سوال : برای این تمرین آیا میتوان پذیرنده متناهی غیر قطعی ای ساخت که از بین یال ها هر کدام که حذف شود همین نتیجه را بدهد؟
۱۷ - آیا تمرین ۱۶ می تواند با استفاده از یک پذیرنده متناهی قطعی حل شود؟ اگر چنین است،راه حل را ارائه دهید، اگر نیست استدلالاتی قانع کننده برای نتیجه خود ارائه دهید.
جواب : خیر. از آنجائیکه زبان [tex]\left \{ a \right \}^{*}[/tex] شامل [tex]\lambda[/tex] می باشد، با حذف هیچ یالی این رشته از بین نخواهد رفت و لذا با حذف هر کدام از یال های هر ماشین متناهی قطعی ای کماکان این رشته تولید خواهد شد که با خواسته سوال که تولید صرفاً [tex]\left \{ a \right \}[/tex] می باشد متضاد است.
۱۸- تغییرات زیر را برای تعریف ۲-۶ در نظر بگیرید. یک nfa با چندین وضعیت ابتدایی بصورت پنج تایی [tex]M=\left ( Q,\Sigma ,\delta ,Q_{0},F \right )[/tex] تعریف می شود که در آن [tex]Q_{0}\subseteq Q[/tex] مجموعه ای از وضعیت های ابتدایی ممکن است. زبان پذیرفته شده توسط چنین ماشینی بصورت زیر تعیف می شود:
[tex]L\left ( M \right )=\left \{ w:\delta ^{*}\left ( q_{0},w \right ) contains \: q_{f}\: ,\: for \: any \: q_{0}\in Q_{0} \: , \: q_{f}\in F \right \}[/tex]
نشان دهید برای هر nfa با چندین وضعیت ابتدایی یک nfa با یک وضعیت ابتدایی وجود دارد که همان زبان را می پذیرد.
جواب : کافیست یک وضعیت شروع جدید [tex]p_{0}[/tex] تعریف نموده و با یک [tex]\lambda[/tex] به هریک از وضعیت های شروع قبلی وصل نمائیم. همچنین وضعیت های شروع قبلی را از حالت شروع خارج نمائیم.(چراکه حالا در ادامه وضعیت شروع جدید قرار دارند)
[tex]\delta (p_{0},\lambda )=Q_{0}[/tex]
۱۹ - فرض کنید در تمرین ۱۸ محدودیت [tex]Q_{0}\cap F=\varnothing[/tex] را اعمال کنیم. آیا این محدودیت تاثیری در نتیجه دارد؟
جواب : خیر. اینکه با استفاده از یک وضعیت شروع واحد به نقاط شروع قبلی برسیم ارتباطی با این ندارد که آن وضعیت ها پایانی باشند یا خیر.
۲۰ - با استفاده از تعریف ۲-۵ نشان دهید که برای هر nfa رابطه زیر برقرار است:
[tex]\delta ^{*}\left ( q,wv \right )=\bigcup_{p\in \delta ^{*}\left ( q,w \right )} \delta ^{*}\left ( p,v \right )[/tex]
[tex]for \: all \: q \in Q \: and \: all \: w,v \in \Sigma ^{*}[/tex]
تعریف ۲-۵
[tex]for \; an \; nfa , \; the \; extended \; transition \; function \; is \; defined \; so \; that \; \delta ^{*}\left ( q_{i},w \right ) \; contains \\ \; q_{j} \; if \; and \; only \; if \; there \; is \; a \; walk \; in \; the \; transition \; graph \; from \; q_{i} \; to \; q_{j} \; labeled \; w.\\ \; this \; holds \; for \; all \; q_{i},q_{j}\in Q \; and \; w \in \Sigma ^{*}[/tex]
***حل نشده***
۲۱- یک پذیرنده متناهی غیر قطعی (nfa) که الف) دارای هیچ انتقالات [tex]\lambda[/tex] نباشد و ب) برای همه [tex]q \in Q[/tex] و همه [tex]a \in \Sigma[/tex]، [tex]\delta \left ( q,a \right )[/tex] شامل حداکثر یک عنصر باشد، گاهی اوقات یک پذیرنده متناهی قطعی غیرکامل نامیده می شود. این امر معقول است زیرا شرایطی قابل تصور است که هیچ انتخابی جهت حرکت وجود نداشته باشد. برای [tex]\Sigma =\left \{ a,b \right \}[/tex]، پذیرنده متناهی قطعی غیرکامل زیر را به یک پذیرنده متناهی قطعی استاندارد تبدیل کنید.
[attachment=8427]
توضیح : در پذبرنده متناهی قطعی غیرکامل، با توجه به اینکه [tex]\lambda[/tex] و یال تکراری وجود ندارد، لذا جهت تبدیل آن به یک dfa، تنها کاری که لازم است انجام دهیم، تعریف یک تله جهت هدایت یال های تعریف نشده به آن می باشد.
توی حل سوال ۲
شکل ۲-۸
توی جوابش اصلا احتیاج به آوردن b نبود.به هر حال خلاصه ترم میشد. بد نبود یه توضیحم بنویسی تا دیگه بقیه روی اون b ها شک نکنن.
سعی کنید این مباحث رو ادامه ندید و بیشتر تست هایی رو بیارید+نکات مهم کنکوری.البته ناراحت نشیدا. از اون طرف هم خودتون ببینید مباحثش خیلی مبتدی هست.
(۰۷ آذر ۱۳۹۱ ۰۲:۴۹ ب.ظ)hp1361 نوشته شده توسط: ۱۶ - یک پذیرنده متناهی غیر قطعی بیابید که [tex]\left \{ a \right \}^{*}[/tex] را بپذیرد بطوریکه اگر در گراف انتقال آن یک یال تنها حذف شود (بدون هیچگونه تغییر دیگری)، ماشین بدست آمده [tex]\left \{ a \right \}[/tex] را بپذیرد.
سوال : برای این تمرین آیا میتوان پذیرنده متناهی غیر قطعی ای ساخت که از بین یال ها هر کدام که حذف شود همین نتیجه را بدهد؟
با سلام
این ماشین الان لاندا را میپذیرد؟
چون قرار است {a}* را بپذیرد که خوب شامل لاندا هم هست...