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

شمارش تعداد 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

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  تعداد برگ درخت؟؟؟؟؟؟؟ rad.bahar ۴ ۴,۸۷۰ ۱۵ آذر ۱۴۰۲ ۱۱:۵۳ ق.ظ
آخرین ارسال: mohamadrra
  اصول ماشین های کنترل عددی و مطلبی ملینا ارشد ۱ ۲,۳۸۸ ۲۸ بهمن ۱۴۰۰ ۰۸:۰۹ ب.ظ
آخرین ارسال: vista2000
  بوک کلاب ماشین لرنینگ با حضور متخصص از شرکت های گوگل ، اساتید و دانشجویان دکترا و. Doctorwho ۰ ۱,۷۰۴ ۱۳ آبان ۱۴۰۰ ۱۲:۰۹ ب.ظ
آخرین ارسال: Doctorwho
  تعداد جواب mostafaheydar1370 ۲۱ ۱۹,۴۶۱ ۰۱ مهر ۱۳۹۹ ۱۱:۴۱ ب.ظ
آخرین ارسال: miinaa
  سوال یادگیری ماشین isoa ۳ ۴,۳۹۸ ۰۸ مرداد ۱۳۹۹ ۰۶:۳۴ ق.ظ
آخرین ارسال: BBumir
  تعداد روش های نوشتن عدد n ss311 ۲ ۳,۳۸۳ ۱۳ بهمن ۱۳۹۸ ۰۵:۲۷ ب.ظ
آخرین ارسال: ss311
  تعداد مسیرها در گراف ss311 ۰ ۲,۰۴۶ ۰۸ بهمن ۱۳۹۸ ۱۲:۴۷ ب.ظ
آخرین ارسال: ss311
  تعداد درخت فراگیر ss311 ۰ ۲,۳۲۷ ۰۶ بهمن ۱۳۹۸ ۰۵:۰۶ ب.ظ
آخرین ارسال: ss311
  تعداد توابع پوشا ss311 ۰ ۲,۰۹۳ ۰۶ بهمن ۱۳۹۸ ۰۴:۵۷ ب.ظ
آخرین ارسال: ss311
  تعداد اعداد ۵ رقمی هم ارز ss311 ۲ ۲,۶۵۸ ۰۶ بهمن ۱۳۹۸ ۰۴:۳۹ ب.ظ
آخرین ارسال: ss311

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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