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

ممنون

یادم نمیاد تو چه کتابی خوندم که نوشته بود حافظه ندارن این ماشینها!
تعداد حالتهاش اندازه مشخصی داره؟
یعنی میشه گفت چون تعداد حالت های یک زبان از فلان اندازه بیشتر میشه پس این زبان منظم نیست؟

(۲۹ دى ۱۳۹۳ ۰۹:۵۰ ق.ظ)Ametrine نوشته شده توسط:  

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

ممنون

یادم نمیاد تو چه کتابی خوندم که نوشته بود حافظه ندارن این ماشینها!
تعداد حالتهاش اندازه مشخصی داره؟
یعنی میشه گفت چون تعداد حالت های یک زبان از فلان اندازه بیشتر میشه پس این زبان منظم نیست؟

ماشین متناهی و به عبارت دیگه زبان منظم قابلیت استفاده از پشته رو نداره. پشته امکان یکبار استفاده از حافظه به اندازه نامحدود رو میده.
لم تزریق هم از این قاعده استفاده میکنه که فرض میکنه رشته ای که طولش بزرگتر از اندازه ماشینه رو نمیشه در یه تعداد حلقه قرار داد که میگه منظم نیست.
ماشین متناهی یه حداکثر تعدادی برای حالتهاش داره ولی این قابلیت رو که تمام زبانهایی که رشته هاشون نامحدود نیست رو قبول میکنه. یعنی اگه بدونیم یه عدد L وجود داشته باشه که طول تمام رشته های زبان از L کوچکتر باشه اون زبان منظم خواهد بود.

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

ممنون
یکبار استفاده از حافظه یعنی چی دقیقاً؟

(۲۹ دى ۱۳۹۳ ۰۴:۴۳ ب.ظ)Ametrine نوشته شده توسط:  ممنون
یکبار استفاده از حافظه یعنی چی دقیقاً؟

منظورم همون خاصیت پشتست. یعنی مقدار داخل پیشه رو نمیشه جداگانه برای مقایسه دو مقدار استفاده کرد.

ببخشید اگه سوالم اشتباهه یا هرچی.
من این درس رو خودم خوندم، کسی نیست سوالامو جواب بده.

این سوال تو کتاب پارسه بود:

کدام عبارت زیر درست است؟
i . یک ماشین متناهی (FA) هیچ حافظه ای ندارد.
ii. یک ماشین پشته ای (PDA) حافظه نامحدود با دسترسی محدود دارد.
iii. یک ماشین تورینگ خطی (LBA) حافظه ای محدود با دسترسی نامحدود دارد.
iv. یک ماشین تورینگ حافظه ای نامحدود با دسترسی نامحدود دارد.

کتاب گفته همه ی موارد درسته.

مگه DFA و NFA نوعی FA نیستن؟

گزینه سوم هم به نظر من اشتباه هست.
مگه ماشین کراندار خطی حافظه ی نامحدود نداره و فقط دسترسیش محدود به رشته ی ورودی که توی [ ] مشخص شده هست؟