این دو سوال مربوط به فصل دوم کتاب لینزه
تفاوت این دوسوال چیه؟
۱/ ایا برای هر nfaی [tex]M=\left \{ Q,\sum,\delta ,q0,F \right \}[/tex] مکمل L(M معادل مجموعه[tex]\left \{ w=\Sigma ^{*}:\delta ^{*}\left( q0,w \right )\bigcap F=\phi \right \}[/tex] است؟
۲/ایا برای هر nfaی [tex]M=\left \{ Q,\sum,\delta ,q0,F \right \}[/tex] متمم L(M معادل مجموعه زیر است؟
[tex]\left \{ w=\Sigma ^{*}:\delta ^{*}\left( q0,w \right )\bigcap \left( Q-F \right )\neq \phi \right \}[/tex]
معنی هرکدوم چیه؟
این دو سوال چه نکته ای رو میخواد نشون بده؟
ممنون از راهنماییتون
(۰۹ آذر ۱۳۹۰ ۰۶:۳۲ ب.ظ)narges_r نوشته شده توسط: این دو سوال مربوط به فصل دوم کتاب لینزه
تفاوت این دوسوال چیه؟
۱/ ایا برای هر nfaی [tex]M=\left \{ Q,\sum,\delta ,q0,F \right \}[/tex] مکمل L(M معادل مجموعه[tex]\left \{ w=\Sigma ^{*}:\delta ^{*}\left( q0,w \right )\bigcap F=\phi \right \}[/tex] است؟
۲/ایا برای هر nfaی [tex]M=\left \{ Q,\sum,\delta ,q0,F \right \}[/tex] متمم L(M معادل مجموعه زیر است؟
[tex]\left \{ w=\Sigma ^{*}:\delta ^{*}\left( q0,w \right )\bigcap \left( Q-F \right )\neq \phi \right \}[/tex]
معنی هرکدوم چیه؟
این دو سوال چه نکته ای رو میخواد نشون بده؟
ممنون از راهنماییتون
نرگس خانم من منظوره این عباراتو میگم. تجزیه و تحلیل و پیاده سازیش روی ماشین با خودتون.
۱- عبارت اول میگه << در هر ماشین Nfa اگر رشته w در زبان (L(M با شروع از وضعیت q0 به یک وضعیت نهایی بره و رشته تموم بشه, رشته w مطمئنا جز زبانه [tex]\bar{L}(M)[/tex] نیست.>> ولی این حرف الزاما به این معنا نیست که در هر ماشین Nfa اگر رشته w در زبان (L(M با شروع از وضعیت q0 به یک وضعیت غیر نهایی بره و رشته تموم بشه, رشته w جز زبانه [tex]\bar{L}(M)[/tex] هست.
۲- عبارت دوم میگه<< در هر ماشین Nfa اگر رشته w در زبان (L(M با شروع از وضعیت q0 به یک وضعیت غیر نهایی بره و رشته تموم بشه, رشته w الزاما جز زبانه [tex]\bar{L}(M)[/tex] هست.>> که این اشتباه است.
از اینجا میشه نتیجه گرفت که با تبدیل وضعیت های غیر پایانی به پایانی و پایانی به غیر پایانی نمیشه متمم یک nfa ساخت
درسته؟؟؟
(۰۹ آذر ۱۳۹۰ ۰۸:۵۳ ب.ظ)narges_r نوشته شده توسط: از اینجا میشه نتیجه گرفت که با تبدیل وضعیت های غیر پایانی به پایانی و پایانی به غیر پایانی نمیشه متمم یک nfa ساخت
درسته؟؟؟
این دو عبارت در مورد پذیرش یک رشته در متمم یک ماشینه nfa صحبت میکنن, نه در مورد ساخت یک ماشین متمم.
این نتیجه گیری رو نمیشه کرد.
دیگه کسی نظری نداشت؟؟؟
کسی نظریه نمیخونه؟؟!! دیگه کسی نظری نداشت؟
اصلا یکی لطفا توضیح بده متمم nfa چجوری ساخته میشه؟
(۱۰ آذر ۱۳۹۰ ۰۹:۲۹ ب.ظ)narges_r نوشته شده توسط: کسی نظریه نمیخونه؟؟!! دیگه کسی نظری نداشت؟
اصلا یکی لطفا توضیح بده متمم nfa چجوری ساخته میشه؟
nfa رو تبدیل به dfa کن بعد تمام گره های پایانی رو به غیر پایانی و تمام گره های غیر پایانی رو به پایانی تبدیل کن.
(۱۰ آذر ۱۳۹۰ ۱۰:۲۲ ب.ظ)sasanlive نوشته شده توسط:(10 آذر ۱۳۹۰ ۰۹:۲۹ ب.ظ)narges_r نوشته شده توسط: کسی نظریه نمیخونه؟؟!! دیگه کسی نظری نداشت؟
اصلا یکی لطفا توضیح بده متمم nfa چجوری ساخته میشه؟
nfa رو تبدیل به dfa کن بعد تمام گره های پایانی رو به غیر پایانی و تمام گره های غیر پایانی رو به پایانی تبدیل کن.
ممنون از پاسخهاتون...
نکته ای که این تمرین میرسونه اینه که نمیشه متمم nfa رو مثل متمم Dfa بدست آورد . تعریف متمم nfa اولی میگه متمم nfa شامل رشته هایی میشه که که با حالت شروع به پایان رشته برسیم و در حالات پایانی نباشیم یعنی ممکنه توی حالتی باشیم که nfa در اون حالت تعریف نشده باشه پس تعریف ماشین دومی برای متمم nfa درست نیست چون این تعریف میگه که فقط در حالت های غیر پایانی موجود ماشین باشیم و حالت های تعریف نشده رو در نظر نمی گیره.
(۰۹ آذر ۱۳۹۰ ۰۸:۵۳ ب.ظ)narges_r نوشته شده توسط: از اینجا میشه نتیجه گرفت که با تبدیل وضعیت های غیر پایانی به پایانی و پایانی به غیر پایانی نمیشه متمم یک nfa ساختبله دقیقا( البته به نظر من:cool
درسته؟؟؟
همین نتیجه رو میرسونه که نباید مثل پیدا کردن متمم dfa عمل کرد.
(۱۱ آذر ۱۳۹۰ ۰۲:۱۳ ب.ظ)ahmadnouri نوشته شده توسط: نکته ای که این تمرین میرسونه اینه که نمیشه متمم nfa رو مثل متمم Dfa بدست آورد . تعریف متمم nfa اولی میگه متمم nfa شامل رشته هایی میشه که که با حالت شروع به پایان رشته برسیم و در حالات پایانی نباشیم یعنی ممکنه توی حالتی باشیم که nfa در اون حالت تعریف نشده باشه پس تعریف ماشین دومی برای متمم nfa درست نیست چون این تعریف میگه که فقط در حالت های غیر پایانی موجود ماشین باشیم و حالت های تعریف نشده رو در نظر نمی گیره.
(۰۹ آذر ۱۳۹۰ ۰۸:۵۳ ب.ظ)narges_r نوشته شده توسط: از اینجا میشه نتیجه گرفت که با تبدیل وضعیت های غیر پایانی به پایانی و پایانی به غیر پایانی نمیشه متمم یک nfa ساختبله دقیقا( البته به نظر من:cool
درسته؟؟؟
درست میگید . برای یافتن متمم nfa روال کلی نداریم پس از تبدیل nfa به dfa استفاده میکنیم.
من یه حل تمرین دست نویس از نظریه رو اینترنت پیدا کردم که این نکته رو دقیقاً توی تمرینات آقای لینز به کار برده.
برای پیدا کردن متمم یک nfa نمیشه حالتای پایانی رو به غیر پایانی تغییر داد و باید اول nfa رو به dfa تبدیل کرد و بعد این کارو انجام داد. توی این جزوه دستنویسه اول راه اول رو رفته و بعد روش خط کشیده و بعد درستش کرده و گفته که تبدیل مستقیم اشتباهه...!