سلام
من تو نوشتن گرامر برای زبانها مشکل دارم،از روی گرامر میتونم با روش سعی و خطا زبانشو بنویسم ولی وقتی زبانو بده گرامرو بخواد نمیتونم بنویسم.
شما چجوری برای یه زبان گرامر مینویسید،یعنی از کجا شروع میکنید؟
مثلا برای این زبان به گرامر بنویسید:
L={a^i+1 b^2i|i>=0}
(۰۲ آبان ۱۳۸۹ ۱۲:۱۲ ق.ظ)mehr.iman نوشته شده توسط: سلام
من تو نوشتن گرامر برای زبانها مشکل دارم،از روی گرامر میتونم با روش سعی و خطا زبانشو بنویسم ولی وقتی زبانو بده گرامرو بخواد نمیتونم بنویسم.
شما چجوری برای یه زبان گرامر مینویسید،یعنی از کجا شروع میکنید؟
مثلا برای این زبان به گرامر بنویسید:
L={a^i+1 b^2i|i>=0}
برای یک زبان میشه چندین گرامر نوشت، و گرامر یک زبان یگانه نیست، یه راه این هستش که شما بیای یه گرامر ساده‌تر که بلد هستید و به این گرامر هم ربط داره(!)رو بنویسید و اونو تعمیم بدید به گرامر مطلوب، مثلاً تو همین مثالی که گفتید تعداد aها نصف تعداد bها به اضافه یک هست، میشه گرامر{a^n b^n } رو بنویسید
S-> aSb|lambda
حالا اگه تو گرامر بالا به جای b قرار بدیم bb گرامرمون تبدیل میشه به {a^n b^2n}
با این حساب فقط میمونه اون به اضافه‌ی یک برای aها که اگه به جای lambda قرار بدید a گرامر ساخته میشه:
S->aSbb|a
این یه راهی بود که من پیشنهاد دادم برای رسیدن به گرامر یک زبان برای هر نفر راهی هست
بله حق با آقا حمیده.
aa^i b^ib^i
s--> aSbb
s--> a
برای درک این مسئله باید قسمتی از کتاب که a^nb^n رو توضیح داده بخونید.
گراف (اتوماتا )هم می تونه کمک کنه.اول اتوماتاشو بکشید( ممکنه اوایل بهینه نکشید ولی با تمرین و سعی و خطا درست می شه )بعد که گره‌ها رو علامت گذاری کردید می تونید گرامر رو راحت بنویسید.
میتونید برای شروع اینجوری گرامر بنویسید مثلا توی این گرامر کوچکترین رشته a است بعد به ازای i های بعدی aaabbbb و aaaabbbbbb داریم اگه دقت کنید در هر بار افزایش i یک a و دو b اضافه شده با تشخیص این موضوع به سادگی گرامر رو مینویسیم. پس یکی تشخیص کوچکترین رشته مهمه و یکی تشخیص قانون حاکم بر گرامر.
من گرامر خطی راست رو از روی گراف به راحتی می نویسم ولی خطی چپ رو نه از روی گراف و نه از روی گرامر خطی راست نمی تونم بنویسم
(فقط ابتدای گرامر چپ(عبارت اول )که انتهای رشته است رو می تونم بنویسم)
لطفاً راهنمایی کنید
(۰۲ آبان ۱۳۸۹ ۰۸:۵۷ ق.ظ)hamidkhl نوشته شده توسط:(02 آبان ۱۳۸۹ ۱۲:۱۲ ق.ظ)mehr.iman نوشته شده توسط: سلام
من تو نوشتن گرامر برای زبانها مشکل دارم،از روی گرامر میتونم با روش سعی و خطا زبانشو بنویسم ولی وقتی زبانو بده گرامرو بخواد نمیتونم بنویسم.
شما چجوری برای یه زبان گرامر مینویسید،یعنی از کجا شروع میکنید؟
مثلا برای این زبان به گرامر بنویسید:
L={a^i+1 b^2i|i>=0}
برای یک زبان میشه چندین گرامر نوشت، و گرامر یک زبان یگانه نیست، یه راه این هستش که شما بیای یه گرامر ساده‌تر که بلد هستید و به این گرامر هم ربط داره(!)رو بنویسید و اونو تعمیم بدید به گرامر مطلوب، مثلاً تو همین مثالی که گفتید تعداد aها نصف تعداد bها به اضافه یک هست، میشه گرامر{a^n b^n } رو بنویسید
S-> aSb|lambda
حالا اگه تو گرامر بالا به جای b قرار بدیم bb گرامرمون تبدیل میشه به {a^n b^2n}
با این حساب فقط میمونه اون به اضافه‌ی یک برای aها که اگه به جای lambda قرار بدید a گرامر ساخته میشه:
S->aSbb|a
این یه راهی بود که من پیشنهاد دادم برای رسیدن به گرامر یک زبان برای هر نفر راهی هست
دوستان واقعا ممنون از پاسخاتون
آقا حمید این گرامری که شما نوشتید جواب میده و فک میکنم از نوع مستقل از متن باشه،حالا اگه بگن همونو به صورت حساس به متن بنویسید چیکار باید کرد؟
بعد اینکه همونطور که فرمودید برای یه زبان چندین گرامر وجود داره،بعد از اینکه گرامرو نوشتیم از کجا مطمئن شیم که گرامر مورد نظر همه رشته‌ها رو تولید میکنه؟(یا چجوری بفهیمم دوتا گرامر معادل هم هستن؟)
(۰۲ آبان ۱۳۸۹ ۱۱:۰۴ ق.ظ)nana2010 نوشته شده توسط: گراف (اتوماتا )هم می تونه کمک کنه.اول اتوماتاشو بکشید( ممکنه اوایل بهینه نکشید ولی با تمرین و سعی و خطا درست می شه )بعد که گره‌ها رو علامت گذاری کردید می تونید گرامر رو راحت بنویسید.والا من فقط فصل یکو خوندم و هنوز به اونجا نرسیدم،این درسم چون تو دانشگاه نداشتیم یه خورده برام سخته اولاش،حالا یواش یواش داره ازش خوشم میاد!
چون n=0 هم داریم کوچکترین رشته a هست اما اگر n>0 بود کوچکترین رشته aabb بود.
(۰۲ آبان ۱۳۸۹ ۱۱:۰۷ ق.ظ)afagh1389 نوشته شده توسط: میتونید برای شروع اینجوری گرامر بنویسید مثلا توی این گرامر کوچکترین رشته a است بعد به ازای i های بعدی aaabbbb و aaaabbbbbb داریم اگه دقت کنید در هر بار افزایش i یک a و دو b اضافه شده با تشخیص این موضوع به سادگی گرامر رو مینویسیم. پس یکی تشخیص کوچکترین رشته مهمه و یکی تشخیص قانون حاکم بر گرامر.بله درسته، نکته همون تشخیص قانونس،این مثال تقریبا ساده بود و راحت میشد قانونشو درآورد ولی بعضی جاها پیدا کردن قانونش سخته که البته اونم با تمرین حل میشه.
بنظر من اینکه آیا گرامر مثال نقض داره یا نه یعنی کاملا" جامع و مانع هست بسته به گرامر و زبان داره.سختی وآسونی مسئله هم بهمین بسته است. فرمولی هم من واسه اش ندیدم که شما بخواهید در همه موارد از اون تبعیت کنید. این یک مهارت هست که شما پیدا میکنید. یعنی اینکه آیا این گرامر میتونه تمام رشته های زبان رو تولید کنه یا نه. من ندیدم جایی فرمول خاصی داشته باشه. کسی دیده؟؟؟
خوب هر گرامر مستقل از متنی حساس به متن هن هست دیگه، این گرامری که ما نوشتیم حساس به متن هم هست،
میتونید رشته های مختلف توی گرامرتون امتحان کنید، تا به صحت گرامرتون مطمئن بشد
برای معادل بودن دو تا گرامر فکر میکنم بهترین راه پیدا کردن زبان مربوط به گرامر باشه، اگه گرامرها معادل باشن زبان یکسانی را تولید میکنن (نه اینکه دقیقاً زبانشونو بدست بیارید، همون که گرامرو بخونید و بفهمید که مثل هم رفتر میکنن که این کار دقت بالایی مخواد )