آیا زبان {۰ =< L = { ai bj ck dj ei fk | i , j , k حساس به متن است؟ چرا؟
کلا حساس به متن بودن را فقط از روی گرامر حساس به متن نوشتن می شود تشخیص داد؟اگر رشته تهی هم در زبان داشته باشیم مثل این سوال گرامر حساس به متن که رشته تهی را تولید نمی کند پس چه باید کرد؟نوشتن گرامر حساس به متن که خیلی سخت است پس کلا باید برای تشخیص حساس به متن چه کار کرد؟
با عرض پوزش طولانی شد
حساس به متن بودن را با بسط گرامر ورشته های زبان میشه تشخیص داد . و اینکه برای یک رشته دو اشتقاق متفاوت داشته باشیم
(۱۰ دى ۱۳۹۱ ۱۱:۰۸ ب.ظ)lestarlight نوشته شده توسط: اگر رشته تهی هم در زبان داشته باشیم مثل این سوال گرامر حساس به متن که رشته تهی را تولید نمی کند پس چه باید کرد؟مهم نیست رشته تهی هم داشته باشد یا نه.مهم اینکه بتونیم ثابت کنیم این زبان دو اشتقاق مختلف برای یک رشته داره
کلا حساس به متن یعنی به متغیرها و الفبا(پایانه)هایی که در اطرافش وجود داره حساس هست و بستگی داره که قبل و بعد یک پایانه یا متغیر چه حرفی و چه تعدادی بیاد . در حالی که مستقل از متن اینطور نیست و اشتقاق ها اصلا ربطی به متغیرها و الفبایی که اطراف یک متغیر میاد نداره
حساس به متن به این خاطر میتونه اشتقاقهای مختلفی برای یک رشته داشته باشه که محدودیتی برای تعداد متغیرها و الفبا در سمت چپ یا است قوانین تولید نداره
یک مثال از رشته های این زبان
(۱۰ دى ۱۳۹۱ ۱۱:۰۸ ب.ظ)lestarlight نوشته شده توسط: {۰ =< L = { ai bj ck dj ei fk | i , j , kمیتونه این باشه :
aa bbb c ddd ee f
در این زبان چون نیاز به حافظه برای نگهداری تعداد الفبا داریم ، و در واقع به هم وابستگی عددی دارند پس مستقل از متن هست و با ماشین پشته ای قابل پیاده سازی است
(۱۱ دى ۱۳۹۱ ۱۲:۴۹ ق.ظ)fatima1537 نوشته شده توسط: یک مثال از رشته های این زبان(۱۰ دى ۱۳۹۱ ۱۱:۰۸ ب.ظ)lestarlight نوشته شده توسط: {۰ =< L = { ai bj ck dj ei fk | i , j , kمیتونه این باشه :
aa bbb c ddd ee f
در این زبان چون نیاز به حافظه برای نگهداری تعداد الفبا داریم ، و در واقع به هم وابستگی عددی دارند پس مستقل از متن هست و با ماشین پشته ای قابل پیاده سازی است
ببخشید من که هرچی فکر کردم این زبان با ماشین پشته ای قابل پیاده سازی نیست میشه بفرمایید چطور شما اینو پیاده کردید؟؟؟
بعد یه سوال دیگه در همین راستا، این ماشین پشته ای که فرمودید از پشته استفاده میکنه(خوب سوال واسم پیش اومد!!!
)؟؟؟؟؟؟؟؟!!!
شک نکنید مستقل از متن نیست. ولی میشه یه گرامز حساس به متن براش استفاده کرد.
با لم تزریق میشه اثبات کرد مستقل از متن نیست. همینجوری هم از تعریفش معلومه. تعداد i,j که توی پشته میره باید قبل از k پاپ بشن. اگه c و f بهم وابسته نبودن مستقل از متن میشد.
خیالتونو راحت کنم گرامری که به این راحتی قابل تعریف باشه در بدترین شرایط حساس به متن هست. شما فقط منظم بودن و مستقل از متن معین و نامین بودنشو چک کنید کافیه. رشته تهی رو هم حالت خاص درنظر بگیرید. گرامر حساس به متن تهی رو قبول نمیکنه ولی زبان حساس به متن میتونه اجتماع زبان یک گرامر و رشته تهی باشه. (چیزی از ارزشهای گرامر حساس به متن کم نمیشه!!
)
سلام .
من یه سوال دارم چطور وقتی b,c,d ها روی a قرار گرفتن توی پشته e رو با a مقایسه کنیم !!!!!!!!!!!!!!؟؟؟؟؟؟؟؟؟؟؟؟؟
به قول جویباری جان شک نکنید که مستقل از متن نیست .
بازم به قول جویباری جان گرامرهای حساس به متن اینقدر قدرت دارند که اکثر زبان ها رو پوشش بدن . اگر در تست کلاس ها پایین تر زبان ها بود(مستقل از متن، منظم،....) شما فقط کافیه کلاس های پایین تر رو امتحان کنید چون در ۹۹ درصد حالات هر نوع زبانی رو میشه گرامر حساس به متن واسش نوشت .
واسه تشخیص حساس به متن بودن زبان یا به عبارتی مستقل از متن نبودن یه زبان از لم تزریق میشه استفاده کرد.
یا اگه بتونیم بفهمیم که مثلا واسه درست کردن ماشین پشته ای اون زبان با یک پشته نمیتونیم این کار رو انجام بدیم یعنی اون زبان مستقل از متن نیست. پس حساس به متنه.