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

کاهش dfa

ارسال:
  

payman84ce پرسیده:

کاهش dfa

سلام کاهش dfa به روش پلکانی چطوریه؟
ممنون

۰
ارسال:
  

hkarimi پاسخ داده:

کاهش dfa

سلام.
والا منم این اسمو نشنیدم ولی الان یه روش خوب رو برات تشریح میکنم.
این کار چنتا مرحله داره که به شرح زیرن:
۱/ تمام وضعیت های غیر قابل دسترس رو حذف کن. مثلا از q0 هیچ جور نمیتونی به q5 برسی. پس راحت با یه خط بترکونش و از صفحه کاغذ محوش کن.
۲/ به ازای هر Qi و Qj که توی گراف وجود داره زوج مرتب های (Qi,Qj( رو تشکیل بده. مثلا اگه گراف ۴ تا وضعیت داره (از Q0 تا Q3) شما باید Q0,Q1 و Q0,Q2 و Q0,Q3 و Q1,Q2 و Q1,Q3 و Q2,Q3 رو یه گوشه بنویسی. با یکم دقت و یه بار امتحان این روش میبینی که تعداد این حالتای دوتایی ترکیب n از ۲ه. (که مهم نیس. یعنی ربطی به کارمون نداره)
۳/ از این وضعیت های لیست شده(مثلا Q0,Q3) اونایی که یکیشون پایانی(مثلا Q3) و دیگری پایانی نیس (مثلا Q0) رو به سادگی هرچه تمام‌تر حذف میکنیم. گرفتی؟ یعنی بعد از لیست کردن اون زوج مرتبا میری تو گراف نگا میکنی، اگه یکی از وضعیتای زوج مرتب نهایی و یکی دیگش نهایی نبود حذفش میکنی.
*******"تذکر": اگه هر دوتا عنصر زوج مرتب پایانی بودن اون زوج مرتبه رو حذفش نمیکنی. خیلی مهمه‌ها *******
این مرحله‌ی ۳ رو واسه همه‌ی زوج مرتبا انجام بده.
مهم. به دققققت بخونش ۴/ به ازای هر زوج مرتب Qi,Qj که تا الان حذف نشده‌، به ازای تمام حروف الفبا‌، خروجی های هر عنصر از این زوج مرتب رو ب دست بیار. یعنی مثلا Q0,Q1 (که تا اینجا حذف نشده) نگا کن ببین از Q0 و ۰ به کدوم وضضعیت میریم. Q0 و ۱ هم نگا کن . واسه Q1 هم همین کارو انجام بده. خب، حالا اگه با Q0 و ۰ رسیدیم به یه وضعیت غیر پایانی ولی با Q1 رسیدیم به یه وضعیت پایانی، این زوج مرتب هم خط میزنیم. Q0 و ۱ , Q1 و۱ رو هم امتحان میکنیم. دقت کن که اگه هر دوتای Q0 و Q1 به ۰ میرسیدن به نود پایانی خط نمیخوره ها.
۵/ مرحله قبل رو واسه همه زوج مرتبا تکرار کن. تمومه.هر چی زوج مرتب باقی موندن ادغام پذیر هستن. مثلا Q0 و Q2 ادغام پذیرن. تو گراف جدید که میکشی این دوتا وضعیت رو تو یه دایره بکش. آفرین، تو تونستی کاهش وضعیت رو اعمال کنی
در کل این روش خیلی ساده و مختصره ولی من بخاطر اینکه مجبور بودم همراه توضیحاتم مثالم بیارم خیلی طولانی شد.
امیدوارم بفهمی چی گفتم
ببخشید. نوشتم ترکیب n از دو که درستش ۲ از nه یعنی همون فرمول C(n,2)

۰
ارسال:
  

mfXpert پاسخ داده:

کاهش dfa

تو مدار منطقی فصل مربوط به طراحی مدارات سنکرون و آسنکرون یه روشی وجود داره که توش از جدول ادغام استفاده میشه تا تعداد حالات یک مدار رو مینیمم کرد.از این جدول ادغام خیلی راحت میشه برای مینیمم کردن تعداد حالات یک DFA هم استفاده کرد(جدول ادغام به صورت پلکانی رسم میشه و احتمالا به همین دلیله که بهش جدول پلکانی هم میگن)



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  اعتراض به سیستم سنجش در خصوص کاهش ظرفیت های ارشد نرم افزار و آیتی Happiness.72 ۲ ۳,۱۲۳ ۰۶ تیر ۱۳۹۷ ۱۱:۰۲ ق.ظ
آخرین ارسال: Happiness.72
  کاهش شدید احتمالی رتبه های قبولی در شبکه و امنیت سال در آیتی ۹۶ alilash ۵ ۳,۴۱۲ ۱۸ خرداد ۱۳۹۶ ۱۱:۲۴ ب.ظ
آخرین ارسال: alilash
  کاهش میزان تلفات در ارسال مالتی مدیا mehran.hzd ۰ ۱,۴۷۷ ۰۷ خرداد ۱۳۹۶ ۰۲:۵۸ ب.ظ
آخرین ارسال: mehran.hzd
  کاهش میزان تلفات در ارسال مالتی مدیا mehran.hzd ۰ ۱,۵۴۹ ۰۷ خرداد ۱۳۹۶ ۰۲:۵۵ ب.ظ
آخرین ارسال: mehran.hzd
  کاهش پذیری چند جمله ای *tarannom* ۲ ۲,۱۶۹ ۰۵ اردیبهشت ۱۳۹۶ ۰۹:۰۸ ب.ظ
آخرین ارسال: *tarannom*
  کاهش کارایی یک کامپیوتر با دستورات انشعاب شرطی Doctorwho ۲ ۱,۷۵۰ ۱۸ دى ۱۳۹۵ ۰۵:۴۴ ب.ظ
آخرین ارسال: boshbosh
  رسم dfa برای زبان زیر (تمرین ۶ کتاب لینز فصل دوم ) MBe ۱۰ ۸,۰۰۹ ۲۳ آبان ۱۳۹۵ ۱۲:۲۷ ق.ظ
آخرین ارسال: signal_micro
Video سمت چپ هر FD کاهش ناپذیر باشد یعنی چه؟ post98 ۱ ۱,۵۰۸ ۲۳ خرداد ۱۳۹۵ ۰۸:۱۷ ب.ظ
آخرین ارسال: Iranian Wizard
  DFA amir777 ۱ ۱,۱۳۶ ۱۷ دى ۱۳۹۴ ۰۱:۰۵ ق.ظ
آخرین ارسال: gunnersregister
  Dfa سوال پنجم فصل چهارم پوران Baranmalihe ۱ ۱,۳۶۹ ۱۰ دى ۱۳۹۴ ۱۲:۰۰ ق.ظ
آخرین ارسال: Jooybari

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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