علوم کامپیوتر ۸۷-اتوماتا قطعی و غیر قطعی - نسخه‌ی قابل چاپ

علوم کامپیوتر ۸۷-اتوماتا قطعی و غیر قطعی - MiladCr7 - 19 دى ۱۳۹۳ ۰۸:۴۰ ب.ظ سلام دوستان گزینه اول پاسخ صحیحه!!میشه بگید منظورش از اتواتای قطعی با تعداد نامتناهی حالت چیه؟؟

RE: علوم کامپیوتر ۸۷-اتوماتا قطعی و غیر قطعی - fatemeh69 - 20 دى ۱۳۹۳ ۱۲:۰۸ ق.ظ سلام غلط بودن گزینه های ۲و۳و۴ که واضحه اتوماتون قطعی متناهی یعنی dfa اتوماتون غیر قطعی متناهی یعنی nfa اما اتوماتون قطعی با تعداد حالت نامتناهی چیه؟ اگه به تعاریف انواع اتوماتون های dfa, nfa, pda, Tm, Lba بندازید می بینید که تعداد حالت ها در تمام این اتوماتون ها متناهی تاست پس اگر اتوماتونی را تصور کنیم که تعداد حالات آن نامتناهی تا باشد قطعا قدرت آن از ماشین تورینگ هم بیشتر است چون وقتی تعداد حالات نامتناهی است هر زبان مزخرفی هم که به ما بدهند باز ما می توانیم آن را پذیرش کنیم. مثلا می تونیم برای پذیرش هر کدوم از رشته های زبان از یه حالت استفاده کنیم. پس اینجوری هر زبانی که به ما بدن ما می تونیم با نامتناهی تا حالت اونو بپذیریم. ولی تو اتوماتون های با تعداد متناهی تا حالت چون تعداد حالت ها متنهای بود ما باید یه الگو یا pattern ای بین رشته ها کشف می کردیم و مثلا می گفتیم اگه فلان الگو بود برو فلان state یا مثلا تا زمانی که فلان الگو مشاهده می شود در فلان state بمان. وو به خاطر همین کشف الگو بود که دستمون بسته بود و یه سری زبان هایی بود که حتی تورینگ هم نداشت اما حالا که دستمون بازه و محدودیت نداریم