معکوس و متمم یک DFA چه تفاوتنی دارن؟..
سه تا هم سوال سراسری ۸۹ و ۸۸هست که پاک آدمو گیج میکنه؟
لطفا هر کی کامل بلده یه توضیحی بده....
(۲۷ مهر ۱۳۹۰ ۰۷:۲۰ ب.ظ)deledivouneh نوشته شده توسط: معکوس و متمم یک DFA چه تفاوتنی دارن؟..اگر DFA زبان L رو بپذیره، با تبدیل حالت(یا حالت های پایانی) به حالت شروع و بالعکس و همچنین معکوس کردن جهت یالها می تونیم ماشینی ایجاد کنیم که [tex]L^{R}[/tex] رو بپذیره
اگر DFA زبان L رو بپذیره، می تونیم با تبدیل حالات پایانی به غیر پایانی و بالعکس کاری کنیم تا ماشین حاصل زبان [tex]\bar{L}[/tex] رو بپذیره
اگر DFA زبان L رو بپذیره، با تبدیل حالت(یا حالت های پایانی) به حالت شروع و بالعکس و همچنین معکوس کردن جهت یالها می تونیم ماشینی ایجاد کنیم که [tex]L^{R}[/tex] رو بپذیره
یعنی میتونیم چند حالت آغازی داشته باشیم؟؟؟
(۲۸ مهر ۱۳۹۰ ۰۳:۵۲ ب.ظ)shadi نوشته شده توسط: یعنی میتونیم چند حالت آغازی داشته باشیم؟؟؟بله. یک ماشین NFA میتونه دارای چندین حالت شروع باشه.البته تعریف NFA چنین اجازه ای رو نمیده اما تو بعضی کتابا چنین چیزی وجود داره
(۲۸ مهر ۱۳۹۰ ۰۳:۵۲ ب.ظ)shadi نوشته شده توسط: اگر DFA زبان L رو بپذیره، با تبدیل حالت(یا حالت های پایانی) به حالت شروع و بالعکس و همچنین معکوس کردن جهت یالها می تونیم ماشینی ایجاد کنیم که [tex]L^{R}[/tex] رو بپذیره
یعنی میتونیم چند حالت آغازی داشته باشیم؟؟؟
ضمن تشکرmfXpert
فکر میکنم اگه چند حالت فاینال داشته باشیم اول تبدیل میکنیم به یک حالت
((واسه همین معکوس L رو میتونیم از روی NFA یدست بیاریم ولی واسه نات L باید حتما ماشین DFA باشه بعد اون روال رو انجام بدیم))
ماشین حاصل از الگوریتم معکوس کردن ممکنه دیگه DFA نباشه.پس اگر نیاز باشه باید ماشین حاصل رو با اعمال الگوریتم تبدیل NFA به DFA دوباره به یک DFA تبدیل کرد.
۶۲ که یه طورایی تکلیفش مشخص هست و چیز زیاد خاصی نیست
۶۳:
۱و۳) غلطه چون قرار نیست از لم تزریق برای اثبات منظم بودن استفاده کنیم
۲) درسته شما k رو بگیر تغداد stateهات یا هر ضریبی از اونا خوب؟ اگه یه رشته پذیرش شد که طولش از تعداد stateهات بیشتر بود خیلی واضح هست که میشه یه رشته داشت که غضو L باشه و از این k کوچکتر.
۶۱-گزینه ۲: یه فرمول هست واسه تفاضل که از روی اشتراک زبان اول با متمم زبان دوم بدست میاد تو کتاب لینز هستش.
نکته سوال اینه که برای متمم گیری باید حتما به صورت معین عمل بشه این dهایی رو هم که نوشته منظور همون deterministic بودن هست. این یه نکته
نکته بعدی متمم شدن فرمول معادل تفاضل هست. یعنی ما می تونیم زبان و اشتراک رو به صورت متمم بنویسیم و بعد از کل عبارت متمم بگیریم که میشه همون فرمول اولیه.
امیدوارم گرفته باشی چی میگم حس فرمول نویسی نبود!