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

سلام

چه روشی وجود داره که بفهمیم یک زبان از نوع خطی هست؟!

اگ بتونیم براش بتونیم ی گرامر خطی بنویسیم خطیه.
اگر هم تشخیص بدیم منظمه، میشه فهمید یا خطی راست هست یا چپ
زبانی ک خطی باشه مستقل از متن هم هست، پس اگ تشخیص بدیم مستقل از متن هست پس خطی هم هست
نمیدونم راه دیگه ای هم هست یا نه

(08 بهمن 1393 07:51 ب.ظ)nazanin2020 نوشته شده توسط: [ -> ]اگ بتونیم براش بتونیم ی گرامر خطی بنویسیم خطیه.
اگر هم تشخیص بدیم منظمه، میشه فهمید یا خطی راست هست یا چپ
زبانی ک خطی باشه مستقل از متن هم هست، پس اگ تشخیص بدیم مستقل از متن هست پس خطی هم هست
نمیدونم راه دیگه ای هم هست یا نه

مرسی

(08 بهمن 1393 07:51 ب.ظ)nazanin2020 نوشته شده توسط: [ -> ]زبانی ک خطی باشه مستقل از متن هم هست، پس اگ تشخیص بدیم مستقل از متن هست پس خطی هم هست

سلام. تا اونجایی که اطلاع دارم این جملتون اشتباهه و زبانهای خطی زیرمجموعه زبانهای مستقل از متنن.

سلام.اره درست میگید هر زبان خطی مستقل از متن هست ولی عکسش لزوما صحیح نیست

(08 بهمن 1393 07:46 ب.ظ)arefeh.hp نوشته شده توسط: [ -> ]سلام



چه روشی وجود داره که بفهمیم یک زبان از نوع خطی هست؟!

سلام
یکی از راه های تشخیص زبان خطی اینه که بتونیم اون زبانو به وسیله یک ماشین پشته ای single turn پیاده سازی کنیم.حالا ماشین پشته ای single turn یعنی اگه یکبار پشته شروع به کم کردن ارتفاع کرد(برداشتن نمادها از پشته) دیگه دوباره اونو افزایش نده.(گذاشتن نمادها در پشته)
مثلا زبان (a^n b^n )
با دیدن a،aها رو تو پشته پوش میکنیم و وقتی b اومد شروع می کنیم به پاپ کردن.الان شروع کردیم به کاهش ارتفاع پشته و دیگه هرگز ارتفاع پشته رو زیاد نکردیم.پس این زبان خطیه.
موفق باشید

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

سلام. بله درست میگید. من ب این دقت نکرده بودم ک یه زبان مستقل از متن میتونه خطی نباشه. ب این دقت کرده بودم هر خطی ای حتما مستقل از متن هست

نکته ی خوبی گفتید

ممنون