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

شمارش تعداد state های ماشین DFA

ارسال:
  

mostafa2012 پرسیده:

شمارش تعداد state های ماشین DFA

سلام
ببخشید من توی این مبحث خیلی ضعف دارم چیکار کنم (تواین مدت باقیمانده؟؟؟؟) اصولا همه اش اشتباه مزنم...(الان زدم ۱ میگه ۲!)

[تصویر:  327419_3iqandw8gsu7lce8ceum.png]

۳
ارسال:
  

Jooybari پاسخ داده:

RE: شمارش تعداد state های ماشین DFA

سلام. گزینه ۲ میشه سیکما استار که یک حالت داره. گزینه ۱ سه حالتیه.

ارسال:
  

mostafa2012 پاسخ داده:

RE: شمارش تعداد state های ماشین DFA

(۲۷ دى ۱۳۹۳ ۰۴:۳۹ ق.ظ)Jooybari نوشته شده توسط:  سلام. گزینه ۲ میشه سیکما استار که یک حالت داره. گزینه ۱ سه حالتیه.

باسلام
خیلی ممنون از اینکه جواب سوال را با تشریح کامل دادید!Dodgy

اگر امکان داره به سوالی که پرسیدم نیز جواب دهید باتشکر!Undecided
Big GrinConfused
یافتن تمامی ارسال‌های این کاربر

ارسال:
  

mostafa2012 پاسخ داده:

RE: شمارش تعداد state های ماشین DFA

(۲۷ دى ۱۳۹۳ ۰۴:۳۹ ق.ظ)Jooybari نوشته شده توسط:  سلام. گزینه ۲ میشه سیکما استار که یک حالت داره. گزینه ۱ سه حالتیه.

گزینه ۳ و دو =>>> یک حالتی هستند؟؟؟
یافتن تمامی ارسال‌های این کاربر

۳
ارسال:
  

fatemeh69 پاسخ داده:

RE: شمارش تعداد state های ماشین DFA

سلام
تو گزینه اول چون می خواد تعدادa ها حتما مضربی از ۳ باشه به ۳ تاحالت نیاز داریم حالتی که باقیمانده ی تعداد a ها بر ۳ برابر صفره، حالتی که باقیمانده ی تعداد a ها بر ۳ برابر یکه و حالتی که باقیمانده ی تعداد a ها بر ۳ برابر ۲ است. و حالت دریگری هم غیر از این وجود نداره
تو هر حالتی که باشیم دیدن b تاثیری در حالت ما نخواهد داشت (چون فقط برامون مهمه که تعداد a ها بر ۳ بخش پذیر باشه و تعداد b ها مهم نیست) و تو هر حالتی که باشیم با دیدن a به حالت بعدی می ریم. همین.
اگه می گفت رشته هایی عضو زبان هستند که باقی مانده ی تعداد a هاشون بر ۳ برابر ۲ باشه هم باز هم می شد ۳ تا state فقط final state مون فرق می کرد.
اگه می گفت رشته هایی عضو زبان هستند که باقی مانده ی تعداد a هاشون بر ۵برابر ۲ باشه می شد ۵ تا state
اگه می گفت رشته هایی عضو زبان هستند که باقی مانده ی تعداد a هاشون بر ۳برابر ۲ باشه و باقی مانده ی تعدادb هاشون بر ۳برابر ۱باشه می شد ۹تا state چون هم تعداد a ها در مدالیتی ۳ می تونه ۰,۱,۲ باشه هم تعداد b ها در مدالیتی ۳ می تونه ۰,۱,۲ باشه پس state هامون می شن ۰۰,۰۱,۰۲,۱۰,۱۱,۱۲,۲۰,۲۱,۲۲ که رقم سمت چپ تو هر state نشون دهنده ی تعداد a ها در مدالیتی ۳ و رقم سمت راست نشون دهنده ی تعداد b ها در مدالتی ۳ است.

اما در گزینه ی ۴ ام دقت کنید چون گفته تعداد a ها و دو برابر تعداد b ها مضربی از ۲ باشه خب یعنی اصلا تعداد b ها مهم نیست و این معادل است با این که بگوییم تعداد a ها مضربی از ۲ باشه که می دونیم تعداد state هاش می شه دوتا.

در زبان دوم با کمی دقت متوجه می شیم که سیگما استاره اما زبان گرینه ی سوم یک شرط برای رشته های ما می ذاره اونم این که هر موقع در رشته یه تعداد b ظاهر شد حتما باید بعدش حداقل یه a هم بیاد که باعث می شه زبان آن سیگما استار نباشه.
تو زبان هایی که عبارت منظم داریم برای شمارش حداقل تعداد state ها هم می تونید خودتون مستقیما dfa شو بکشید و مینیمال کنید هم می تونید از روش تقسیمات چپ متوالی استفاده کنید که خیلی هم روش مطمئنی هست. روش کار و هم تو این تاپیک گفتم :

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

واسه زبان گزینه سوم این تکنیکو پیاده می کنیم:
[tex]a^{-1}L=L[/tex]
[tex]b^{-1}L=b^{\ast}a(b^{\ast}a)^{\ast}[/tex]
[tex](ba)^{-1}L=(b^{\ast}a)^{\ast}[/tex]
[tex](bb)^{-1}L=b^{\ast}a(b^{\ast}a)^{\ast}[/tex]
[tex](baa)^{-1}L=(b^{\ast}a)^{\ast}[/tex]
[tex](bab)^{-1}L=b^{\ast}a(b^{\ast}a)^{\ast}[/tex]

خب دیگه به تکرار افتادیم پس state هامون می شن
[tex]L-\: b^{\ast}a(b^{\ast}a)^{\ast}-\: (b^{\ast}a)^{\ast}[/tex]

پس سه تا state داریم . تعداد final state هامون همبه تعداد اون هاییه که لاندا توشون دارن مثلا تو این زبان از بین [tex]L-\: b^{\ast}a(b^{\ast}a)^{\ast}-\: (b^{\ast}a)^{\ast}[/tex] فقط اولی و سومی لامدا دارند پس دوتا final state داریم

ارسال:
  

mostafa2012 پاسخ داده:

RE: شمارش تعداد state های ماشین DFA

(۱۳ بهمن ۱۳۹۳ ۱۲:۰۷ ب.ظ)fatemeh69 نوشته شده توسط:  سلام
تو گزینه اول چون می خواد تعدادa ها حتما مضربی از ۳ باشه به ۳ تاحالت نیاز داریم حالتی که باقیمانده ی تعداد a ها بر ۳ برابر صفره، حالتی که باقیمانده ی تعداد a ها بر ۳ برابر یکه و حالتی که باقیمانده ی تعداد a ها بر ۳ برابر ۲ است. و حالت دریگری هم غیر از این وجود نداره
تو هر حالتی که باشیم دیدن b تاثیری در حالت ما نخواهد داشت (چون فقط برامون مهمه که تعداد a ها بر ۳ بخش پذیر باشه و تعداد b ها مهم نیست) و تو هر حالتی که باشیم با دیدن a به حالت بعدی می ریم. همین.
اگه می گفت رشته هایی عضو زبان هستند که باقی مانده ی تعداد a هاشون بر ۳ برابر ۲ باشه هم باز هم می شد ۳ تا state فقط final state مون فرق می کرد.
اگه می گفت رشته هایی عضو زبان هستند که باقی مانده ی تعداد a هاشون بر ۵برابر ۲ باشه می شد ۵ تا state
اگه می گفت رشته هایی عضو زبان هستند که باقی مانده ی تعداد a هاشون بر ۳برابر ۲ باشه و باقی مانده ی تعدادb هاشون بر ۳برابر ۱باشه می شد ۹تا state چون هم تعداد a ها در مدالیتی ۳ می تونه ۰,۱,۲ باشه هم تعداد b ها در مدالیتی ۳ می تونه ۰,۱,۲ باشه پس state هامون می شن ۰۰,۰۱,۰۲,۱۰,۱۱,۱۲,۲۰,۲۱,۲۲ که رقم سمت چپ تو هر state نشون دهنده ی تعداد a ها در مدالیتی ۳ و رقم سمت راست نشون دهنده ی تعداد b ها در مدالتی ۳ است.

اما در گزینه ی ۴ ام دقت کنید چون گفته تعداد a ها و دو برابر تعداد b ها مضربی از ۲ باشه خب یعنی اصلا تعداد b ها مهم نیست و این معادل است با این که بگوییم تعداد a ها مضربی از ۲ باشه که می دونیم تعداد state هاش می شه دوتا.

در زبان دوم با کمی دقت مت.جه می شیم که سیگما استاره اما زبان گرینه ی سوم یک شرط برای رشته های ما می ذاره اونم این که هر موقع در رشته یه تعداد b ظاهر شد حتما باید بعدش حداقل یه a هم بیاد که باعث می شه زبان آن سیگما استار نباشه.
تو زبان هایی که عبارت منظم داریم برای شمارش حداقل تعداد state ها هم می تونید خودتون مستقیما dfa شو بکشید و مینیمال کنید هم می تونید از روش تقسیمات چپ متوالی استفاده کنید که خیلی هم روش مطمئنی هست. روش کار و هم تو این تاپیک گفتم :

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

واسه زبان گزینه سوم این تکنیکو پیاده می کنیم:
[tex]a^{-1}L=L[/tex]
[tex]b^{-1}L=a(b^{\ast}a)^{\ast}[/tex]
[tex](ba)^{-1}L=(b^{\ast}a)^{\ast}[/tex]
[tex](bb)^{-1}L=\phi[/tex]
[tex](baa)^{-1}L=(b^{\ast}a)^{\ast}[/tex]
[tex](bab)^{-1}L=a(b^{\ast}a)^{\ast}[/tex]

باتشکر فراوان!
یافتن تمامی ارسال‌های این کاربر

ارسال:
  

fatemeh69 پاسخ داده:

RE: شمارش تعداد state های ماشین DFA

(۱۳ بهمن ۱۳۹۳ ۱۲:۱۲ ب.ظ)mostafa2012 نوشته شده توسط:  باتشکر فراوان!
یه کم جوابم رو ویرایش کردم
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

Ametrine پاسخ داده:

RE: شمارش تعداد state های ماشین DFA

گزینه ۳ مشابه گزینه ۲ نیست؟!
یعنی تعداد حالت های اونم یک میشه؟!
کسی توضیح نمیده اینو؟ Confused

ارسال:
  

Jooybari پاسخ داده:

RE: شمارش تعداد state های ماشین DFA

(۲۹ دى ۱۳۹۳ ۰۴:۳۶ ب.ظ)Ametrine نوشته شده توسط:  گزینه ۳ مشابه گزینه ۲ نیست؟!
یعنی تعداد حالت های اونم یک میشه؟!
کسی توضیح نمیده اینو؟ Confused

یکی از تفاوت هاش اینه که گزینه ۳ رشته b رو تولید نمیکنه.
یافتن تمامی ارسال‌های این کاربر

ارسال: #۱۰
  

Ametrine پاسخ داده:

RE: شمارش تعداد state های ماشین DFA

(۲۹ دى ۱۳۹۳ ۰۵:۱۱ ب.ظ)Jooybari نوشته شده توسط:  یکی از تفاوت هاش اینه که گزینه ۳ رشته b رو تولید نمیکنه.
آهان، درسته
ممنون
یافتن تمامی ارسال‌های این کاربر

۰
ارسال: #۱۱
  

Elena_71 پاسخ داده:

RE: شمارش تعداد state های ماشین DFA

دوستان کاش جامع تر توضیح میدادن



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  تصمیم پذیری علوم ۹۱ ماشین تورینگ bluebaran ۲ ۱,۶۷۰ ۱۱ بهمن ۱۳۹۳ ۰۲:۲۳ ق.ظ
آخرین ارسال: bluebaran
  چند سوال درمورد تعداد حالات نهایی و شروع dfaها pooyaa ۲ ۱,۳۹۶ ۰۶ بهمن ۱۳۹۳ ۰۶:۵۵ ب.ظ
آخرین ارسال: pooyaa
  تعداد حالات نهایی nfa برای زبان دارای لاندا و فاقد لاندا pooyaa ۲ ۱,۵۲۹ ۰۶ بهمن ۱۳۹۳ ۰۶:۵۳ ب.ظ
آخرین ارسال: pooyaa
  توضیح در مورد ماشین تورینگ mostafa2012 ۴ ۱,۶۳۴ ۰۴ بهمن ۱۳۹۳ ۱۰:۰۹ ق.ظ
آخرین ارسال: mostafa2012
  بدست آوردن عبارت منظم یک dfa mostafa2012 ۸ ۲,۱۸۵ ۰۳ بهمن ۱۳۹۳ ۰۲:۲۴ ق.ظ
آخرین ارسال: Jooybari
Question آیا تعداد زیرمجموعه های شمارای RE ناشماراست؟ Ametrine ۵ ۱,۴۸۱ ۰۱ بهمن ۱۳۹۳ ۱۲:۵۶ ق.ظ
آخرین ارسال: fatemeh69
Question زبان منظم، DFA، حافظه، به خاطر آوردن! Ametrine ۷ ۲,۲۱۵ ۲۹ دى ۱۳۹۳ ۱۱:۴۰ ب.ظ
آخرین ارسال: Ametrine
  کمینه کردن ماشین maryam.roshan ۱ ۹۶۸ ۲۸ دى ۱۳۹۳ ۰۱:۲۲ ق.ظ
آخرین ارسال: Hamid_0311
Question تعداد حالات اتوماتای قطعی متناهی علوم کامپیوتر ۸۴ Ametrine ۳ ۱,۱۴۱ ۲۷ دى ۱۳۹۳ ۰۴:۴۳ ب.ظ
آخرین ارسال: Hamid_0311
  زبان ماشین- سراسری ۹۰ raha_ce ۴ ۱,۲۵۳ ۱۶ دى ۱۳۹۳ ۰۹:۱۰ ب.ظ
آخرین ارسال: raha_ce

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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