در این ویدیویی آموزشی قصد داریم فرم نرمال چامسکی را مطرح کرده و سپس نحوه تبدیل گرامر مستقل از متن به فرم نرمال چامسکی را بیان کنیم.
کیفیت فیلم بصورت پیش فرض بر روی حالت low تنظیم شده است و شما می توانید با استفاده از تنظیمات موجود، این آموزش را با بالاترین کیفیت مشاهده نمایید.
شما می توانید با استفاده از گزینه “متن فیلم”، متن مربوط به حل سوال را مشاهده کنید.
//******************************************************************************************************************************************//
پیشنهاد می شود قبل از مشاهده این آموزش، مروری بر مبحث نرمال کردن گرامرها داشته باشید.
یک گرامر مستقل از متن G را یک فرم نرمال چامسکی می گوییم، اگر هر قانون از گرامر به یکی از شکل‌های روبرو باشد؛ به اینصورت که شبه جمله سمت راست شامل دو متغیر و یا یک ترمینال است .
برای تبدیل گرامر به فرم نرمال چامسکی باید ۴ اقدام روبرو را انجام داد.
۱- حذف قوانین λ
۲- حذف قوانین یکه مانند A نتیجه می دهد B
۳-حذف متغیر غیرمفید
که با این سه عمل گرامر تا جای ممکن ساده می شود و
۴- تبدیل قوانین باقی مانده با طول شبه جمله سمت راست بیشتر از ۲ به فرم چامسکی
برای درک بهتر این موضوع یک مثال را با هم بررسی می کنیم. می خواهیم گرامر روبرو را به فرم نرمال چامسکی تبدیل کنیم.
گام اول برای تبدیل حذف قوانین λ می باشد.
برای حذف λ هر جایی که متغیر مربوط به آن ظاهر شود باید به جای آن λ گذاشته شود تا قوانین جدید مشخص گردد. در اینجا متغیرهای A و B ، λ تولید می کنند پس در تمام قوانین هر جایی که B یا A ظاهر شد λ می گذاریم.
توجه داشته باشید در طی مراحل انجام شده از رنگ قرمز به عنوان حذف متغیر در این مرحله از الگوریتم و رنگ سبز به عنوان اضافه شدن قانون جدید به مجموع قوانین است.
در این مرحله باید قوانین یکه را حذف نماییم. در این گرامر دو قانون یکه A و B وجود دارد که باید حذف و جایگزین شود.
که آن ها حذف و با قوانین مربوطه جایگزین کردیم.
قوانین غیرمفید در گرامر وجود ندارد که بخواهیم حذف کنیم. پس در گام سوم باید قوانینی که به فرم چامسکی نیستند را تبدیل کرد . در این گرامر در این مرحله ۴ مورد از قوانین وجود دارد که می بایست به فرم چامسکی تبدیل شود. قوانینی که در آنها عنصر پایانی دیده می شود.
بدین منظور ابتدا قوانین جدیدی تعریف می کنیم که از یک متغیر به ترمینال a برود و همچنین برای ترمینال b متغیر دیگری تعریف می کنیم.
متغیر Ua و Ub را در قوانین قبلی جایگزین می کنیم. در اینجا با جایگزینی متغیر چهار مورد از قوانینی که به فرم چامسکی نبودند، تصحیح شدند.
در فرم نرمال چامسکی طول جمله طرف راست قوانین نباید بیشتر از ۲ باشد، پس در این چهار قانون که طول جمله سمت راست بیشتر از ۲ است، اولین متغیر از سمت چپ را نگه داشته و به ازای متغیرهای باقی مانده یک متغیر جدید و قانون مربوط به آن را اضافه می کنیم . قانون جدید اگر به فرم چامسکی نبود این روال را ادامه می دهیم.
به این ترتیب گرامر تبدیل به فرم نرمال چامسکی شد.
اکنون با یک مثال دیگر روال تبدیل گرامر به فرم نرمال چامسکی را بررسی می کنیم.
در این مرحله برای حذف λ سه قانون جدید اضافه می شود.
در این گرامر متغیر A یک متغیر غیر مفید است زیرا در تمام قوانینش در شبه جمله سمت راست وجود دارد پس تمام قوانینی که این متغیر را دارد، باید حذف کرد.
برای تبدیل قوانین باقی مانده به فرم چامسکی ابتدا برای ترمینال هایی که یک متغیر خاص، آنها را بصورت تکی تعریف نکرده، متغیر و قانون مربوط به آن را ایجاد می کنیم. در اینجا دو ترمینال a و b بوسیله هیچ متغیری به صورت تکی تعریف نشده اند.
در قوانینی که ترمینال ها بصورت تکی نباشند متغیر مربوط به آن را جایگذاری می کنیم.
در قوانینی که طول شبه جمله سمت راست بیش از ۲ متغیر است با تعریف متغیر جدید و قوانین مربوط به آن، قوانین باقی مانده را به فرم نرمال چامسکی در می آوریم.
به این صورت که در این عبارات اولین متغیر از سمت چپ را نگه داشته و به ازای متغیرهای باقی مانده یک متغیر جدید و قانون مربوط به آن را اضافه می کنیم . قانون جدید اگر به فرم چامسکی نبود این روال را ادامه می دهیم.
همانطور که مشاهده می شود از قوانین ایجاد شده یک قانون به فرم چامسکی نیست، پس این قانون را هم جایگزین می کنیم.
به این ترتیب گرامر به فرم نرمال چامسکی تبدیل شد.
کوتاه ، مفید ، عالی
ممنون