(۲۳ فروردین ۱۳۹۲ ۰۷:۰۷ ب.ظ)post98 نوشته شده توسط:  با سلام به تمامی دوستان

سوال رو ضمیمه کردم

۴ تا سوال هستش که باید بررسی کنیم ببینم منظم هست یا مستقل از متن من جواب دادم نظرتون چیه آیا درست گفتم یا غلط.؟

الف) با توجه به اینکه حالت محدود کننده وجود داره یعنی یک بازه وجود داره یا همون شرط (na<nb<nc) پس مستقل از متن هستش

ب)تو این گزینه هم حالت محدود کننده (j<1000) پس مستقل از متن هستش

ج)تو این گزینه محدود سازی وجود نداره یعنی حالت بازه ای رو در نظر نگرفته و فقط عدد ۱۰ رو محدود کرده پس منظم هستش

د)و گزینه د هم زمانی که ما یک تناظر یا یک رابطه بین حروف الفبا وجو داشته باشد آن زبان را مستقل از متن می گویییم اما چون در

این گزینه حرف c بین [tex]ww^{r}[/tex] اومده پس مستقل از متن نیست و منظم است



اگه اشتبا گفتم هر کدوم رو ممنون میشم بگید چرا یه توضیح کوتاه بدین ممنون میشم

مرسی

آخری مستقل از متن هست، اون C باعث میشه، مستقل از متن قطعی باشه، اگه اون c نبود میشد، مستقل از متن غیر قطعی.
کلا در صورتی زبانی منظم هست که بشه با حالت های محدود پیاده سازیش کرد، مثلا وقتی a+b!=10 رو داریم، تعداد محدودی عدد هست که جمعشون بشه ۱۰ پس میتونیم با dfa پیاده سازیش کنیم و منظم هست، جایی که ما نیاز به حافظه پشته ای برای تشخیص زبان داریم دیگه منظم نیست.مستقل از متن میشه.

ممنون که پاسخ دادین

پس در صورتی که حالت محدود کننده داشته باشیم می تونیم با dfa پیاده سازی کنیم پس باید درست حدس زده باشم
که گزینه الف و ب هم مستقل از متن هستش چون حالت محدود کننده هستش ؟

اون جوری که استاد ما به ما گفتش یه سوال مثل گزینه د حل کرد اما بدون c که گفت میشه مستقل از متن دیگه در مورد
قطعی و غیر قطعی به ما چیزی نگفت دلیلشم این بود که wwr به صورت مستقیم باهم رابطه دارن ولی حالا تو این گزینه د
c بین wwr هست که دیگه به صورت مستقیم با هم رابطه ندارند؟

Post 98 عزیز:
متاسفانه دلایل شما برای من مبهمه! محدود سازی بازه ای یعنی چی، البته تقصیر شما نیست من خیلی نظریه زبانم ضعیفه- حالا من دلیلم برای مورد "د" اینه ببینید شما سر در میارید چیزی:

اولا" برای تشخیص زبان منظم، یکی از راه ها کشیدن dfa یا nfa برای اون زبانه- شما یه کم اگر تو کاغذ شروع کنی برای ترسیم dfa برای زبان wcwR میبینی نمشه و نمیتونی (به خاطر ارتباط معکوس بین w , wR- چون dfa نتونستی بکشی پس منظم نیست حالا باید ببینی میتونی براش pda یا همون ماشین پشته ای بکشی (تو شکل زیر) یا نه اونوقت اگر یه ذره سعی کنی میبینی میشه، اونم به خاطر رابطه عکس w و wR ) -بله استاد شما درست گفت بخاطر وجود ارتباط بین w و wR حالا چه c این وسط باشه و چه نباشه - هر چند اگر c باشه مستقل ازمتن قطعیه

حالا بی زحمت اینجوری من رو تفهیم کنید که چرا گزینه "الف" مستقل از متنه؟؟ من میگم نیست

(۲۳ فروردین ۱۳۹۲ ۱۰:۰۷ ب.ظ)MajidManesht2012 نوشته شده توسط:  Post 98 عزیز:
متاسفانه دلایل شما برای من مبهمه! محدود سازی بازه ای یعنی چی، البته تقصیر شما نیست من خیلی نظریه زبانم ضعیفه- حالا من دلیلم برای مورد "د" اینه ببینید شما سر در میارید چیزی:

اولا" برای تشخیص زبان منظم، یکی از راه ها کشیدن dfa یا nfa برای اون زبانه- شما یه کم اگر تو کاغذ شروع کنی برای ترسیم dfa برای زبان wcwR میبینی نمشه و نمیتونی (به خاطر ارتباط معکوس بین w , wR- چون dfa نتونستی بکشی پس منظم نیست حالا باید ببینی میتونی براش pda یا همون ماشین پشته ای بکشی (تو شکل زیر) یا نه اونوقت اگر یه ذره سعی کنی میبینی میشه، اونم به خاطر رابطه عکس w و wR ) -بله استاد شما درست گفت بخاطر وجود ارتباط بین w و wR حالا چه c این وسط باشه و چه نباشه - هر چند اگر c باشه مستقل ازمتن قطعیه

حالا بی زحمت اینجوری من رو تفهیم کنید که چرا گزینه "الف" مستقل از متنه؟؟ من میگم نیست

گزینه الف مستقل از متن نیست، چون با یه ماشین پشته ای نمیشه ۳ تا شرط رو بررسی کنیم، مثلا برای اینکه تعداد a و b رو چک کنیم که b ها از a ها بیشتر باشن، به ازای a، تو پشته x میذاریم و به ازای b، از پشته x رو pop میکنیم، باید b رو ببینیم تو رشته ولی پشته خالی باشه، ولی برای چک کردن c ها دیگه b نداریم که بررسی کنیم.