۱
subtitle
ارسال: #۱
  
شمارش تعداد state های ماشین DFA
سلام
ببخشید من توی این مبحث خیلی ضعف دارم چیکار کنم (تواین مدت باقیمانده؟؟؟؟) اصولا همه اش اشتباه مزنم...(الان زدم ۱ میگه ۲!)
ببخشید من توی این مبحث خیلی ضعف دارم چیکار کنم (تواین مدت باقیمانده؟؟؟؟) اصولا همه اش اشتباه مزنم...(الان زدم ۱ میگه ۲!)
۳
ارسال: #۲
  
RE: شمارش تعداد state های ماشین DFA
سلام. گزینه ۲ میشه سیکما استار که یک حالت داره. گزینه ۱ سه حالتیه.
ارسال: #۳
  
RE: شمارش تعداد state های ماشین DFA
ارسال: #۴
  
RE: شمارش تعداد state های ماشین DFA
۳
ارسال: #۵
  
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 داریم
تو گزینه اول چون می خواد تعداد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 داریم
ارسال: #۶
  
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]
باتشکر فراوان!
ارسال: #۷
  
RE: شمارش تعداد state های ماشین DFA
۰
ارسال: #۸
  
RE: شمارش تعداد state های ماشین DFA
گزینه ۳ مشابه گزینه ۲ نیست؟!
یعنی تعداد حالت های اونم یک میشه؟!
کسی توضیح نمیده اینو؟
یعنی تعداد حالت های اونم یک میشه؟!
کسی توضیح نمیده اینو؟
ارسال: #۹
  
RE: شمارش تعداد state های ماشین DFA
ارسال: #۱۰
  
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?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close