تالار گفتمان مانشت

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

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

(27 دى 1393 04:39 ق.ظ)Jooybari نوشته شده توسط: [ -> ]سلام. گزینه ۲ میشه سیکما استار که یک حالت داره. گزینه ۱ سه حالتیه.

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

اگر امکان داره به سوالی که پرسیدم نیز جواب دهید باتشکر!

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

(29 دى 1393 04:36 ب.ظ)Ametrine نوشته شده توسط: [ -> ]گزینه ۳ مشابه گزینه ۲ نیست؟!
یعنی تعداد حالت های اونم یک میشه؟!
کسی توضیح نمیده اینو؟

یکی از تفاوت هاش اینه که گزینه 3 رشته b رو تولید نمیکنه.

(29 دى 1393 05:11 ب.ظ)Jooybari نوشته شده توسط: [ -> ]یکی از تفاوت هاش اینه که گزینه ۳ رشته b رو تولید نمیکنه.

آهان، درسته
ممنون

(27 دى 1393 04:39 ق.ظ)Jooybari نوشته شده توسط: [ -> ]سلام. گزینه ۲ میشه سیکما استار که یک حالت داره. گزینه ۱ سه حالتیه.

گزینه 3 و دو =>>> یک حالتی هستند؟؟؟

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

سلام
تو گزینه اول چون می خواد تعداد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 داریم

(13 بهمن 1393 12:07 ب.ظ)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]

باتشکر فراوان!

(13 بهمن 1393 12:12 ب.ظ)mostafa2012 نوشته شده توسط: [ -> ]باتشکر فراوان!

یه کم جوابم رو ویرایش کردم