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

کاهش 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