زمان کنونی: ۰۹ فروردین ۱۴۰۳, ۰۸:۰۲ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

متمم nfa

ارسال:
  

narges_r پرسیده:

متمم nfa

این دو سوال مربوط به فصل دوم کتاب لینزه
تفاوت این دوسوال چیه؟
۱/ ایا برای هر 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]

معنی هرکدوم چیه؟
این دو سوال چه نکته ای رو میخواد نشون بده؟

ممنون از راهنماییتون

۰
ارسال:
  

sasanlive پاسخ داده:

RE: متمم nfa

(۰۹ آذر ۱۳۹۰ ۰۶:۳۲ ب.ظ)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] هست.>> که این اشتباه است.

۰
ارسال:
  

narges_r پاسخ داده:

متمم nfa

از اینجا میشه نتیجه گرفت که با تبدیل وضعیت های غیر پایانی به پایانی و پایانی به غیر پایانی نمیشه متمم یک nfa ساخت
درسته؟؟؟

ارسال:
  

sasanlive پاسخ داده:

RE: متمم nfa

(۰۹ آذر ۱۳۹۰ ۰۸:۵۳ ب.ظ)narges_r نوشته شده توسط:  از اینجا میشه نتیجه گرفت که با تبدیل وضعیت های غیر پایانی به پایانی و پایانی به غیر پایانی نمیشه متمم یک nfa ساخت
درسته؟؟؟

این دو عبارت در مورد پذیرش یک رشته در متمم یک ماشینه nfa صحبت میکنن, نه در مورد ساخت یک ماشین متمم.
این نتیجه گیری رو نمیشه کرد.
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

narges_r پاسخ داده:

متمم nfa

دیگه کسی نظری نداشت؟؟؟

۰
ارسال:
  

narges_r پاسخ داده:

متمم nfa

کسی نظریه نمیخونه؟؟!! دیگه کسی نظری نداشت؟
اصلا یکی لطفا توضیح بده متمم nfa چجوری ساخته میشه؟

ارسال:
  

sasanlive پاسخ داده:

RE: متمم nfa

(۱۰ آذر ۱۳۹۰ ۰۹:۲۹ ب.ظ)narges_r نوشته شده توسط:  کسی نظریه نمیخونه؟؟!! دیگه کسی نظری نداشت؟
اصلا یکی لطفا توضیح بده متمم nfa چجوری ساخته میشه؟

nfa رو تبدیل به dfa کن بعد تمام گره های پایانی رو به غیر پایانی و تمام گره های غیر پایانی رو به پایانی تبدیل کن.
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

ahmadnouri پاسخ داده:

متمم nfa

نکته ای که این تمرین میرسونه اینه که نمیشه متمم nfa رو مثل متمم Dfa بدست آورد . تعریف متمم nfa اولی میگه متمم nfa شامل رشته هایی میشه که که با حالت شروع به پایان رشته برسیم و در حالات پایانی نباشیم یعنی ممکنه توی حالتی باشیم که nfa در اون حالت تعریف نشده باشه پس تعریف ماشین دومی برای متمم nfa درست نیست چون این تعریف میگه که فقط در حالت های غیر پایانی موجود ماشین باشیم و حالت های تعریف نشده رو در نظر نمی گیره.

(۰۹ آذر ۱۳۹۰ ۰۸:۵۳ ب.ظ)narges_r نوشته شده توسط:  از اینجا میشه نتیجه گرفت که با تبدیل وضعیت های غیر پایانی به پایانی و پایانی به غیر پایانی نمیشه متمم یک nfa ساخت
درسته؟؟؟
بله دقیقا( البته به نظر من:cool Smileهمین نتیجه رو میرسونه که نباید مثل پیدا کردن متمم dfa عمل کرد.

ارسال:
  

Masoud05 پاسخ داده:

RE: متمم nfa

(۱۱ آذر ۱۳۹۰ ۰۲:۱۳ ب.ظ)ahmadnouri نوشته شده توسط:  نکته ای که این تمرین میرسونه اینه که نمیشه متمم nfa رو مثل متمم Dfa بدست آورد . تعریف متمم nfa اولی میگه متمم nfa شامل رشته هایی میشه که که با حالت شروع به پایان رشته برسیم و در حالات پایانی نباشیم یعنی ممکنه توی حالتی باشیم که nfa در اون حالت تعریف نشده باشه پس تعریف ماشین دومی برای متمم nfa درست نیست چون این تعریف میگه که فقط در حالت های غیر پایانی موجود ماشین باشیم و حالت های تعریف نشده رو در نظر نمی گیره.

(۰۹ آذر ۱۳۹۰ ۰۸:۵۳ ب.ظ)narges_r نوشته شده توسط:  از اینجا میشه نتیجه گرفت که با تبدیل وضعیت های غیر پایانی به پایانی و پایانی به غیر پایانی نمیشه متمم یک nfa ساخت
درسته؟؟؟
بله دقیقا( البته به نظر من:cool Smileهمین نتیجه رو میرسونه که نباید مثل پیدا کردن متمم dfa عمل کرد.

درست میگید . برای یافتن متمم nfa روال کلی نداریم پس از تبدیل nfa به dfa استفاده میکنیم.
یافتن تمامی ارسال‌های این کاربر

۰
ارسال: #۱۰
  

variant20002000 پاسخ داده:

متمم nfa

من یه حل تمرین دست نویس از نظریه رو اینترنت پیدا کردم که این نکته رو دقیقاً توی تمرینات آقای لینز به کار برده.
برای پیدا کردن متمم یک nfa نمیشه حالتای پایانی رو به غیر پایانی تغییر داد و باید اول nfa رو به dfa تبدیل کرد و بعد این کارو انجام داد. توی این جزوه دستنویسه اول راه اول رو رفته و بعد روش خط کشیده و بعد درستش کرده و گفته که تبدیل مستقیم اشتباهه...!



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  تعداد حالات نهایی nfa برای زبان دارای لاندا و فاقد لاندا pooyaa ۲ ۳,۰۹۹ ۰۶ بهمن ۱۳۹۳ ۰۶:۵۳ ب.ظ
آخرین ارسال: pooyaa
  تعریف رسمی زبانی که توسط nfa پذیرفته نمیشود pooyaa ۲ ۱,۸۵۸ ۰۳ بهمن ۱۳۹۳ ۰۲:۴۲ ق.ظ
آخرین ارسال: pooyaa
  تبدیل nfa به dfa alirezafchh ۱ ۲,۱۵۵ ۰۸ دى ۱۳۹۳ ۱۲:۴۷ ق.ظ
آخرین ارسال: fatemeh69
  نقطه شروع در تبدیل NFA به DFA kingmax ۵ ۳,۷۵۶ ۰۵ دى ۱۳۹۳ ۰۳:۰۲ ق.ظ
آخرین ارسال: Jooybari
  سوال از تبدیل nfa به عبارت منظم arefeh.hp ۱ ۳,۳۸۵ ۱۳ آذر ۱۳۹۳ ۰۸:۱۸ ب.ظ
آخرین ارسال: Jooybari
Question توضیح شیوه تبدیل NFA به DFA براساس این شکل s_t_6 ۲ ۱۵,۲۱۷ ۲۴ مرداد ۱۳۹۳ ۱۲:۳۵ ب.ظ
آخرین ارسال: fatemeh69
Exclamation پیاده سازی تبدیل NFA به DFA kimiya_ab ۲ ۲,۳۵۳ ۱۹ مرداد ۱۳۹۳ ۰۲:۴۰ ب.ظ
آخرین ارسال: Riemann
  سوال در مورد تبدیل NFA به DFA sipser ۶ ۵,۲۹۵ ۲۲ خرداد ۱۳۹۳ ۰۹:۴۹ ب.ظ
آخرین ارسال: sipser
  سوال - تبدیل عبارت regExp به NFA sipser ۳ ۲,۶۴۵ ۲۲ خرداد ۱۳۹۳ ۰۷:۳۷ ب.ظ
آخرین ارسال: Jooybari
  حداقل تعداد حالات nfa joyebright ۳ ۱,۹۸۲ ۲۰ خرداد ۱۳۹۳ ۰۳:۴۸ ق.ظ
آخرین ارسال: Jooybari

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close