۰
subtitle
ارسال: #۱
مینیمال reduction کردن DFA
سلام خدمت دوستان ، یه تاپیک در این مورد بود اما خوب متوجه منظورش نشدم . یه مثال ضمیمه کردم اما تا یه جایی حلش می کنم اما بعدش سوال برام پیش اومده .
مثلا تو این مثال میام تمامی زوج مرتب های dfa رو تشکیل می دیم ، بعد اونایی که یه q به node آخر منتهی میشن و q دیگری به node غیر متناهیوصل میشنو حذف می کنیم ، که من اینکارو انجام دادم .
اما بعد مثلا زوج مرتب q1,q2 باقی مونده ، میام هم q1 رو با الفبا که a هست و هم q2 رو بررسی می کنم که با a به کجا میرن.(تو این مثال q3) اما دیگه نمی دونم چطوری باید زوج مرتبارو قبول کرد یا رد کرد و ایا نیاز این زوج مرتب دوباره با الفبا دیگه مثل b تو ایم مثال چک بشه .؟
ممنون میشم یکم توضیح بدید
با تشکر![[تصویر: 374443_9899a6a9a1843ce5b7f650664f69b68f.jpg]](https://img.manesht.ir/374443_9899a6a9a1843ce5b7f650664f69b68f.jpg)
Sent from my SM-P601 using Tapatalk
مثلا تو این مثال میام تمامی زوج مرتب های dfa رو تشکیل می دیم ، بعد اونایی که یه q به node آخر منتهی میشن و q دیگری به node غیر متناهیوصل میشنو حذف می کنیم ، که من اینکارو انجام دادم .
اما بعد مثلا زوج مرتب q1,q2 باقی مونده ، میام هم q1 رو با الفبا که a هست و هم q2 رو بررسی می کنم که با a به کجا میرن.(تو این مثال q3) اما دیگه نمی دونم چطوری باید زوج مرتبارو قبول کرد یا رد کرد و ایا نیاز این زوج مرتب دوباره با الفبا دیگه مثل b تو ایم مثال چک بشه .؟
ممنون میشم یکم توضیح بدید
با تشکر
Sent from my SM-P601 using Tapatalk
۰
ارسال: #۲
RE: مینیمال reduction کردن DFA
سلام. روشی که من یادمه با این روش متفاوته. اول فرض میکنیم مشابهن و بعد اونها رو جدا میکنیم.
نودها رو به دو دسته پایانی و غیرپایانی تقسیم میکنیم. یک دسته میشه [tex]\{q_1,q_2,q_3\}[/tex] و یک دسته هم میشه [tex]\{q_4,q_5\}[/tex]. اگه اعضای یک مجموعه با یه حرف از الفبا به دو مجموعه مجزا برن باید اونها رو جدا کنیم.
مثلاً به q4 و q5 دقت کنید که هر دوشون با a یا b به مجموعه خودشون میرن. پس میشه اونها رو باهم درنظر گرفت. q1 و q2 هم رفتار مشابه با هم و متفاوت با q3 دارن. پس نیازه که جدا بشن. یک دسته میشه [tex]\{q_1,q_2\}[/tex] و یک دسته هم [tex]\{q_3\}[/tex].
حالا باید دوباره رفتار هر سه دسته رو چک کنیم. میبینیم که اعضای تمام دسته ها رفتار مشابه با هم دارن. پس ماشین سه حالته میشه.
نودها رو به دو دسته پایانی و غیرپایانی تقسیم میکنیم. یک دسته میشه [tex]\{q_1,q_2,q_3\}[/tex] و یک دسته هم میشه [tex]\{q_4,q_5\}[/tex]. اگه اعضای یک مجموعه با یه حرف از الفبا به دو مجموعه مجزا برن باید اونها رو جدا کنیم.
مثلاً به q4 و q5 دقت کنید که هر دوشون با a یا b به مجموعه خودشون میرن. پس میشه اونها رو باهم درنظر گرفت. q1 و q2 هم رفتار مشابه با هم و متفاوت با q3 دارن. پس نیازه که جدا بشن. یک دسته میشه [tex]\{q_1,q_2\}[/tex] و یک دسته هم [tex]\{q_3\}[/tex].
حالا باید دوباره رفتار هر سه دسته رو چک کنیم. میبینیم که اعضای تمام دسته ها رفتار مشابه با هم دارن. پس ماشین سه حالته میشه.
ارسال: #۳
RE: مینیمال reduction کردن DFA
(۰۲ مرداد ۱۳۹۴ ۰۸:۲۹ ق.ظ)Jooybari نوشته شده توسط: سلام. روشی که من یادمه با این روش متفاوته. اول فرض میکنیم مشابهن و بعد اونها رو جدا میکنیم.
نودها رو به دو دسته پایانی و غیرپایانی تقسیم میکنیم. یک دسته میشه [tex]\{q_1,q_2,q_3\}[/tex] و یک دسته هم میشه [tex]\{q_4,q_5\}[/tex]. اگه اعضای یک مجموعه با یه حرف از الفبا به دو مجموعه مجزا برن باید اونها رو جدا کنیم.
مثلاً به q4 و q5 دقت کنید که هر دوشون با a یا b به مجموعه خودشون میرن. پس میشه اونها رو باهم درنظر گرفت. q1 و q2 هم رفتار مشابه با هم و متفاوت با q3 دارن. پس نیازه که جدا بشن. یک دسته میشه [tex]\{q_1,q_2\}[/tex] و یک دسته هم [tex]\{q_3\}[/tex].
حالا باید دوباره رفتار هر سه دسته رو چک کنیم. میبینیم که اعضای تمام دسته ها رفتار مشابه با هم دارن. پس ماشین سه حالته میشه.
این روشی که می فرمایید کاملا درسته اما زمانی که state های اتومات زیاد باشه کار سخت میشه
ارسال: #۴
RE: مینیمال reduction کردن DFA
(۰۴ مرداد ۱۳۹۴ ۰۳:۳۲ ب.ظ)joyebright نوشته شده توسط: این روشی که می فرمایید کاملا درسته اما زمانی که state های اتومات زیاد باشه کار سخت میشه
در مورد روشی که شما عنوان کردید اطلاعی ندارم. مزیت این روش وقتیه که تعداد زیادی state حذف بشن. احتمالاً روشی که شما عنوان کردید کاراییش وقتیه که تعداد کمی state حذف میشن.
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close