اگر G یک گرامر مستقل از متن باشد الگوریتمی وجود دار که:
۱-تعیین کند L(G متناهی است یا خیر
۲-تعیین کند L(G تهی است یا خیر
۳-تعیین کند L(G= سیگما *
اگر L زبانی مستقل از متن باشد الگوریتمی وجود دار که:
۱-تعیین کند L= سیگما * یا خیر؟
اول اینکه این جملات درست هستن یا نه
بعد این عبارت L(G= سیگما * یعنی زبان ما نامتناهیه؟
بعد تفاوتی بین این دو جمله هست در عبارات بالا
اگر L زبانی مستقل از متن باشد
اگر G یک گرامر مستقل از متن باشد
دوباره اشتباه چاپی فکر کنم منو گمراه کرده.
با تشکر
سیگما استار نامتناهی هست. اگر حروف الفبا متناهی باشد میشه زبان حاصل رو شمرد (با مرتب کردن به ترتیب دیکشنری) و در نتیجه یک نگاشت هست که اون رو به اعداد طبیعی به صورت یک به یک و پوشا میبره و بنابراین کاردینالیتی اون برابر با اعداد طبیعی است یعنی نامتناهی و شمارا خواهد بود. و اگر حروف الفبا نامتناهی باشند که واضحه که زبان هم نامتناهی هست.
بنابراین برابری زبان با سیگما استار به معنی نامتنهای بودن اون هست اما هر زبان نا متناهی با سیگما استار برابر نیست ! و این دو با هم تفاوت دارن
در کل فکر نمیکنم تفاوتی تو منظور طراح باشه بین زبان و گرامر. خب اگر زبان مستقل از متن باشه پس گرامر داره پس رو گرامرش الگوریتم میزنیم
یا به عکس
و اما در مورد اون گزاره ها :
از علامت شروع گرامر شروع کن و به تعداد ناپایانه هات حرکت در نظر بگیر
مثلا ۳ تا ناپایانه اگر داری ۳ حرکت
توی این ۳ حرکت اگر ناپایانه تکراری پیش اومد زبان نامتناهی هست در غیر اینصورت متناهیست
فقط توجه کنید همه حالات باید چک بشه یعنی اگر یه حالت از حرکات ناپاینه غیرتکراری نداد دلیل بر متناهی بودن زبان نیست
چک کردن این تعداد حرکات هم به صورت متناهی قابل انجامه چون هم تعداد ناپایانه ها متناهیست و هم تعداد جملات هر ناپایانه
(حتی با درخت اشتقاق هم میشه انجام داد)
به نظر من تهی بودن رو هم میشه تشخیص داد
چون الگوریتم وجود داره که ناپاینه های غیرقابل دسترسی رو حذف میکنه و همچنین unit ها رو
بعد از این هر پایانه ای که در گرامر موجود بود قطعا تضمین وجود داره که بهش خواهیم رسید و زبان تهی نیست
یا اینکه پایانه ای وجود نخواهد داشت و زبان تهی هست
* اگر منظور از تهی بودن تولید فقط اپسیلون باشه
در مورد سیگما استار مطمئن نیستم. میدونم از قسمت قبلی نمیشه این رو نتیجه گرفت چون زبان مستقل از متن روی مکمل گیری بسته نیست
پ.ن : من متناسب با درک و سواد خودم جواب دادم امیدوارم اگر اشتباه هست دوستان دیگه هم نظر بدن که استفاده کنیم